new operations available for heap: http://code.google.com/p/jc-pheap/source/list
changeVal <---- any value inside the heap, not just the min. honor system. if you didn't put a value in, don't lie and changes its value. runtime varies from O(1) to O(logn). code has explanation. was ambitious and went for 'changeVal()' so values can go *up*, *in addition* to decreasing. lazyDelete <---- tries to put off work by usually being O(1). also relies on honor system. notes available on when amortization breaks down in functional setting eagerDelete <---- tries to do as much garbage collection as possible, so is always at least O(logn). More if lazy stuff has bubbled to top of heap. On Thu, Apr 23, 2009 at 8:19 PM, e <evier...@gmail.com> wrote: > "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 -~----------~----~----~----~------~----~------~--~---
