"meld" results look good (unless I made a mistake somewhere). I merged two collections, each with 2 million unique elements. did union of sorted sets, then did meld with my heap implementation:
============================ performing union of two sorted sets "Elapsed time: 18881.81 msecs" --------------------------------------------- making another heap performing meld of two heaps "Elapsed time: 0.146 msecs" ============================ checking in latest version of test. On Tue, Apr 21, 2009 at 2:10 AM, e <evier...@gmail.com> wrote: > I've done a little comparing to sorted-set as recommended. The following > test (in case there is anything bogus about it) is checked in with the java > project: > http://code.google.com/p/jc-pheap/source/browse/trunk/jc-pheap/src/persistent_heap/testing/test.clj?spec=svn8&r=8 > > deduping 2,000,000 nums > shuffling 1999019 nums > ========================================= > inserting into sorted set > "Elapsed time: 39375.887 msecs" > -------------------- > popping from front of sorted set > "Elapsed time: 15189.0 msecs" > ========================================= > heap insert > "Elapsed time: 15101.546 msecs" > ------------------ > heap pop > "Elapsed time: 59715.796 msecs" > ========================================= > > What I am finding consistently (again, unless the test is bogus) is pretty > much expected. *Overall* the excellently implemented sorted-set outperforms > the heap I'm working on if you add the all the "insert" times to all the the > "pop-front" times. > > That said, if you want fast inserts, and you're not even sure yet if people > want all the elements in sorted order, the heap has advantages ... > especially if you're not even planning on referencing elements in the middle > of the list (something I do hope to support in some fashion eventually, > note). It may also be the case that some smart java/algorithm people could > find opportunities to speed up my deleteMin().* > > a note on deduping:* > > One difference that doesn't seem to matter performance-wise much is that > sorted-set elements are unique. I'm not sure if clojure currently has a > data structure (other than considering the heap) that works like a sorted > multimap or sorted multiset. Would it be the same to sort a vector in > between inserts? That doesn't sound fast, but maybe I should have done that > test, too. > > So, anyway, for this test, I inserted unique elements into both structures > so one wouldn't have way more than the other when comparing things like > popping. I also sampled from a wide range of numbers, so I probably didn't > have to go to such lengths, as it turns out. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en -~----------~----~----~----~------~----~------~--~---
