[petsc-dev] LLCondensed work

[Matthew Knepley]

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>