On Mon, Dec 19, 2011 at 10:54 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:
> > > On Dec 19, 2011, at 9:30 PM, Matthew Knepley 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 > > Wikipedia sucks for all sort/search algorithms; there is no > discussion/mention of what happens with duplicate keys at all. We have > many many duplicates that must be eliminated. > > Note that the result is always generated as the merging of "a bunch of > sorted lists", thus an algorithm that takes advantage of the sorted nature > seems advantages. I tried a heap based scheme but that ended up being > useless because of the duplicate issue. Okay, so you want fast Merge-wo-Duplicates and Traverse. To summarize Option 1: What is currently there Merge-wo-Duplicates: A Fortran-style linked list is used to hold the indices, a PetscBT (bitmap) is used to check for membership. The indices are pushed in one-by-one, checking the BT each time Option 2: Brain dead Put values directly after current values and sort in place Option 3: Traditional Put values directly after and merge in place (std::inplace_merge) Both 2 and 3 are not taking account of duplicates. I see at least three ways to do this: 1) Use a PetscBT and ignore duplicates in the input array 2) Use a PetscBT and squish duplicates out of the output array (prob too much data movement) 3) Ignore duplicates on traversal. This would be fast, its just a question of the memory overhead Matt > > Barry > > > > > 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 > > -- 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/20111220/55545567/attachment.html>