oh, but there's one other little point, which is that sets typically store unique values where that requirement is lifted from heaps.
On Sun, Apr 19, 2009 at 1:52 PM, e <evier...@gmail.com> wrote: > thank you for the idea. > > Here's how I extrapolate in terms of doing comparisons/experimentation: > > If sorted-set does the sort in advance, then this would be a way to delay > some of that work, but if my implementation is too terrible, then there's a > chance that the sorted-set is more practical. That is, perhaps a sorted-set > is able to do a complete sort in the same time (or less) that it takes the > heap to just insert the elements. The first is, of course O(log(n)) (unless > it uses more than one processor), and the latter in this structure is O(n), > but maybe the constant is way too high. > > But here would be an interesting situation: what if all the Heap inserts > do end up being faster, but popping every element off is slower because > deleteMin()'s constant is so high? Well, then there's a cross-over point > that would be nice to know about. It might be better to use the heap, when > you only want, say, the top K things, but if you want the top K+1 things, > than it's cheaper to just sort them all. > > Lastly, if a heap were found that trumps sorted-set construction when > adding both insert time and the time to pop all elements, then it could make > sense to implement sorted-set using a heap because of it's semi-laziness. > Of course, things are seldom that simple. It could be the case that one > data structure is better for some size problems and on some machines than > the other, in which case both have their use. > > > On Sun, Apr 19, 2009 at 1:34 PM, Mark Engelberg > <mark.engelb...@gmail.com>wrote: > >> >> I'm curious to know how this approach compares to using Clojure's >> sorted sets or hash tables. >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
