a functional/persistent priority queue
Hi, In case anyone is interested in participating or consuming -- for use with clojure or otherwise: Suggestions and requests are welcome: http://code.google.com/p/jc-pheap/ Summary (besides what's at the link): If only as an exercise, I've spent a little time coding up (in java right now) a paper by Brodal and Okasaki (origially found by googling) on a functional priority queue ( http://code.google.com/p/jc-pheap/source/browse/trunk/jc-pheap/src/persistent_heap/brodal_priority.pdf) with optimal worst-case runtimes. I think one thing I will do pretty soon is compare this approach (performance and memory) to just handing out copies of arrays to consumers (or some other imperative approach), but the idea/interface could be useful even then. The implementation under the hood would just change. I think this could end up being a good chance for me to start learning macros, too, to make use in clojure easy. Another thing that seems important is to try to figure out how to add decreaseKey() in a functional setting. Also, something I'm wondering about is how heaps fit into a lazy environment. I think of it as semi-lazy because some of the sorting work is delayed until values are needed (popped off the top), but it's not really like a typical stream processor/filter where only one or two elements need to be in memory at once. Finally, for fun, I'm in the middle of playing with the data-structural bootstrapping part of the paper (that code isn't checked in yet), but it's usefulness will depend on how important meld is to people (meld seems fast enough right now, maybe). --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: a functional/persistent priority queue
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 -~--~~~~--~~--~--~---
Re: a functional/persistent priority queue
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.comwrote: 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 -~--~~~~--~~--~--~---
Re: a functional/persistent priority queue
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.comwrote: 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 -~--~~~~--~~--~--~---
Re: a functional/persistent priority queue
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. for completeness, I forgot about QuickSelect if *all* you want is the top K, and especially in an imperative setting: http://www.scribd.com/doc/4954930/Advanced-Topics-in-Sorting so I guess another part of the use case might be that different consumers want to get a potentially different top-K. So once a single heapification occurs, each consumer can have their own view and pop in O(k log(n)) time, for whatever k they want, reusing most of a shared data structure. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
