java - How to efficiently generate a set of unique random numbers with a predefined distribution?

Question

I have a map of items with some probability distribution:

Map<SingleObjectiveItem, Double> itemsDistribution;

Given a certain m I have to generate a Set of m elements sampled from the above distribution.

As of now I was using the naive way of doing it:

while(mySet.size < m)
   mySet.add(getNextSample(itemsDistribution));

The getNextSample(...) method fetches an object from the distribution as per its probability. Now, as m increases the performance severely suffers. For m = 500 and itemsDistribution.size() = 1000 elements, there is too much thrashing and the function remains in the while loop for too long. Generate 1000 such sets and you have an application that crawls.

Is there a more efficient way to generate a unique set of random numbers with a "predefined" distribution? Most collection shuffling techniques and the like are uniformly random. What would be a good way to address this?

UPDATE: The loop will call getNextSample(...) "at least" 1 + 2 + 3 + ... + m = m(m+1)/2 times. That is in the first run we'll definitely get a sample for the set. The 2nd iteration, it may be called at least twice and so on. If getNextSample is sequential in nature, i.e., goes through the entire cumulative distribution to find the sample, then the run time complexity of the loop is at least: n*m(m+1)/2, 'n' is the number of elements in the distribution. If m = cn; 0<c<=1 then the loop is at least Sigma(n^3). And that too is the lower bound!

If we replace sequential search by binary search, the complexity would be at least Sigma(log n * n^2). Efficient but may not be by a large margin.

Also, removing from the distribution is not possible since I call the above loop k times, to generate k such sets. These sets are part of a randomized 'schedule' of items. Hence a 'set' of items.

Answer 1

Start out by generating a number of random points in two dimentions.

Then apply your distribution

Now find all entries within the distribution and pick the x coordinates, and you have your random numbers with the requested distribution like this: