Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Re: Linked lists as arrays: inserting values

by Tanktalus (Canon)
on Sep 25, 2006 at 15:43 UTC ( #574759=note: print w/replies, xml ) Need Help??

in reply to Linked lists as arrays: inserting values

Well, it seems that even you quote says "almost always" - perhaps you've found one of the places that make it "almost always" rather than just "always".

That said, as far as I'm aware, perl data is mostly a small struct of pointers, so copying them around is probably not that expensive - O(n) based on the number of items that need to be copied around instead of O(nm) where m is related to the length of the strings, or the contents of whatever they may refer to (hash refs, array refs, objects, etc.). So it may not really be that bad to use splice.

The flip side is that by using perl arrays for your data instead of linked lists, perl handles all the details for you. Not that linked lists are necessarily hard or anything, but any time you introduce any type of complexity, you increase the possibility for bugs. By their nature, programs are complex, so we can't avoid that risk. However, we can avoid risk in areas with insignificant gains.

That, of course, begs us to ask: what gains? And thus, I challenge you to benchmark it to prove that there are gains to be had with another method, and to prove that those gains are of significance in your application.

My guess is that you'll need a package full of code to abstract the list away to keep the rest of your code simple. And that will eat away at significant portions of your speed gains. And then, if you ever want to hand your list to some standard function, you're going to have to convert it back to a list anyway, and there goes all the rest of your gains.

That's just a guess, though. ;->

  • Comment on Re: Linked lists as arrays: inserting values

Replies are listed 'Best First'.
Re^2: Linked lists as arrays: inserting values
by tilly (Archbishop) on Sep 26, 2006 at 04:33 UTC
    Absolutely the correct answer.

    Building a large data set by repeatedly splicing into the middle is indeed O(n*n) while a linked list is O(n). But that is O(n*n) with a small constant term versus O(n) with a big term. Unless your dataset is very large, the native array approach will be far faster. Just consider the cost of accessing the next element. With the native approach it will be a pointer lookup versus having to make a function call (and Perl function calls are slow).

    Furthermore a final reason not to use linked lists in Perl. Unless you are very careful, the linked lists will have circular data structures (each item points to the next which points to the previous). Therefore you are either in the business of having to do memory management yourself, or else you need to add yet another layer of slow indirection. Either way you've added more complexity, more room for bugs, and have reduced your potential performance gains even more.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://574759]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2018-06-21 03:24 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (117 votes). Check out past polls.