TL; DR
Для максимальной производительности, если вам нужен только один образец, используйте
R = a( sum( (rand(1) >= cumsum(w./sum(w)))) + 1 );
и если вам нужно несколько образцов, используйте
[~, R] = histc(rand(N,1),cumsum([0;w(:)./sum(w)]));
Избегайте randsample. Генерирование нескольких выборок заранее на три порядка быстрее, чем создание отдельных значений.
Показатели производительности
Поскольку это обнаружилось в верхней части моего поиска в Google, я просто хотел добавить некоторые показатели производительности, чтобы показать, что правильное решение будет очень сильно зависеть от значения N и требований приложения. Кроме того, изменение дизайна приложения может значительно повысить производительность.
Для больших N, или даже N > 1:
a = 1:3; % possible numbers
w = [0.3 0.1 0.2]; % corresponding weights
N = 100000000; % number of values to generate
w_normalized = w / sum(w) % normalised weights, for indication
fprintf('randsample:\n');
tic
R = randsample(a, N, true, w);
toc
tabulate(R)
fprintf('bsxfun:\n');
tic
R = a( sum( bsxfun(@ge, rand(N,1), cumsum(w./sum(w))), 2) + 1 );
toc
tabulate(R)
fprintf('histc:\n');
tic
[~, R] = histc(rand(N,1),cumsum([0;w(:)./sum(w)]));
toc
tabulate(R)
Результаты:
w_normalized =
0.5000 0.1667 0.3333
randsample:
Elapsed time is 2.976893 seconds.
Value Count Percent
1 49997864 50.00%
2 16670394 16.67%
3 33331742 33.33%
bsxfun:
Elapsed time is 2.712315 seconds.
Value Count Percent
1 49996820 50.00%
2 16665005 16.67%
3 33338175 33.34%
histc:
Elapsed time is 2.078809 seconds.
Value Count Percent
1 50004044 50.00%
2 16665508 16.67%
3 33330448 33.33%
В этом случае histc является самым быстрым
Однако в случае, когда, возможно, невозможно сгенерировать все N значений заранее, возможно, потому что веса обновляются на каждой итерации, т.е. N=1:
a = 1:3; % possible numbers
w = [0.3 0.1 0.2]; % corresponding weights
I = 100000; % number of values to generate
w_normalized = w / sum(w) % normalised weights, for indication
R=zeros(N,1);
fprintf('randsample:\n');
tic
for i=1:I
R(i) = randsample(a, 1, true, w);
end
toc
tabulate(R)
fprintf('cumsum:\n');
tic
for i=1:I
R(i) = a( sum( (rand(1) >= cumsum(w./sum(w)))) + 1 );
end
toc
tabulate(R)
fprintf('histc:\n');
tic
for i=1:I
[~, R(i)] = histc(rand(1),cumsum([0;w(:)./sum(w)]));
end
toc
tabulate(R)
Результаты:
0.5000 0.1667 0.3333
randsample:
Elapsed time is 3.526473 seconds.
Value Count Percent
1 50437 50.44%
2 16149 16.15%
3 33414 33.41%
cumsum:
Elapsed time is 0.473207 seconds.
Value Count Percent
1 50018 50.02%
2 16748 16.75%
3 33234 33.23%
histc:
Elapsed time is 1.046981 seconds.
Value Count Percent
1 50134 50.13%
2 16684 16.68%
3 33182 33.18%
В этом случае пользовательский подход cumsum (основанный на версии bsxfun) является самым быстрым.
В любом случае randsample определенно выглядит как плохой выбор со всех сторон. Это также показывает, что если алгоритм может быть организован для генерации всех случайных переменных заранее, то он будет работать на намного лучше (обратите внимание, что в случае N=1 в случае *1042* генерируются значения на три порядка меньше). аналогичное время выполнения).
Код доступен здесь .