Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: (corrections) Re: Answer: Efficient access to sparse lists?

by Improv (Pilgrim)
on Jan 26, 2001 at 01:45 UTC ( [id://54372]=note: print w/replies, xml ) Need Help??


in reply to (corrections) Re: Answer: Efficient access to sparse lists?
in thread Efficient access to sparse lists?

The problem is that I need fast *ordered* access, something that a hash really won't help me with.

Replies are listed 'Best First'.
(tye)Re: Efficient access to sparse lists?
by tye (Sage) on Jan 26, 2001 at 02:22 UTC

    Ah, now I finally understand what you want. (:

    You need a more complex data structure. You can wrap a nice interface around it if you like, but I'll leave that part up to you (or others).

    I think you've found a reason to implement a linked list in Perl (normally you don't need such things in Perl). I went with a circular, doubly-linked list for ease of implementation (where "turn 0" is a dummy turn used to find the first and last turns):

    my %turn= ( 0=>{Next=>5,Prev=>53}, 5=>{Turn=>"turn 0",Prev=>0,Next=>28}, 28=>{Turn=>"turn 28",Prev=>5,Next=>53}, 53=>{Turn=>"turn 53",Prev=>28,Next=>0}, ); sub pushTurn { my( $num, $turn )= @_; my $last= $turn{0}{Prev}; $turn{$num}= {Turn=>$turn,Prev=>$last,Next=>0}; $turn{0}{Prev}= $num; $turn{$last}{Next}= $num; } sub deleTurn { my( $num )= @_; my( $prev, $next )= @{ $turn{$num} }{qw( Prev Next )}; $turn{$prev}{Next}= $next; $turn{$next}{Prev}= $prev; delete $turn{$num}; }

    I hope that is close enough to correct that you can get an implementation working. {-:

    Use:

    my %turn= ( 0=>{Next=>0,Prev=>0} );
    to bootstrap the data structure.

            - tye (but my friends call me "Tye")
Re: Re: (corrections) Re: Answer: Efficient access to sparse lists?
by BoredByPolitics (Scribe) on Jan 26, 2001 at 06:08 UTC
    Have you considered a linked list in a hash?

    Update: Apologies for the redundant post - I hadn't discovered the notes depth setting until a few moments ago, so hadn't noticed tye's post.

    Pete

Re (tilly) 2: (corrections) Re: Answer: Efficient access to sparse lists?
by tilly (Archbishop) on Jan 26, 2001 at 06:56 UTC
    What you are talking about sounds like what a BTree is for. You can get it done in Perl, use DB_File (or the next generation and possibly immature BerkeleyDB) to get it in C.

    If you go with the latter two options watch out for the need to set a sort order. You will run into that will the all-Perl solution as well, but there you can modify the module to work that way...

      FYI, since this problem does not require sorted inserts into the middle of the list, a BTree is overkill. A hashed linked list is hugely simpler and probably faster for most operations.

              - tye (but my friends call me "Tye")
        I am not convinced that the problem does not require inserts in sorted position. Whether or not that was envisioned was not said, but my address books have names added randomly, and I expect them back in order. A BTree is definitely the right structure for that expectation.

        I would have to bench both ways for speed, but to get the full functionality that a BTree offers (most of which is very well suited to address books) with hand-rolled Perl will wind up being more complex than loading a widely used and well-optimized standard library.

        Sure, a linked list is easier to roll by hand. But it is easier still to not roll by hand at all...

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://54372]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (4)
As of 2024-03-29 12:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found