Thank you very much for your answer. I forgot to tell you that I also needs to be able to have usual set operations.
They become linear with your 1st idea. (But, sorry, it's my bad! I should have asked the right question. Your answer is very good for the question I actually asked, not the one I had in mind :)) The second idea is also good, but would perform a bit less good than using wider trees than binary. (I might use this second idea, though, with a set instead of a vector, if I can't manage to make HashTries work). On Sat, Jun 26, 2010 at 2:50 PM, Jules <julesjac...@gmail.com> wrote: > You can store the numbers in a vector [2 5 3]. Instead of doing this > store the cumulative weight v = [0 2 7 10]. What your problem comes > down to is given a number n, find the the lowest index i such that > v[i] <= n. This can be accomplished with binary search. You can also > use a binary search tree instead of a vector. You also keep a vector w > with the actual objects. Drawing is done like this: generate a random > number n between 0 and total-weight = (last v). Then find the smallest > index i such that v[i] <= n. The drawn object is w[i]. Hope this > helps. > > On 26 jun, 15:01, Nicolas Oury <nicolas.o...@gmail.com> wrote: > > Dear all, > > > > for a project, I need a data structure to represent finite distribution, > > that is a set of elements, each of which having a mass in the set, and > two > > functions: > > > > - total-mass : the sum of the masses of each element > > - draw : return an element with a probability proportional to its mass > > > > I currently use the simple idea : a Persistent Hash Map from elt to mass: > > - the total-mass is the reduce of (+ . second) > > - drawing is choosing a random-number between 0 and the total-mass and > > looping through the seq, to look for the corresponding element. > > > > Both operation are linear in the number of elements. This is a problem, > > because these sets tend to be quite big in my project. > > > > I think that if I used a HashTrie with total-mass cached in each node, > > total-mass would be in constant time and draw in log time. > > > > So here is my question : does anyone has, for example for the "clojure in > > clojure" project, a sketch of an implementation of PersistentHashMap > > in clojure itself? (I would be happy to contribute, if it needs more > work). > > Or has anyone a better idea that mine to have drawable sets? > > > > Thanks for your help, > > > > Best regards, > > > > Nicolas. > > -- > 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 > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com<clojure%2bunsubscr...@googlegroups.com> > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en -- 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 Note that posts from new members are moderated - please be patient with your first post. 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
