Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Traditional Linked List and Perl's built-in Data Structure

by monkfan (Curate)
on Dec 15, 2005 at 14:01 UTC ( #516959=perlquestion: print w/ replies, xml ) Need Help??
monkfan has asked for the wisdom of the Perl Monks concerning the following question:

But again, Perl's built-in are virtually always good enough. -perldoc -q linked
There are things you can do more efficiently with linked lists than with Perl arrays. -Abigail
I just bumped with Abigail`s comment above. I wonder on what case that actually may happen?

Regards,
Edward

Comment on Traditional Linked List and Perl's built-in Data Structure
Re: Traditional Linked List and Perl's built-in Data Structure
by blazar (Canon) on Dec 15, 2005 at 14:10 UTC
    I don't know what Abigail exactly meant, but in any case perl's arrays just like most any other Perl's data type have a whole pile o' magic built in them, and are designed to be (as) good (as possible) dwimmery-wise, so they may be suboptimal in other respects, e.g. memory use, etc.
Re: Traditional Linked List and Perl's built-in Data Structure
by salva (Monsignor) on Dec 15, 2005 at 14:19 UTC
    as in any language, inserting and deleting elements on the middle of big arrays is an expensive operation: O(N), while on linked lists, you can do it on O(1).
Re: Traditional Linked List and Perl's built-in Data Structure
by BrowserUk (Pope) on Dec 15, 2005 at 14:33 UTC

    Basically, almost any tree structure or graph, will use less memory and have faster traversal times, if implemented in C using direct pointer access and manipulations, than when the same structures are built using Perl's references.

    As fast as Perl's hashes and arrays are, you do pay some costs for their generality and ease of use. Indirecting through a reference costs more than indirecting through a raw address, and raw C-style arrays use considerably less memory than the equivalent Perl arrays.

    However, for those costs, you get a whole slew of benefits:

    • Automated memory management. (No alloc/free to contend with).
    • Automated expansion/contraction. (No realloc/memcpy et al).
    • Autovivication. (No need to predeclare the size of your arrays).
    • Tranparent manipulation, coersion and mixing of strings, integers and reals.
    • Automated pointer management. It's (almost) impossible to segfault Perl unlike C.
    • Programmer productivity.

    For anything other than the most demanding of applications that need extremely fast response times, or to manipulate huge amounts of memory, the gains far outweight the costs. And even when you do need to manipulate large volumes of data, a little extra effort can sometimes allow you to accomodate upto an order of magnitude more data in the same amount of ram, whilst still avoiding the need to leave the convenience of Perl and get down and dirty with C.

    That said, a well thought out set of tree primitives written in XS, available in Perl would be a nice addition.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

    Edited by planetscape - added <ul></ul> tags

      That said, a well thought out set of tree primitives written in XS, available in Perl would be a nice addition.
      Has there been any consideration of adding some new intrinsic data structure types to perl6, like linked lists, or binary / n-ary / red-black / balanced / whatever trees, etc?

        I don't know. That might make a good question for the P6 mailling list.

        If method call overheads are substantially lower, and if the early proposal that it would be possible to specify (or advise) the storage size for array elements, (something like my @array :integer; from memory), then it may be unnecessary, as it may be possible to create a P6 class or mixin for trees, graphs, etc. that would be fast and efficient. I guess it will depend upon how successful Parrot is in keeping the levels of indirection down.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Traditional Linked List and Perl's built-in Data Structure
by planetscape (Canon) on Dec 15, 2005 at 17:14 UTC

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (15)
As of 2014-09-16 13:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (22 votes), past polls