On Mon, Dec 19, 2011 at 9:34 PM, Jed Brown <jedbrown at mcs.anl.gov> wrote:
> On Mon, Dec 19, 2011 at 19:30, Matthew Knepley <knepley at gmail.com> wrote: > >> I looked at the new checkins for fast MatMatSym. It looks to me like you >> want a data >> structure that has >> >> a) O(N) space, where N is the number of entries >> >> b) fast insert >> >> c) fast traversal >> >> It seems like the best data structure of this is >> >> http://en.wikipedia.org/wiki/Y-fast_trie >> >> It has O(N) space, and O(log log M) where M is the maximum key size. It >> basically >> uses prefix compression on the bitwise representation of the keys, so >> that runs of >> consecutive integers are handled well. >> >> So far, I cannot find any free implementations. >> > > Do you have a reference showing that the constants are decent? > There are some in the article. I have used other tries which had very favorable constants compared to balanced binary. Matt -- What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead. -- Norbert Wiener -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111219/5786fd2a/attachment.html>
