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

Discussion in 'C Programming' started by Theodore H. Smith, Apr 20, 2004.

  1. 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/
    Theodore H. Smith, Apr 20, 2004
    #1
    1. Advertising

  2. Theodore H. Smith

    Allan Bruce Guest

    "Theodore H. Smith" <> wrote in message
    news:...
    > 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
    Allan Bruce, Apr 20, 2004
    #2
    1. Advertising

  3. Theodore H. Smith

    CBFalconer Guest

    Allan Bruce wrote:
    > "Theodore H. Smith" <> 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)
    CBFalconer, Apr 20, 2004
    #3
  4. Theodore H. Smith

    Ben Pfaff Guest

    Re: What to do if you've made a new high performance datastructure?

    (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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \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\
    );}return 0;}
    Ben Pfaff, Apr 20, 2004
    #4
  5. > 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.
    Theodore H. Smith, Apr 21, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rui Pacheco

    High performance file creation

    Rui Pacheco, Nov 11, 2003, in forum: Java
    Replies:
    2
    Views:
    352
    Michael Borgwardt
    Nov 11, 2003
  2. christopher diggins
    Replies:
    31
    Views:
    994
    Mark A. Gibbs
    Apr 9, 2004
  3. Steve

    High performance binary data

    Steve, Aug 10, 2007, in forum: Python
    Replies:
    3
    Views:
    461
    sturlamolden
    Aug 10, 2007
  4. Anil RS
    Replies:
    0
    Views:
    122
    Anil RS
    Aug 6, 2004
  5. Replies:
    1
    Views:
    197
    Simon Cropper
    Jul 31, 2012
Loading...

Share This Page