my understanding of a suggestion in the chat room was to add a separate slot for an object associated with a priority rather than having comparable objects inserted.
That is, the priority of something is not the something. It's just its priority. I need to play around a lot more with this to make these recent operations make sense. It could even make sense to use clojure's hashmap to hook objects to their places in the heap. If the Hashmap insert speeds are minuscule in comparison to the Heap insert speeds, then we could even end up with something I've now learned is called a Priority Search Queue. It's like a sorted map but explicitly lists heap operations and search/assoc like things . If internally using a Clojure Hashmap + the new Heap is faster than the SortedMap, and does all the stuff, and more, I'll let yuz know. On Sat, Apr 25, 2009 at 5:46 PM, e <evier...@gmail.com> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
