[Mono-dev] faster than hashtable?

[Konstantin Triger]

You may also consider using "bit dictionary algorythms":

Suppose your key is n bits long, you divide it to k levels each m bits (k*m
= n).

At each level you have 2^m arrays that point to the next level array etc,
while at last it will be an array of values. Provided the range of potential
keys is relatively dense this solution will not take too much memory, while
read access will be very fast since it's only several bit operations and
memory dereferences.

Kosta

On Wed, Oct 28, 2009 at 7:10 PM, Rafael Teixeira <monoman at gmail.com> wrote:

> As p/invokes cost a lot, another (fourth) option would be to
> reimplement judy arrays algorithm (which I admittedly know nearly
> nothing about) in managed code. From reading their 10 minutes intro, I
> guess some of the cache-fill optimizations it implements may be
> jeopardized by the JIT workings, but I guess it still may be helpful
> to implement and profile along the other options.
>
> Hope it helps,
>
> Rafael "Monoman" Teixeira
> ---------------------------------------
> "To be creative means to be in love with life. You can be creative
> only if you love life enough that you want to enhance its beauty, you
> want to bring a little more music to it, a little more poetry to it, a
> little more dance to it."
> Osho
>
>
>
> On Wed, Oct 28, 2009 at 2:30 PM, pablosantosluac at terra.es
> <pablosantosluac at terra.es> wrote:
> > Sure Alan!
> >
> > So, basically, the options are:
> >
> > - Use a sorted ArrayList and a binary search
> > - Reimplement hashtable focusing on long keys
> > - Write a wrapper to Judy
> >
> > Alan McGovern wrote:
> >> Really what you need to do is benchmark all of the different options
> >> using your expected workload. It's near useless us telling you X is
> >> faster or Y is better without knowing the workload involved.
> >>
> >> Alan.
> >>
> >> On Wed, Oct 28, 2009 at 2:40 PM, pablosantosluac at terra.es
> >> <mailto:pablosantosluac at terra.es> <pablosantosluac at terra.es
> >> <mailto:pablosantosluac at terra.es>> wrote:
> >>
> >>     Excellent. Is there a wrapper for C#? Is it worth?
> >>
> >>     Felipe Lessa wrote:
> >>     > On Tue, Oct 27, 2009 at 11:58:31PM +0100,
> >>     psantosl at codicesoftware.com <mailto:psantosl at codicesoftware.com>
> wrote:
> >>     >> If you need to store key/value pairs, where the key will be
> ALWAYS a
> >>     >> unique long (no collisions), is there anything better than a
> >>     Hashtable?
> >>     >
> >>     > There are always Judy arrays, see http://judy.sourceforge.net/.
> >>     >
> >>     > --
> >>     > Felipe.
> >>     > _______________________________________________
> >>     > Mono-devel-list mailing list
> >>     > Mono-devel-list at lists.ximian.com
> >>     <mailto:Mono-devel-list at lists.ximian.com>
> >>     > http://lists.ximian.com/mailman/listinfo/mono-devel-list
> >>     >
> >>     _______________________________________________
> >>     Mono-devel-list mailing list
> >>     Mono-devel-list at lists.ximian.com
> >>     <mailto:Mono-devel-list at lists.ximian.com>
> >>     http://lists.ximian.com/mailman/listinfo/mono-devel-list
> >>
> >>
> > _______________________________________________
> > Mono-devel-list mailing list
> > Mono-devel-list at lists.ximian.com
> > http://lists.ximian.com/mailman/listinfo/mono-devel-list
> >
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>



-- 
Regards,
Konstantin Triger
RSS: http://feeds.feedburner.com/ktriger
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ximian.com/pipermail/mono-devel-list/attachments/20091029/0c6d5e8c/attachment.html