Re: A (psossibly) fast, novel search table technique

On Thu, 22 Mar 2007 13:54:30 -0700, Ben Pfaff <blp@xxxxxxxxxxxxxxx>
wrote:

cri@xxxxxxxx (Richard Harter) writes:

[new data structure for table]
I didn't go into details at the time and no one followed up on
the thought. It turns out that there is an interesting data
structure involved, one that I am not familiar with. Let me
generalize a wee bit.

It's interesting. I'd like to see empirical analysis of this
technique (in terms of time and space cost) for an
implementation, with comparison against a hash table
implementation.

I put together an implementation and have done a few tests but I'm a
ways from anything definitive. Preliminary results suggest that, yes,
it's faster than hash tables for searches. In the data sets I tested it
took longer to hash a string than it did to search for it. There are
quite a few caveats. The code is a first implementation and can
probably be tweaked. The testing data sets are mostly source code and
concatenated collections of HTML files so there isn't a large spread of
record sizes. Also I haven't instrumented the insert code; it will be
slower than a search but shouldn't be slower by much.

More later.



.

Relevant Pages

  • Re: Hashes are good, but not good enough.
    ... PJH> the case where a hash is the appropriate data structure. ... RAM (but note that many databases also use hash-based indexes, so hashes ...
    (comp.lang.perl.misc)
  • Re: combining hashes
    ... >>> A hash is an ordered data structure indexed by a specific key. ... My mind's eye sees it differently. ... c> An array is ...
    (comp.lang.perl.misc)
  • Re: I am needing a gentle introduction to accessing a perl array from a reference
    ... The data structure here is nothing more than a flat array. ... There is no hash anywhere in your code up at the top... ... Returns a list consisting of all the keys of the named hash. ... We need an understanding of the data structure if we are ...
    (comp.lang.perl.misc)
  • Re: Hash order bug?
    ... a review of one's Data Structures course may be in order ... did I realize that the underlying data structure is a hash, ... If you need to iterate through a hash in order by key, ...
    (comp.lang.ruby)
  • Re: use SDBM_File - Cant use string as a HASH ref
    ... I'm trying to tie this kind of hash into SDBM ... DBM files can only store simple values like strings and numbers. ... serialize the data structure as a string before storing it in the DBM, ... there were 100 perfect squares ...
    (perl.beginners)