Re: [boost] Boost container similar to Judy arrays?

Subject: Re: [boost] Boost container similar to Judy arrays?
From: Stewart, Robert (Robert.Stewart_at_[hidden])
Date: 2010-09-14 12:53:42

Christopher Jefferson wrote:
> On 7 Oct 2009, at 14:36, Achilleas Margaritis wrote:
>
> > Does boost have a container with similar properties to Judy
> > arrays? I searched the documentation but I did not find
> > anything similar.

I know of nothing like it in Boost.

> > Here is the Judy arrays home page:
> >
> > http://judy.sourceforge.net/index.html
>
> It is hard to find from a quick read. How is a Judy array
> different to using a std::map, with int as the indexing type?

http://judy.sourceforge.net/doc/10minutes.htm is a better link to follow.

According to that page:

"Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:

    * Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API).
    * Judy is designed to avoid cache-line fills wherever possible. (This is the main design criteria for Judy.)
    * A b-tree requires a search of each node (branch), resulting in more cache-line fills.
    * A binary-tree has many more levels (about 8X), resulting in more cache-line fills.
    * A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.
    * An "expanse"-based digital tree (of which Judy is a variation) never needs balancing as it grows.
    * A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression."

The API is simple; the complexity, which sounds substantial, hides behind it.  The data structure is highly adaptive to the data stored within it just based upon its design, or so it sounds.

_____
Rob Stewart                           robert.stewart_at_[hidden]
Software Engineer, Core Software      using std::disclaimer;
Susquehanna International Group, LLP  http://www.sig.com

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.