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

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...

  • Comment on Re (tilly) 2: (corrections) Re: Answer: Efficient access to sparse lists?

Replies are listed 'Best First'.
(tye)Re2: (corrections) Re: Answer: Efficient access to sparse lists?
by tye (Sage) on Jan 30, 2001 at 21:11 UTC

    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")
[reply]
      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...

[reply]

        Uh, tilly, wrong thread. This thread is talking about a turn-based game, not an address book.

                - tye (but my friends call me "Tye")
[reply]

In Section Seekers of Perl Wisdom