3 ms·
Computer architecture being what it is now, though, it has been observed recently that a lot of uses of linked lists are still faster with arrays/vectors, even
by jerf 12y ago
Computer architecture being what it is now, though, it has been observed recently that a lot of uses of linked lists are still faster with arrays/vectors, even if you do the "expensive" operations with them.
Point here not being "you're wrong", because you're still right in at least some cases, but that benchmarking can be called for if you're really choosing them for performance because the expense of cache misses and the way linked lists verge on the pathological case for cache misses (not quite, you do stand a chance the next element is in cache and possibly even the next element of RAM, but over time it's not a very good chance) means that arrays can win more often than you would naively think due to the fact linked lists take a rather staggeringly large constant factor nowadays, and it can take rather a lot of using their O(1) advantages to make up for it. This is totally a reachable bar, just, less than you might think.
http://www.codeproject.com/Articles/340797/Why-you-should-never-ever-EVER-use-linked-list-in http://www.codeproject.com/Articles/340797/Why-you-should-ne...
https://www.youtube.com/watch?v=YQs6IC-vgmo https://www.youtube.com/watch?v=YQs6IC-vgmo
(Note that for instance the second video computes a bit of a pathological case where you have to traverse to find where to insert. In some cases, you will for some reason or other already have that point in hand, which is one of the things that indicates linked lists may be useful; if you always have that case linked lists could still win. But the point should still be taken that vectors/arrays can be way faster than you'd think.)
Of course, if you're using a dynamic scripting language where everything's guaranteed boxed and there's no hope of keeping things local anyhow, well, you might as well take whatever makes the algorithms easier.