Re: heaps in clojure vs SML

Criterium automates the JVM warmup process. On Sunday, February 1, 2015 at 1:16:37 PM UTC-6, Ashton Kemerling wrote: > > Also remember to give the JVM some warm up time, as the JVM depends > heavily on JIT style optimizations, and measuring performance without it > might not represent real world

Re: heaps in clojure vs SML

I published my heap implementation on github: https://github.com/maruks/clj-data It has reasonable performance. I used it for https://www.hackerrank.com/challenges/messy-medians [org.clojars.maruks/maruks.data "0.0.1"] On Sun, Feb 1, 2015 at 7:16 PM, Ashton Kemerling wrote: > Also rem

Re: heaps in clojure vs SML

Also remember to give the JVM some warm up time, as the JVM depends heavily on JIT style optimizations, and measuring performance without it might not represent real world behavior, -- Ashton On Saturday, January 31, 2015 at 11:39:05 PM UTC-7, Mars0i wrote: > > You also might want to use Criter

Re: heaps in clojure vs SML

You also might want to use Criterium rather than *time *for accurate benchmarking*.* On Friday, January 30, 2015 at 6:54:52 AM UTC-6, Maris wrote: > > > yes, it helped :-) > > type hints make non-trivial difference > > thank you > > On Friday, 30

Re: heaps in clojure vs SML

yes, it helped :-) type hints make non-trivial difference thank you On Friday, 30 January 2015 12:43:40 UTC, Nicola Mometto wrote: > > > If you set! *warn-on-reflection* to true, you'd see a lot of reflection > warnings from your code. > > Type-hinting the code like this: http://sprun

Re: heaps in clojure vs SML

If you set! *warn-on-reflection* to true, you'd see a lot of reflection warnings from your code. Type-hinting the code like this: http://sprunge.us/ATiV makes your example execute in 120ms on my machine. Maris writes: > I implemented leftist heap (from Purely Functional Data Structures book) >

heaps in clojure vs SML

I implemented leftist heap (from Purely Functional Data Structures book) in clojure. https://gist.github.com/maruks/135fef92455578b61de2 It takes 32 seconds to insert 10 elements in heap: (time (peek (reduce conj (empty-heap) (range 1000 2000 100) ))) "Elapsed time: 32649.

Re: heaps in clojure

That heap-sort example is not really lazy. The java.util.concurrent.PriorityBlockingQueue essentially sorts the whole thing, and then the heap-sort is just making a lazy seq over that. Also, note that the "speed test" at that link is only working with lists of 1000, and the original poster descri

Re: heaps in clojure

Pepijn de Vos had a blogpost about lazy sorts. One of them seems to be a particularly good fit for this problem: http://pepijndevos.nl/lazy-sorting/index.html (the heap-sort example seems the fastest of those for this use-case...). Em sexta-feira, 16 de setembro de 2011, Mark Engelberg escreveu:

Re: heaps in clojure

That's really no different from just sorting the list and taking the first 5. O(n log(n)). And for really large data sets, this is going to consume a lot of memory. The method I outlined would be O(n) and doesn't force the sequence to all be resident in memory at the same time. On Fri, Sep 16, 2

Re: heaps in clojure

Using PriorityQueue should give a good, fast result. Here's my implementation: (defn smallest-n [n xs] (let [q (java.util.PriorityQueue. xs)] (for [i (range n)] (.poll q (smallest-n 5 (shuffle (range 100))) ;; (0 1 2 3 4) Jim -- You received this message because you are subscribed to

Re: heaps in clojure

Ah yeah. Sorry, I'd superimposed something I was thinking about on to the original problem. -- Dave On 15 Sep 2011 09:07, "Mark Engelberg" wrote: > The initial problem statement is to figure out what would be the first 10 > items if you sorted the list. > > I don't see anything about frequency

Re: heaps in clojure

The initial problem statement is to figure out what would be the first 10 items if you sorted the list. I don't see anything about frequency or how many times you've seen a given item in the statement of the problem. When I talk about a "best" item, I mean it is the first with regard to whatever

Re: heaps in clojure

But when an element is dropped from the list, you're effectively resetting its seen-count to zero. It might be seen again, and it might (if you hadn't reset the seen-count), have ended up in the top 10. Or have I misunderstood? -- Dave On 15 Sep 2011 08:54, "Mark Engelberg" wrote: > If you mai

Re: heaps in clojure

If you maintain the invariant that at each point, your sorted set contains the top 10 you've seen so far, then from that invariant you can conclude that at the end of the traversal, your sorted set contains the top 10 for the overall list. On Thu, Sep 15, 2011 at 12:34 AM, David Powell wrote: >

Re: heaps in clojure

Does that work? There is no guarantee that the top 10 of the overall list matches the top 10 of earlier prefixes, so the candidates that get discarded might be part of the overall top 10, and the elements that pushed them out could just be local maxima. -- Dave On 15 Sep 2011 08:23, "Mark Engelb

Re: heaps in clojure

You can do one linear pass over your data, accumulating a sorted set of the best 10 items you've found so far. You seed the sorted set with the first 10 items from your list, then continue traversing your list. With each new item you encounter, you ask if it is any better than the worst of the be

Re: heaps in clojure

Thanks Jason, I think some sort of priority queue may be the solution. Thanks, Sunil. On Wed, Sep 14, 2011 at 12:39 AM, Jason Wolfe wrote: > There is java.util.PriorityQueue, which is heap-based: > > > http://download.oracle.com/javase/1,5.0/docs/api/java/util/PriorityQueue.html > > -Jason > >

Re: heaps in clojure

Hi chouser, Thanks for your response. but correct me if I am wrong.. wouldn't sorted-set completely sort the complete collection without actually taking into account that only the first few elements are needed? Thanks, Sunil. On Tue, Sep 13, 2011 at 7:15 PM, Chouser wrote: > On Tue, Sep 13, 201

Re: heaps in clojure

There is java.util.PriorityQueue, which is heap-based: http://download.oracle.com/javase/1,5.0/docs/api/java/util/PriorityQueue.html -Jason On Sep 13, 4:44 am, Sunil S Nandihalli wrote: > Hi Everybody, >  I have a very large, but with finite size, collection. I would like to get > like first 1

Re: heaps in clojure

On Tue, Sep 13, 2011 at 7:44 AM, Sunil S Nandihalli wrote: > Hi Everybody, >  I have a very large, but with finite size, collection. I would like to get > like first 10 elements in the sorted list . I would use a heap if I were in > c++ .. is there a inbuilt implementation of this in clojure? .. I

Re: heaps in clojure

There is the inbuilt sort function, also sort-by is useful. In "The joy of clojure", there were an example of a lazy sort. It can be found here: http://www.manning.com/fogus/ In the file "q.clj" in the source code. Jonathan On Tue, Sep 13, 2011 at 1:44 PM, Sunil S Nandihalli < sunil.nandiha...@g

heaps in clojure

Hi Everybody, I have a very large, but with finite size, collection. I would like to get like first 10 elements in the sorted list . I would use a heap if I were in c++ .. is there a inbuilt implementation of this in clojure? .. Is there some other way to achieve this? some sort of lazy sort would