Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Array VS Linked List

by asset (Novice)
on Nov 16, 2007 at 17:15 UTC ( #651271=perlquestion: print w/ replies, xml ) Need Help??
asset has asked for the wisdom of the Perl Monks concerning the following question:

Hey folks. After reading previous posts on the topic of using linked lists in Perl, Ive come to the conclusion that the general concensus is that in Perl you will almost never need to use a linked list as push,pop,splice,etc on arrays provides the same functionality.

In my scenario Im putting together a non-blocking shell on Win32 and I want the lowest possible CPU usage I can get. I have the shell functional using an Array as the input storage mechanism, yet I'm questioning the potential resource savings I would get (in Perl) by using a linked list instead. The main reason Im questioning this is that the same code to handle the input string will also be used to perform simple editing of text documents within the same program.

So lets say I need to use as little CPU as possible, and I need to manipulate a block of text from anywhere within that block of text.

Now for my question.

Would you use a linked list instead, and would there be any modules out there that you would use instead of brewing it up from scratch?

Comment on Array VS Linked List
Re: Array VS Linked List
by dragonchild (Archbishop) on Nov 16, 2007 at 17:20 UTC
    Your question makes very little sense to me. Why? Because a Perl array is a linked list. It's not "like" a linked list. It's not "mostly" a linked list. There is no difference.

    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
      Is there then a way, when handed only one element of an array, to obtain the next or previous element?
        Given that this is (almost always) an optimization for providing the tools to properly traverse said list, it's not necessary. And, linked lists only point in one direction. Doubly-linked lists point in both.

        The point of a linked list is to provide O(1) add and remove operations anywhere in the list, given certain assumptions. If you can do that with a Perl array (which you can), then it satisfies all the reasons why a linked list exists. The implementation of meeting those criteria is ... irrelevant.

        Linked lists are, in many ways, inferior to Perl's arrays. You cannot do random access into a linked list, but you can into a Perl array.


        My criteria for good software:
        1. Does it work?
        2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

      Erm, no a perl AV (the underlying C data type underneath an @array) is a pointer to a C array of SV* (pointers to the underlying C scalar value type). You can't trim elements out from the middle without shifting the successors down, nor prepend an element without shifting things up; you can append (i.e. push) items onto it but this may trigger a realloc of the C array of SV*s (likewise prepending may need to do this as well; but there may be an optimization for that). See the (slightly long in the tooth) relevant section of Perlguts Illustrated for more details.

      Now having said that, for most of what you'd use a linked list for in another language yes arrays are the appropriate data structure. And if you really need a true linked list it's trivial to whip one up.

      Update: And just to clarify a bit when I say you can't trim things out of the middle I'm talking about the underlying C operations that are taking place. Of course when you use splice it "Just Works™" and the representation of the array looks as if you've just removed the element(s) out from the middle; but underneath it all there's some shifting around being done that's going to be more overhead than would be if a true LL was being used under the hood.

        Thanks Fletch, I'm going to comp performance between using an array and a linked list. BTW, to dragonchild, an example of what I want to avoid is the added CPU usage when inserting characters into the middle of the array. Lets say my user decides to paste a block of text into the middle of the document. The bigger the array is the more CPU it uses to do so. Right now I'm seeing significant (to me) CPU usage when this occurs, and since my intent for this project is to be entirely non-blocking, I figure I may as well do everything I can to drop any unecessary CPU usage. From what I'm seeing, I certainly have to question your statement about a perl array being a linked list, as it certainly doesnt perform like one.
        The point was that, from within Perl itself (and not dipping into XS), the array is the best data structure for handling the needs of a linked list. Yeah, you could create a hashref for each node and put in references to the next element. But, I would be shocked and appalled if doing that was faster than the corresponding array implementation.

        The only benefit I can see is if you are translating algorithms directly from C (or a similar language) and want to have functions that you can pass nodes and it can call $node->next or $node->prev. But, translating functions to take $arr and $idx instead and $node->next translates to $arr->[$idx+1] is probably saner.


        My criteria for good software:
        1. Does it work?
        2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Array VS Linked List
by amarquis (Curate) on Nov 16, 2007 at 17:52 UTC

    On the question of which is faster: I can only assume that a "for real" linked list implementation would be faster, since your application will be insert/delete heavy. But, it is very trivial to make up a linked list in Perl, so the best course of action, if CPU cycles are that precious, would be to implement both and benchmark the suckers.

Re: Array VS Linked List
by ysth (Canon) on Nov 16, 2007 at 18:17 UTC
    What is this a list *of*? Lines? Characters?
Re: Array VS Linked List
by jdporter (Canon) on Nov 16, 2007 at 21:51 UTC
Re: Array VS Linked List
by tilly (Archbishop) on Nov 17, 2007 at 02:41 UTC
    The overhead of the method calls in a linked list implementation will kill any theoretical performance improvement unless you really, really are splicing in the middle of long lists very, very often.

    If you really want to implement a linked list, go ahead. At the bottom of tilly's scratchpad there is an implementation of a doubly linked list in Perl that avoids accidentally creating circular references and leaking memory. It is available.

    But I can guarantee you that it is the wrong approach to take for almost all possible programs that you might want to write.

Re: Array VS Linked List
by sundialsvc4 (Monsignor) on Nov 19, 2007 at 18:36 UTC

    A Perl array is a list, and a Perl hash is (unless "tied") a hash-table. All very-cleverly implemented for you by some very-clever people, long ago.

    Dictum Ne Agas:   Do Not Do A Thing Already Done.

    Focus on your problem:   the “what,” not the “how.”

    Do not be overly concerned about the poor ol' CPU, because... “at hundreds of millions of operations per second, no one can hear you scream.” Just make sure that your algorithm is efficiently and sensibly designed, and leverage existing platforms (like Perl itself, and CPAN) to the greatest possible extent.

    Don't "diddle" code to make it faster:   Choose a better algorithm.

Re: Array VS Linked List
by Anonymous Monk on Nov 20, 2007 at 07:46 UTC
    IF you are already willing to take the performance hit of using perl, then there is usually very little point doing linked lists in perl.

    Once you have decided to "pay" the price of perl, you get perl arrays, hashes etc included, which tend to map to real world structures and problems more conveniently (to the programmer) than "classical" linked lists (which are more convenient to the computer).

    It's like buying a truck and trying to use it to do something non-truckish - e.g. pull wheelies. While that may be possible don't be surprised if you get strange looks, or people don't think it's for a serious purpose.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://651271]
Front-paged by andyford
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2014-07-12 07:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (238 votes), past polls