snape has asked for the wisdom of the Perl Monks concerning the following question:

Would it be advisable to code data structures in Perl ? I am not talking about the hashes or arrays or may be hash of array etc (although they are known as data types in perl). I would like to know the view point of people using advanced data structures like matrices/ unbalaced or balanced trees (AVL, red black etc) / graphs ? and how often it is used or do you think C is better as it is faster than perl ?

Thanks.

Replies are listed 'Best First'.
Re: Perl Data Structures
by BrowserUk (Patriarch) on Sep 30, 2010 at 22:57 UTC

    The main problem with coding things like trees in Perl, is not (so much), performance, but memory usage.

    In C, a simple RB-tree node might require 20 (64-bit:40) bytes of ram. Doing the same in terms of Perl's built-in data structures will consume anything from 336 to 512 bytes. (64-bit Perl).

    That order of magnitude increase in memory usage severally limits the size of tree you can deal with, even before you get to the performance aspect.

    And anything you do to lessen the memory usage is a further direct hit on performance.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re: Perl Data Structures
by graff (Chancellor) on Oct 01, 2010 at 01:06 UTC
    do you think C is better as it is faster than perl ?

    If faster execution and/or smaller memory footprint are crucially important factors, then C is better. If reducing the amount of programmer time involved in creating, debugging, maintaining and extending code is more important, then Perl is better.

[reply]
Re: Perl Data Structures
by JavaFan (Canon) on Oct 01, 2010 at 10:57 UTC
    do you think C is better as it is faster than perl ?
    If you think C is better because it's faster, why would you write anything in Perl? It's not just when you're coding trees that C is faster.

    I'd say that you see little use of balanced trees in Perl because most problems tackled by Perl programmers don't need to be solved with a balanced tree. And if they do - they're just using a database.

[reply]
Re: Perl Data Structures
by blakew (Monk) on Oct 01, 2010 at 22:23 UTC
    Generally you'll be advised against it, however there are options on CPAN that attest to most things covered in your list. Heap::Simple is a slim and fast priority queue and other structures may fit other niches (ex. Tree::R, Graph). There's also of course PDL for vector programming. Lots of modules dealing with HTML and interchange formats (XML, etc.) implement trees internally. You have looked?

    For general purpose though, no, basically use arrays for positional indexing and hashes for name-based indexing; map, grep and subs to operate on them (in place of classical ADT's) and classes (Moose) when you "need to go deeper."

[reply]

Back to Seekers of Perl Wisdom