什么是在数组中快速计算元素数量的方法?

7
在我的模型中,最常见的任务之一是计算数组中每个元素的数量。这些计数来自一个封闭的集合,因此我知道有X种元素,并且所有或部分元素与表示“空”单元格的零一起填充数组。数组没有按任何方式排序,并且可能非常长(约1M个元素),在一个模拟期间需要执行数千次此任务(这也是数百个模拟的一部分)。结果应该是大小为X的向量r,因此r(k)是数组中k的数量。
示例:
对于X = 9,如果我有以下输入向量:
v = [0 7 8 3 0 4 4 5 3 4 4 8 3 0 6 8 5 5 0 3]

我希望能得到这个结果:
r = [0 0 4 4 3 1 1 3 0]

请注意,我不想要零的计数,而且在数组中没有出现的元素(比如 2)在结果向量的相应位置上有一个 0r(2) == 0)。
最快实现此目标的方法是什么?

在你编辑之后:为什么结果向量的长度是9?我怎么知道9是一个有效的数字,恰巧没有出现呢? - Dev-iL
@Dev-iL 我写道: “我知道有X种元素”, 然后 “结果应该是一个大小为X的向量”. - EBH
2个回答

11
tl;dr: 最快的方法取决于数组的大小。对于小于214的数组,下面的方法3 (accumarray) 更快。对于大于该大小的数组,下面的方法2 (histcounts) 更好。
更新:我还使用了2016b引入的implicit broadcasting进行了测试,结果几乎与bsxfun方法相同,在该方法中没有显着差异(相对于其他方法)。
让我们看看有哪些可用的方法来执行此任务。对于以下示例,我们将假设X具有n个元素,从1到n,我们感兴趣的数组是M,它是一个大小可能变化的列数组。我们的结果向量将是spp1,其中spp(k)Mk的数量。尽管我在这里写关于X,但在下面的代码中没有明确的实现,我只定义n = 500,并且X隐式地为1:500

朴素的for循环

解决此任务最简单和直接的方法是使用一个for循环迭代X中的元素,并计算等于它的M中的元素数量:
function spp = loop(M,n)
spp = zeros(n,1);
for k = 1:size(spp,1);
    spp(k) = sum(M==k); 
end
end

当然,这样做并不聪明,特别是当只有来自X的少量元素填充M时,因此我们最好先寻找那些已经在M中的元素:

function spp = uloop(M,n)
u = unique(M); % finds which elements to count
spp = zeros(n,1);
for k = u(u>0).';
    spp(k) = sum(M==k); 
end
end

通常,在MATLAB中,尽可能利用内置函数是可取的,因为大多数情况下它们更快。我想到了5个选项来实现这一点:
1. 函数 tabulate 函数tabulate返回一个非常方便的频率表,乍一看似乎是这个任务的完美解决方案:
function tab = tabi(M)
tab = tabulate(M);
if tab(1)==0
    tab(1,:) = [];
end
end

唯一需要修复的是,如果表格中计数了0元素(可能M中没有零),则需要删除表格的第一行。
2.函数histcounts。另一个可以很容易地根据我们的需求进行调整的选项是histcounts
function spp = histci(M,n)
spp = histcounts(M,1:n+1);
end

在这里,为了分别计算1到n之间的所有不同元素,我们将边界定义为1:n+1,因此X中的每个元素都有自己的箱子。我们也可以编写histcounts(M(M>0),'BinMethod','integers'),但我已经测试过它,它需要更多时间(尽管它使函数独立于n)。
3. 函数accumarray 接下来我要介绍的选项是使用函数accumarray
function spp = accumi(M)
spp = accumarray(M(M>0),1);
end

在这里,我们将函数M(M>0)作为输入,以跳过零,并使用1作为vals输入来计算所有唯一元素的数量。

4. 函数bsxfun

我们甚至可以使用二进制运算符@eq(即==)来查找每种类型的所有元素:

function spp = bsxi(M,n)
spp = bsxfun(@eq,M,1:n);
spp = sum(spp,1);
end

如果我们将第一个输入M和第二个1:n放在不同的维度中,那么一个是列向量,另一个是行向量,然后函数将比较M中的每个元素与1:n中的每个元素,并创建一个length(M)-by-n逻辑矩阵,我们可以对其进行求和以获得所需的结果。

