matlab - Matlab 中唯一值的累计计数

Question

假设您正在收集卡片 - 您的相册由 n_cards 卡片组成。您购买的每一包都包含cards_in_pack张卡，每张卡被抽取的概率相同。如果您不能交易您的 double ，您需要购买多少包才能收集所有卡片？假设你想模拟这个过程。这是一种显而易见的方法:

n_cards = 100; n_experiments = 1e4; cards_in_pack = 5;
cards = randi([1 n_cards], ceil(sqrt(n_cards)) * n_experiments * n_cards, 1, 'uint16');

tic
n_packs = zeros(n_experiments, 1);
ctrl1 = 1;
i_f = 0;
n = 0;
while ctrl1
  ctrl2 = 1;
  i1 = 0;
  while ctrl2
    i1 = i1 + 1;
    ctrl2 = numel(unique(cards((cards_in_pack * i_f + 1):(cards_in_pack * (i_f + i1))))) ~= n_cards;
  end
  n = n + 1;
  n_packs(n) = i1;
  i_f = i_f + i1;
  ctrl1 = n ~= n_experiments;
end
toc

% Average number of packs: 
mean(n_packs)
% Distribution of the number of packs necessary to complete the album
hist(n_packs, 50)

% Number of cards needed in the experiments: 
sum(n_packs) * cards_in_pack

这很慢 - 有更快的方法吗？具体来说:有没有一种快速计算 Matlab 中唯一值累积计数的方法？

Answer 1

模拟可以跨实验矢量化。因此去掉了实验循环，大大减少了仿真时间。

由于每个实验可能在不同时间完成(需要不同数量的包)，因此实验可以处于两种状态:正在进行 或已完成。该代码维护一个正在进行的实验向量 (exps_ongoing) 和一个在每个实验中获得的卡片的 0-1 矩阵 (cards_obtained)。

对于每个正在进行的实验，都会生成一个新包，并且该包中包含的卡片被(覆盖)写入cards_obtained。为正在进行的实验获取所有卡片后，该实验将从 exps_ongoing 中删除。当所有实验都完成时，代码结束。

n_cards = 100;
cards_in_pack = 5;
n_experiments = 1e4;

cards_obtained = zeros(n_cards,n_experiments);
%// will contain cards obtained in each experiment
exps_ongoing = 1:n_experiments; %// list of which experiments are ongoing
n_packs = zeros(1,n_experiments); %// will record how many packs have been used
while ~isempty(exps_ongoing)
    n_packs(exps_ongoing) = n_packs(exps_ongoing) + 1;
    %// pick one pack for each ongoing experiment
    new_cards = randi(n_cards,cards_in_pack,numel(exps_ongoing));
    %// generate pack contents for each ongoing experiment
    cards_obtained(new_cards + repmat(((exps_ongoing)-1)*n_cards,cards_in_pack,1)) = true;
    %// take note of obtained cards in each ongoing experiment. Linear indexing is used here
    exps_ongoing = setdiff(exps_ongoing,exps_ongoing(all(cards_obtained(:,exps_ongoing))));
    %// ongoing experiments for which all cards have been obtained are removed
end
disp(mean(n_packs))

对于您的输入数据，这在我的计算机上将时间减少了50 倍(104.36 秒对比 1.89 秒，使用 tic、toc 测量)。