On Mon, Dec 19, 2011 at 10:54 PM, Barry Smith <span dir="ltr"><<a href="mailto:bsmith@mcs.anl.gov">bsmith@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"><br>
<br>
On Dec 19, 2011, at 9:30 PM, Matthew Knepley wrote:<br>
<br>
> I looked at the new checkins for fast MatMatSym. It looks to me like you want a data<br>
> structure that has<br>
><br>
>   a) O(N) space, where N is the number of entries<br>
><br>
>   b) fast insert<br>
><br>
>   c) fast traversal<br>
><br>
> It seems like the best data structure of this is<br>
><br>
>    <a href="http://en.wikipedia.org/wiki/Y-fast_trie" target="_blank">http://en.wikipedia.org/wiki/Y-fast_trie</a><br>
<br>
</div>   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.<br>
<br>
   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.</blockquote>
<div><br></div><div>Okay, so you want fast Merge-wo-Duplicates and Traverse. To summarize</div><div><br></div><div>Option 1: What is currently there</div><div><br></div><div>  Merge-wo-Duplicates:</div><div><br></div><div>
    A Fortran-style linked list is used to hold the indices, a PetscBT (bitmap) is used to check for membership.</div><div><br></div><div>    The indices are pushed in one-by-one, checking the BT each time</div><div><br></div>
<div> Option 2: Brain dead</div><div><br></div><div>    Put values directly after current values and sort in place</div><div><br></div><div>  Option 3: Traditional</div><div><br></div><div>    Put values directly after and merge in place (std::inplace_merge)</div>
<div><br></div><div>Both 2 and 3 are not taking account of duplicates. I see at least three ways to do this:</div><div><br></div><div>  1) Use a PetscBT and ignore duplicates in the input array</div><div><br></div><div>  2) Use a PetscBT and squish duplicates out of the output array (prob too much data movement)</div>
<div><br></div><div>  3) Ignore duplicates on traversal. This would be fast, its just a question of the memory overhead</div><div><br></div><div>     Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class="HOEnZb"><font color="#888888"><br>
   Barry<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
><br>
> It has O(N) space, and O(log log M) where M is the maximum key size. It basically<br>
> uses prefix compression on the bitwise representation of the keys, so that runs of<br>
> consecutive integers are handled well.<br>
><br>
> So far, I cannot find any free implementations.<br>
><br>
>    Matt<br>
><br>
> --<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>
<br>
</div></div></blockquote></div><br><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>