Why you should never, EVER write an article that advises other people to never, EVER do something:
a) You have red gnomes jumping in front of you
b) You have no idea why, in my case, using linked lists actually makes a lot of sense
c) if linked lists were to be "considered evil", someone else would have found out in the last 20 years.
The bottom line is: know what you're doing. The article has a point (locality of reference) and therefore it's worthwhile. The advise to simply not use linked lists, doesn't help.
The article has some good points about cache locality, but to suggest that you should never, EVER use linked-list is just terrible, terrible, terrible advice.
Well we should obviously NEVER EVER use any LISP derivatives (car/cdr/cons).
These sort of articles make me sigh. They are narrow minded and miss the point that everything is a compromise and choosing the right compromise is the art, not a bunch of explicit rules.
On the subject, I don't think a real native LISP machine would have cache locality problems. An x86 perhaps which brings in the question that doesn't the architecture define what is good and bad and isn't it a compiler's job to make this issue go away (not ours).
Until then, why do not we all just stay away from the linked-list for the time being? After all C++ is all about performance - and linked-list is not!
No, thank you. Instead, why don't we try and understand the benefits and pitfalls of various data structures? Although linked lists may not be a great generic data structure, they can be incredibly useful for certain types of actions. Enumerating their strengths is a much more useful exercise than asserting sweeping generalizations.
As for your example: any stack or queue data structure is more efficiently implemented with a linked list than an array/vector. (Or any data structure that just needs to do operations on the head/tail of a data structure.)
Examples based on integers. This is lame, because moving integers in vectors is only memcpy call.
Linked-list is better for heavy objects. Inserting heavy objects into middle of container causes N copy-constructors calls. Here comes the pain.
Some kind of medium between vectors and lists is vector of pointers(or indexes) to objects (stored in another vector). You need to divide storing from ordering, and you get positives side of each variant.
The author does an insertion sort in a linked list, of course that's going to be slow.
For a sorted insert you need to do 2 things: find the right spot for insertion and the insert itself. An insertion sort does this n times.
For a simple array/vector that's:
search: O(n)
insert: O(1)
total takes (O(n) + O(1)) x O(n) = O(n^2)
For a linked list:
search: O(n)
insert: O(n)
total takes (O(n) + O(n)) x O(n) = O(n^2)
There we go, the algorithm takes O(n^2) for both data structures. The theory already proves that a linked list has absolutely no advantage over an array when using this algorithm. On top of that, iterating over a linked list is slower than over an array for various reasons, even thought they are both O(n). So that's where the difference is coming from.
The example he uses is clearly a wrong use case for a linked list, it's plain wrong to conclude that the whole data structure should never be used.
In the basic case, linked lists are O(n) for inserting at position n, on account of having to follow n elements' worth of pointer trail to get to that position. When you're inserting at the first position (as should normally be the case for most applications to which linked lists are well suited), n happens to be 1.
For certain applications where you already have a pointer to position n by the time you find out you need to insert there, then insertion does end up taking constant time as long as it's not a persistent linked list. But big-O is for describing the worst case, not the ideal case that you can achieve given certain optimizations.
11 comments
[ 3.0 ms ] story [ 33.2 ms ] threada) You have red gnomes jumping in front of you
b) You have no idea why, in my case, using linked lists actually makes a lot of sense
c) if linked lists were to be "considered evil", someone else would have found out in the last 20 years.
The bottom line is: know what you're doing. The article has a point (locality of reference) and therefore it's worthwhile. The advise to simply not use linked lists, doesn't help.
These sort of articles make me sigh. They are narrow minded and miss the point that everything is a compromise and choosing the right compromise is the art, not a bunch of explicit rules.
On the subject, I don't think a real native LISP machine would have cache locality problems. An x86 perhaps which brings in the question that doesn't the architecture define what is good and bad and isn't it a compiler's job to make this issue go away (not ours).
No, thank you. Instead, why don't we try and understand the benefits and pitfalls of various data structures? Although linked lists may not be a great generic data structure, they can be incredibly useful for certain types of actions. Enumerating their strengths is a much more useful exercise than asserting sweeping generalizations.
As for your example: any stack or queue data structure is more efficiently implemented with a linked list than an array/vector. (Or any data structure that just needs to do operations on the head/tail of a data structure.)
http://docs.oracle.com/javase/6/docs/api/java/util/ArrayDequ...
I highly recommend that every Java developer read the source for this class (and the rest of the java.util Collections).
Linked-list is better for heavy objects. Inserting heavy objects into middle of container causes N copy-constructors calls. Here comes the pain.
Some kind of medium between vectors and lists is vector of pointers(or indexes) to objects (stored in another vector). You need to divide storing from ordering, and you get positives side of each variant.
For a sorted insert you need to do 2 things: find the right spot for insertion and the insert itself. An insertion sort does this n times.
For a simple array/vector that's:
search: O(n)
insert: O(1)
total takes (O(n) + O(1)) x O(n) = O(n^2)
For a linked list:
search: O(n)
insert: O(n)
total takes (O(n) + O(n)) x O(n) = O(n^2)
There we go, the algorithm takes O(n^2) for both data structures. The theory already proves that a linked list has absolutely no advantage over an array when using this algorithm. On top of that, iterating over a linked list is slower than over an array for various reasons, even thought they are both O(n). So that's where the difference is coming from.
The example he uses is clearly a wrong use case for a linked list, it's plain wrong to conclude that the whole data structure should never be used.
For certain applications where you already have a pointer to position n by the time you find out you need to insert there, then insertion does end up taking constant time as long as it's not a persistent linked list. But big-O is for describing the worst case, not the ideal case that you can achieve given certain optimizations.
mdwrigh2 is totally right. I flipped the O(1) for linked list insertion with the O(n) for verctor insertion :).