random - Efficient use of Octave's randsample (with weights) in a situation of huge vector and most weights equal to zero

Question

In an upcoming simulation project, I will come in a situation where I will have to draw one random element from a huge vector in a weighted sense. For most elements of the vector, the assigned weight will be zero. I also need to draw only one element, so the replacement or no replacement function is irrelevant.

This random picking step will be the bottleneck for my simulation, so getting the best efficiency and speed will be critical.

Are there any hacks/tips on what is best to do? Are there any important savings possible in the context of my project?

PS: Is randsample reliable on huge vectors?

question from:https://stackoverflow.com/questions/66045855/efficient-use-of-octaves-randsample-with-weights-in-a-situation-of-huge-vecto

Answer 1

Knowing that most weights are equal to zero you can rewrite a faster implementation of randsample from Octave source. In my timing it is 6X-7X faster than the original implementation:

function y = randsample_fast(v, w)
    f = find(w);
    w = w(f);
    w = w / sum(w);
    w = [0 cumsum(w)];
    y = f(lookup (w , rand));
    %y = f(find (w <= rand, 1, "last"));
    y = v(y);
end

• Inputs are assumed to be row vectors.
• Changing find to lookup may slightly improve the performance.