0

I have an array, lets say :

var people = [
    {name: "Jack", weight: 10},
    {name: "Beth",weight: 2},
    {name: "Michael",weight: 5},
    {name: "Elsa",weight: 6},
    {name: "April",weight: 3},
    {name: "John",weight: 6},
    {name: "David",weight: 1}
]

And I want to pick from this list of objects, while picking some of them more often according to their weight.

I can do that with brute force by pushing each object into a seperate array as many times as their weight value.

eg: var newArr = ["Jack", "Jack", "Jack", ........, "John", "John", "David"];

But this is not an elegant and optimal way of doing things. Given a large number of objects, this solution does not provide a good peformance.

I want to create a function to select from the array, and run that function 100 times, or even 1000 times to check if the solution returns a desired distribution.

function selectVolunteer(arr) {
    // some code here
    return randomVolunteer;
}
// Now run the function 1000 times to check this works
for (var i = 0; i < 10000; i++) {
    function selectVolunteer(people)
}

So, what are my options to create a more efficient algorithm, so that when i iterate through a list of 100000 objects there will be no problem.

While posting this, i looked at some questions suggested by StackOverflow, but could not find what i was looking for. There is an answer Generate A Weighted Random Number suggested by @trincot, but there are some conflicts with the question i asked. If i run that suggested function with these parameters arr = {0:0.1, 1:0.7, 2:0.9} 10000 times, it gives me this output : 0 : 983 , 1 : 7011 and 2 : 2006 which is all wrong because 2 has more probability than 1 while outout suggest something different.

Thank you.

Community
  • 1
  • 1
Rüzgar
  • 947
  • 9
  • 20
  • None of the duplicates satisfied you? In what way? – trincot May 06 '17 at 09:45
  • Is the `weight` going to stay the same? Or do you intend on changing it when calling the function? – ibrahim mahrir May 06 '17 at 09:47
  • @trincot, sorry i may have put it wrong, lets not say satisfied, but not the answer i was looking for. In some of them there were even no proper answer at all. – Rüzgar May 06 '17 at 09:49
  • The referred to answer (http://stackoverflow.com/a/8435261/5459839) has two different ways of doing it, and has a comment to optimise the second way. I don't see there is more to it. – trincot May 06 '17 at 09:51
  • @ibrahim mahrir yes, weight are going to stay same for each object in the array. – Rüzgar May 06 '17 at 09:51
  • @trincot, i checked that answer, but it is not accurate. If i run the function with these parameters `arr = {0:0.1, 1:0.7, 2:0.9}` 10000 times, it gives me this output : `0 : 983` , `1 : 7011` and `2 : 2006` which is all wrong because 2 has more probability than 1 while outout suggest something different. I think you should consider re-opening this question. – Rüzgar May 06 '17 at 10:41
  • https://jsfiddle.net/g38uh7zw/, if `weight`s could be floats, then remove `Math.floor`. – ibrahim mahrir May 06 '17 at 10:51
  • @ibrahim mahrir, i checked your solution. And it is working as expected. Thank you for your efforts, Happy to accept as correct answer, if this post is reopened. – Rüzgar May 06 '17 at 10:53
  • @Rüzgar You're welcome! Just notice that I rolled back to the previous version, the one with `rand = Math.floor(Math.random() * sum);` not `rand = Math.floor(Math.random() * (sum + 1));` I got confused when I was sketching the example on paper :D. – ibrahim mahrir May 06 '17 at 10:54
  • 2
    No problem. Looking at your code, i got what you mean. Thanks again. But i believe we should re-open this so that other people may find this useful. – Rüzgar May 06 '17 at 11:00
  • 2
    @Rüzgar, your distribution has to be normalised to sum to 1 before you apply the solution at the referenced answer. If you need it to work with distributions of which the coefficients sum up to something else than 1, then it is not difficult to either adapt your input, or else adapt the code. Other answers in the same Q&A deal with the latter. There is no reason to reopen this question. – trincot May 06 '17 at 11:28
  • @trincot Thanks. – Rüzgar May 06 '17 at 11:31

0 Answers0