5. 函数ndgrid

另一种选项类似于bsxfun,即使用ndgrid函数显式创建所有可能性的两个矩阵:
function spp = gridi(M,n)
[Mx,nx] = ndgrid(M,1:n);
spp = sum(Mx==nx);
end

然后我们将它们进行比较并在列上求和,以得到最终结果。

基准测试

我进行了一项小测试,以找出所有上述方法中最快的方法,我对所有测试定义了 n = 500。对于某些方法(特别是天真的 for),n 对执行时间有很大的影响,但这不是问题,因为我们想要针对给定的 n 进行测试。

以下是测试结果:Timing hist

我们可以注意到几件事:

  1. 有趣的是,最快的方法发生了转变。对于小于214的数组来说,accumarray是最快的。对于大于214的数组,histcounts是最快的。
  2. 如预期的那样,在两个版本中,朴素的for循环都是最慢的,但对于小于28的数组,“unique & for”选项更慢。在大于211 的数组中,ndgrid成为最慢的,这可能是因为需要在内存中存储非常大的矩阵。
  3. tabulate在小于29的大小的数组上工作的方法存在一些不规则性。在我进行的所有试验中,这个结果是一致的(模式略有变化)。

(由于在更高的值上会导致计算机卡顿,并且趋势已经非常明显),所以bsxfunndgrid曲线被截断了)

另外,请注意y轴为log10,因此单位减少(比如对于大小为219的数组,在accumarrayhistcounts之间),意味着操作速度快了10倍。

欢迎在评论中提出改进此测试的建议,如果您有另一种概念上不同的方法,请建议为答案。

代码

这里是所有函数包装在一个计时函数中:

function out = timing_hist(N,n)
M = randi([0 n],N,1);
func_times = {'for','unique & for','tabulate','histcounts','accumarray','bsxfun','ndgrid';
    timeit(@() loop(M,n)),...
    timeit(@() uloop(M,n)),...
    timeit(@() tabi(M)),...
    timeit(@() histci(M,n)),...
    timeit(@() accumi(M)),...
    timeit(@() bsxi(M,n)),...
    timeit(@() gridi(M,n))};
out = cell2mat(func_times(2,:));
end

function spp = loop(M,n)
spp = zeros(n,1);
for k = 1:size(spp,1);
    spp(k) = sum(M==k); 
end
end

function spp = uloop(M,n)
u = unique(M);
spp = zeros(n,1);
for k = u(u>0).';
    spp(k) = sum(M==k); 
end
end

function tab = tabi(M)
tab = tabulate(M);
if tab(1)==0
    tab(1,:) = [];
end
end

function spp = histci(M,n)
spp = histcounts(M,1:n+1);
end

function spp = accumi(M)
spp = accumarray(M(M>0),1);
end

function spp = bsxi(M,n)
spp = bsxfun(@eq,M,1:n);
spp = sum(spp,1);
end

function spp = gridi(M,n)
[Mx,nx] = ndgrid(M,1:n);
spp = sum(Mx==nx);
end

这是运行此代码并生成图形的脚本:

N = 25; % it is not recommended to run this with N>19 for the `bsxfun` and `ndgrid` functions.
func_times = zeros(N,5);
for n = 1:N
    func_times(n,:) = timing_hist(2^n,500);
end
% plotting:
hold on
mark = 'xo*^dsp';
for k = 1:size(func_times,2)
    plot(1:size(func_times,1),log10(func_times(:,k).*1000),['-' mark(k)],...
        'MarkerEdgeColor','k','LineWidth',1.5);
end
hold off
xlabel('Log_2(Array size)','FontSize',16)
ylabel('Log_{10}(Execution time) (ms)','FontSize',16)
legend({'for','unique & for','tabulate','histcounts','accumarray','bsxfun','ndgrid'},...
    'Location','NorthWest','FontSize',14)
grid on

1 这个奇怪的名称来源于我的领域,生态学。我的模型是元胞自动机,通常模拟虚拟空间中的个体生物(上面的M)。这些个体属于不同的物种(因此称为spp),共同组成所谓的“生态群落”。群落的“状态”由每个物种的个体数量组成,即本答案中的spp向量。在这些模型中,我们首先为个体定义一个物种库(上面的X),而群落状态考虑了物种库中的所有物种,而不仅仅是存在于M中的物种。


