What to do if you've made a new high performance data structure?

[Theodore H. Smith]

OK, so I've invented a new data structure, used for look up tables
(AKA "map" or "dictionary"), which is much faster, and uses less RAM,
than the popular hashing algorithms.

I've written a demonstration library, correctness test framework and
speed testing framework. I've written a comparison using the STL
ext/hash_map, and mine performs 1.57x as fast as that one, and uses
less RAM.

So, assuming someone did invent a new high performance data structure,
which could replace some existing well known data structures, what's
the process for going about letting people know of it?

How do I let the world know? Any answers from people in the know about
data structures for lookup tables, will be very much appreciated!

In case anyone is interested, the information and code is at
www.elfdata.com/dictionary/

[Allan Bruce]

"Theodore H. Smith" <de****@elfdata.com> wrote in message
news:e2**************************@posting.google.c om...

OK, so I've invented a new data structure, used for look up tables
(AKA "map" or "dictionary"), which is much faster, and uses less RAM,
than the popular hashing algorithms.

I've written a demonstration library, correctness test framework and
speed testing framework. I've written a comparison using the STL
ext/hash_map, and mine performs 1.57x as fast as that one, and uses
less RAM.

So, assuming someone did invent a new high performance data structure,
which could replace some existing well known data structures, what's
the process for going about letting people know of it?

How do I let the world know? Any answers from people in the know about
data structures for lookup tables, will be very much appreciated!

In case anyone is interested, the information and code is at
www.elfdata.com/dictionary/

Interesting work, but your claim about being 1.57x faster puzzles me. I
don't mean to put your method down, but the STL implementation you are using
may be a particularly slow one, for many reasons (e.g. security, threadsafe
etc.). I suggest you test your method on seeveral C++ complilers and OSs.
Also, how fair is your test? There are certain ways to make ones algorithm
perform better over another with certain examples. Of course, to come close
to the speed of the STL is good work, to beat it even better.
Out of interest, is your implementation threadsafe?
Allan

[CBFalconer]

Allan Bruce wrote:

"Theodore H. Smith" <de****@elfdata.com> wrote in message
.... snip ...

I've written a demonstration library, correctness test framework
and speed testing framework. I've written a comparison using the
STL ext/hash_map, and mine performs 1.57x as fast as that one,
and uses less RAM.

.... snip ...
Interesting work, but your claim about being 1.57x faster puzzles
me. I don't mean to put your method down, but the STL implementation

..... snip ....

The STL and C++ are OT on c.l.c. Here we tend to deal with the C
language.

--
Some useful references:
<http://www.ungerhu.com/jxh/clc.welcome.txt>
<http://www.eskimo.com/~scs/C-faq/top.html>
<http://benpfaff.org/writings/clc/off-topic.html>
<http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/> (C99)

[Ben Pfaff]

de****@elfdata.com (Theodore H. Smith) writes:

So, assuming someone did invent a new high performance data structure,
which could replace some existing well known data structures, what's
the process for going about letting people know of it?

How do I let the world know? Any answers from people in the know about
data structures for lookup tables, will be very much appreciated!

You write a paper for a journal or a conference and submit it for
review. If you're not interested in writing for a reviewed
publication, then you write an article and publish it in a
magazine or on your webpage.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Theodore H. Smith]

> Interesting work, but your claim about being 1.57x faster puzzles me. I

don't mean to put your method down, but the STL implementation you are using
may be a particularly slow one, for many reasons (e.g. security, threadsafe
etc.). I suggest you test your method on seeveral C++ complilers and OSs.
Also, how fair is your test? There are certain ways to make ones algorithm
perform better over another with certain examples. Of course, to come close
to the speed of the STL is good work, to beat it even better.
Out of interest, is your implementation threadsafe?
Allan

To the best of my knowledge (which does increase over time, so I may
later realise it's more unfair than I thought), the only "unfairness"
is that the keys are read in order, which my algorithm is better
suited to. I didn't realise this at the time of writing my code, and
will correct my tests for the next release, by making them either
random, or using a more real-world test.

My implementation is not thread safe. If someone wants that, there is
a feature request section on my website!
(http://www.elfdata.com/dictionary/) Otherwise, a wrapper is
necessary.

I've tested several compilers, and testing several OSs I'll be able to
do after I figured out how to use SourceForge's compile farm!! It's
very confusing, what with it's ssh keys and that.