arraysmatlabroulette-wheel-selection

(Roulette Wheel) Sorting multiple elements in an array


I'm perfoming a Roulette Wheel selection (http://www.edc.ncl.ac.uk/assets/hilite_graphics/rhjan07g02.png), and I want to compute the selection of n elements. How can I do this avoiding the use of loops?

For example, I have the following prob vector:

prob = [0.1 0.3 0.4 0.15 0.05];

The selection of a single element=0.2 would be:

cumprob = cumsum(prob);
selected = find(element<=prob,1,'first')

selected = 2

But, what about computing the selection of n elements? The intuitive and slow way would be:

cumprob = cumsum(prob);
for id = 1:1:n 
   selected(id) = find(element(id)<=prob,1,'first');
end

Is there any way to implement this avoiding the use of the for loop?

Thanks in advance.


Solution

  • Method 1: use discretize (requires Matlab version R2015a or newer)

    Method 2: use arrayfun which is way slower.

    Test code:

    n = 5e6;
    element = rand(n,1);
    prob = [0.1 0.3 0.4 0.15 0.05];
    
    cumprob = cumsum(prob);
    
    tic
    selected1 = zeros(n,1);
    for id = 1:1:n 
       selected1(id) = find(element(id)<=cumprob,1,'first');
    end
    toc
    
    tic
    selected2 = discretize(element,[0,cumprob]);
    toc
    isequal(selected1, selected2)
    
    tic
    selected3 = arrayfun(@(e) sum(e>=cumprob)+1, element);
    toc
    isequal(selected1, selected3)
    

    Timing (inaccurate, but works) and accuracy comparison:

    Elapsed time is 5.634721 seconds.
    Elapsed time is 0.059813 seconds.
    
    ans =
    
         1
    
    Elapsed time is 18.838859 seconds.
    
    ans =
    
         1
    
    >>