[petsc-dev] LLCondensed work

[Matthew Knepley]

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.

   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/4df3e15e/attachment.html>