Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > What to do if you've made a new high performance data structure?

Reply
Thread Tools

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

 
 
Theodore H. Smith
Guest
Posts: n/a
 
      04-20-2004
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/
 
Reply With Quote
 
 
 
 
Allan Bruce
Guest
Posts: n/a
 
      04-20-2004

"Theodore H. Smith" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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


 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      04-20-2004
Allan Bruce wrote:
> "Theodore H. Smith" <(E-Mail Removed)> 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)


 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      04-20-2004
http://www.velocityreviews.com/forums/(E-Mail Removed) (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;}
 
Reply With Quote
 
Theodore H. Smith
Guest
Posts: n/a
 
      04-21-2004
> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
High performance binary data Steve Python 3 08-10-2007 03:08 PM
Rebel XT, made in Japan, made in Thailand jazu Digital Photography 10 12-12-2006 05:11 AM
High Quality Feng Shui (Chinese Goodluck products) made available at your doorstep. Anil RS ASP .Net Web Controls 0 08-06-2004 12:43 PM
cmputer made high pitched beep continues on sotdown Diehard Computer Information 6 01-17-2004 03:13 AM
Compatibility-made paging reducesoverall performance. ME Computer Support 3 07-14-2003 07:06 PM



Advertisments