Discussion on:
View:
Show:
I code VB and I have never (except when I was learning the language) dimmed an array with a set size. I dim them as variants and redim them based on the count of rows and columns returned . I am not sure that your argument that you must know the size of an array to use it is completely valid, but I have only been programming for 3 years so I could be all wet.
In my experience arrays in VB, except for when you ReDim them, are pretty much set to a certain size (are are difficult to work with, imho). In other scripting languages, such as JScript or Perl, things are much more flexible. Of course, none of these languages have pointers, so there is no choice but to use C for that.
In VB, the redim statement will actually reallocate the original array elements into a new array with the new size, then drop the original array used. This is, like the author said, under the hood of the programming language that is used. This operation thus becomes expensive. Remember, all arrays are allocated contigously in memory.
You ARE using it when you know the size. You are figuring out the size at run time, but you are still only using it after you know it's size AND have declared it to be that size (via the ReDim). That you have delcared the variable before you figure out the size is entirely irrelevant.
When you ReDim a collection, you only know that it is currently not big enough, so make it larger. Depending on the language and the collection function, you may not even know how much larger you made the collection.
As the author explained, there are some languages that provide the functionalities that take the basic data structure and enhance that data structure to releive the user of that data structures short comings. The lower level implementation is stillas the author presented, but the implementation ( as Java or VB per se) have wrote things in the language to help you out.
But the basic data structures that the author mentions are correct.
But the basic data structures that the author mentions are correct.
This article is not directed at the VB programmer as VB does not have linked lists.
Also, you shouldn't Dim arrays always as Variants since they take up the most memory not to mention the type checking issues.
Variants allow the programmer to be sloppy, and are shunned for apps in a business environment. This is the main reason I'm glad they were dropped from VB.NET.
Also, you shouldn't Dim arrays always as Variants since they take up the most memory not to mention the type checking issues.
Variants allow the programmer to be sloppy, and are shunned for apps in a business environment. This is the main reason I'm glad they were dropped from VB.NET.
I am little surprised to see a discussion of arrays versus linked lists in the era of object oriented programming.
In an object oriented approach, most of the data that would be combined in tables in a procedural model are distributed in classes. Once a specific object or class instance is selected, there are no more tables to access. Sets of objects are typically handled as collections with the details of the implementation hidden from the developer. The implementation is usually done asa dynamically allocated and sized array as opposed to a linked list, but most developers will never see this detail.
I would strongly urge developers to avoid working with arrays or linked lists. C programmers should strongly cosider C++, adn C++ programmers should look at standard templates like vector or list. Visual Basic has its own collection classes, and I am sure similar constructs exist in Java.
I enjoyed the historical reference to linked lists, but I would advise programmersto use more modern constructs, if at all possible.
In an object oriented approach, most of the data that would be combined in tables in a procedural model are distributed in classes. Once a specific object or class instance is selected, there are no more tables to access. Sets of objects are typically handled as collections with the details of the implementation hidden from the developer. The implementation is usually done asa dynamically allocated and sized array as opposed to a linked list, but most developers will never see this detail.
I would strongly urge developers to avoid working with arrays or linked lists. C programmers should strongly cosider C++, adn C++ programmers should look at standard templates like vector or list. Visual Basic has its own collection classes, and I am sure similar constructs exist in Java.
I enjoyed the historical reference to linked lists, but I would advise programmersto use more modern constructs, if at all possible.
OOP doesn't invalidate proper data structure analysis, it simply allows for hidden implementation. The VB "Collection" is implemented with one or more of these underlying ADT's (abstract data types) and just because you can and should hide their implementation in code does not mean you should ignore their implications in the architecture.
The advantage that OOP offers is a uniform interface (look at STL and the .Net interfaces) to a number of different data structures. This allows for the choice of which data structure to use to be seperated from the code that uses it. Then, the choice of which ADT to use becomes purely a matter of analyzing how it is used, without worrying about changing any of your code.
Just because most developers now won't ever code these objects themselves (outside of school) doesn't mean that they can afford to ignore what they are. You still need to know when it is a good idea to use a vector (ie array) vs a list, even though your code will still be functionally correct with either.
The advantage that OOP offers is a uniform interface (look at STL and the .Net interfaces) to a number of different data structures. This allows for the choice of which data structure to use to be seperated from the code that uses it. Then, the choice of which ADT to use becomes purely a matter of analyzing how it is used, without worrying about changing any of your code.
Just because most developers now won't ever code these objects themselves (outside of school) doesn't mean that they can afford to ignore what they are. You still need to know when it is a good idea to use a vector (ie array) vs a list, even though your code will still be functionally correct with either.
The capabilities build into language provided collection classes, templates, etc., are far more powerful than the standard linked list and array.
A standard linked list has list pointers embedded in the basic structure. The classic problem with linked lists is when an item is placed on two lists leading to broken and merged lists.
A standard array is a fixed size item, with little consideration given to dynamic sizing or inserting or deleting records. The classic problems with fixed length arrays are: wasted storage and overruns.
Most collections are built with dynamically sized arrays and handle insertions and deletions with low level operations like the C memcpy. In operation, these collections tend to size themselves to fit the maximum needs of the program with a minimal amount of memory reallocation.
Modern collection classes have evolved far beyond their beginnings with linked lists and arrays. In general, I would recommend using the provided collection functions and only revert back to linked lists or arrays under demonstrable and measureable situations.
A standard linked list has list pointers embedded in the basic structure. The classic problem with linked lists is when an item is placed on two lists leading to broken and merged lists.
A standard array is a fixed size item, with little consideration given to dynamic sizing or inserting or deleting records. The classic problems with fixed length arrays are: wasted storage and overruns.
Most collections are built with dynamically sized arrays and handle insertions and deletions with low level operations like the C memcpy. In operation, these collections tend to size themselves to fit the maximum needs of the program with a minimal amount of memory reallocation.
Modern collection classes have evolved far beyond their beginnings with linked lists and arrays. In general, I would recommend using the provided collection functions and only revert back to linked lists or arrays under demonstrable and measureable situations.
I think the use of arrays and/or linked lists, or collections has a lot to do with the language used as well as the demands of the application.
I use C++ to make games and game supplements, so I try to be as efficient and economic with the systemresources as possible, so even though my objects are classes, I usually have arrays or linked lists of class objects and I am in control of when and how they are allocated and deallocated.
In an application using MFC, VB or other higher level tools, many details are hidden from the programmer, but under the hood they still exist.
The decision to use such tools, already implies that a level of performance is sacrifised for ease in development, which of course is a valid design decision formany types of applications.
I use C++ to make games and game supplements, so I try to be as efficient and economic with the systemresources as possible, so even though my objects are classes, I usually have arrays or linked lists of class objects and I am in control of when and how they are allocated and deallocated.
In an application using MFC, VB or other higher level tools, many details are hidden from the programmer, but under the hood they still exist.
The decision to use such tools, already implies that a level of performance is sacrifised for ease in development, which of course is a valid design decision formany types of applications.
An array or linked list does not give any more control to the allocation or deallocation of an object than something like an STL list or vector template.
In terms of efficiency, when walking through a collection, I think you will find the use of an iterator (as in the collection templates) as the most efficient, followed by indexing through an array of pointers, with the least efficient methods being indexing through an array of structs or walking a linked list. I also would add, though, that if the efficiency at this level is a concern, that none of the above solutions is probably appropriate.
As most software (games may be excluded from this) has a significant life time. Added complexity in the initial design translates into added difficulty in maintenance. I always caution developers to be very certain of performance gains (i.e. measure it) before selecting a more complex solution.
In terms of efficiency, when walking through a collection, I think you will find the use of an iterator (as in the collection templates) as the most efficient, followed by indexing through an array of pointers, with the least efficient methods being indexing through an array of structs or walking a linked list. I also would add, though, that if the efficiency at this level is a concern, that none of the above solutions is probably appropriate.
As most software (games may be excluded from this) has a significant life time. Added complexity in the initial design translates into added difficulty in maintenance. I always caution developers to be very certain of performance gains (i.e. measure it) before selecting a more complex solution.
The article states that Link-Lists are one-dimensional by nature, however, with simple modifications they can easily be made multi-dimensional. These are quite handy when you need a multi-dimensional array structure but don't want to waste the memory on empty elements.
If you've ever touched LISP, you'll know that linked list can almost express all kinds of basic data structures, probably except for hashtable.
A good example of a multidimensional linked list is the skip list datastructure, even if you might not concider it simple. That's a really nice dynamic structure with logarithmic searching (and thus editing). I found a neat applet that shows how thestructure works:
http://iamwww.unibe.ch/~wenger/DA/SkipList/
http://iamwww.unibe.ch/~wenger/DA/SkipList/
One day I decided to test different data structures for efficiency. What I found was:
-Arrays are more efficient when timing is involved. They are alot faster when it comes to smaller amounts of data.
-Link lists are more efficient memory wise. However, as the data being handle becomes bigger, the linked list turns out to be faster than the array.
-Arrays are alot easier than lists to code.
Just one more thing. To those people who say that there are easier implementations with certain languages, they all work the same underneath. Being able to code ADT's puts you one step up above all those wannabe programmers.
-Arrays are more efficient when timing is involved. They are alot faster when it comes to smaller amounts of data.
-Link lists are more efficient memory wise. However, as the data being handle becomes bigger, the linked list turns out to be faster than the array.
-Arrays are alot easier than lists to code.
Just one more thing. To those people who say that there are easier implementations with certain languages, they all work the same underneath. Being able to code ADT's puts you one step up above all those wannabe programmers.
Memory associated with linked lists can also be an issue. If you have a singly dimensioned array with N floating point items, then a singly linked list will have 2 N items; a doubly linked list, 3 N items.
- Keyboard Shortcuts:
- Prev
- Next
- Toggle