如果您在loop函数中展开for循环并将其替换为switch-case,则可以获得平衡的结果(丑陋但有效)。对于较小的数组大小,它比histcounts更快,但比accumarray慢。但是,对于大型数组大小,它比accumarry更快,比histcounts慢。我使用了您的代码来验证这一点。然而,最好的结果是使用if-else检查v的大小,然后使用accumarrayhistcounts,因为没有总体最佳答案。 - solid
@solid你所说的“用switch-case语句替换它”是什么意思?难道是为X中的每个元素写一个case,就像有500个case一样吗? - EBH
是的,有点。好吧,写500多个案例不好玩(而且不高效,因为展开太多会再次减慢代码速度,在一般情况下,即使让代码变得非常丑陋,这通常也是一个好主意)。你可以编写一些案例,例如使用20行“spp(k + i)= sum(M == k + i);”和“i = 0:19”,并调用此25次。它会产生一些开销,但仍然比在一个for循环中执行所有500个要快。 - solid

5
我们知道输入向量始终包含整数,那么为什么不利用这一点来从算法中“挤”出更多性能呢?
我一直在尝试优化两种最佳分箱方法suggested by the OP,这就是我想出的:
  • 唯一值的数量(问题中的X或示例中的n)应该明确转换为无符号整数类型。
  • 计算额外的箱并丢弃它比“仅处理”有效值更快(请参见下面的accumi_new函数)。

Though improvements are not large, it might be substantial when large datasets are involved.

这个函数在我的电脑上运行大约需要30秒时间。我正在使用MATLAB R2016a。


function q38941694
datestr(now)
N = 25;
func_times = zeros(N,4);
for n = 1:N
    func_times(n,:) = timing_hist(2^n,500);
end
% Plotting:
figure('Position',[572 362 758 608]);
hP = plot(1:n,log10(func_times.*1000),'-o','MarkerEdgeColor','k','LineWidth',2);
xlabel('Log_2(Array size)'); ylabel('Log_{10}(Execution time) (ms)')
legend({'histcounts (double)','histcounts (uint)','accumarray (old)',...
  'accumarray (new)'},'FontSize',12,'Location','NorthWest')
grid on; grid minor;
set(hP([2,4]),'Marker','s'); set(gca,'Fontsize',16);
datestr(now)
end

function out = timing_hist(N,n)
% Convert n into an appropriate integer class:
if n < intmax('uint8')
  classname = 'uint8';
  n = uint8(n);
elseif n < intmax('uint16')
  classname = 'uint16';
  n = uint16(n);
elseif n < intmax('uint32')
  classname = 'uint32';
  n = uint32(n);
else % n < intmax('uint64')  
  classname = 'uint64';
  n = uint64(n);
end
% Generate an input:
M = randi([0 n],N,1,classname);
% Time different options:
warning off 'MATLAB:timeit:HighOverhead'
func_times = {'histcounts (double)','histcounts (uint)','accumarray (old)',...
  'accumarray (new)';
    timeit(@() histci(double(M),double(n))),...
    timeit(@() histci(M,n)),...
    timeit(@() accumi(M)),...
    timeit(@() accumi_new(M))
    };
out = cell2mat(func_times(2,:));
end

function spp = histci(M,n)
  spp = histcounts(M,1:n+1);
end

function spp = accumi(M)
  spp = accumarray(M(M>0),1);
end

function spp = accumi_new(M)
  spp = accumarray(M+1,1);
  spp = spp(2:end);
end

非常好!事实上,在我的模型中,我一直使用uint,所以我已经利用了它,但你指出这一点很好。我想知道在数组大小为2^14时会发生什么,这似乎是histcountsaccumarray之间比较的关键点?此外,对于大数据,histcounts仍然是最佳选择。 - EBH
另外,只是为了好玩,我已经在答案中添加了另一种方法。 - EBH
@EBH 我也尝试了bsxfun的方法,但没有提及它,因为它并不更好。也许如果不是因为那个“tish'a be'av”的饥饿感,我会想出更好的主意... :P - Dev-iL
好的,我已经包含它是因为我想涵盖各种方法。无论如何,我认为这是应对饥饿最有效的方法之一 ;) - EBH

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接