On Mon, Dec 19, 2011 at 9:34 PM, Jed Brown <span dir="ltr"><<a href="mailto:jedbrown@mcs.anl.gov">jedbrown@mcs.anl.gov</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im"><div class="gmail_quote">On Mon, Dec 19, 2011 at 19:30, Matthew Knepley <span dir="ltr"><<a href="mailto:knepley@gmail.com" target="_blank">knepley@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div>I looked at the new checkins for fast MatMatSym. It looks to me like you want a data<div>structure that has</div><div><br></div><div>  a) O(N) space, where N is the number of entries</div><div><br></div><div>
  b) fast insert</div>
<div><br></div><div>  c) fast traversal</div><div><br></div><div>It seems like the best data structure of this is</div><div><br></div><div>   <a href="http://en.wikipedia.org/wiki/Y-fast_trie" target="_blank">http://en.wikipedia.org/wiki/Y-fast_trie</a></div>


<div><br></div><div>It has O(N) space, and O(log log M) where M is the maximum key size. It basically</div><div>uses prefix compression on the bitwise representation of the keys, so that runs of</div><div>consecutive integers are handled well.</div>


<div><br></div><div>So far, I cannot find any free implementations.</div></div></blockquote></div><br></div><div>Do you have a reference showing that the constants are decent?</div>
</blockquote></div><br>There are some in the article. I have used other tries which had very favorable<div>constants compared to balanced binary.</div><div><br></div><div>   Matt<br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener<br>
</div>