计算数组中元素的最快方法是什么? [英] What is the fastest way to count elements in an array?

问题描述

在我的模型中，要完成的最重复的任务之一是计算数组中每个元素的数量.计数来自一个封闭的集合，所以我知道有 X 类型的元素，它们全部或部分填充数组，以及代表空"单元格的零.该数组没有以任何方式排序，并且可能排序很长(大约 100 万个元素)，并且该任务在一次模拟(也是数百次模拟的一部分)期间完成了数千次.结果应该是一个大小为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)在相应的数组中有一个 0结果向量的位置 (r(2) == 0).

实现这一目标的最快方法是什么?

解决方案

tl;dr: 最快的方法取决于数组的大小.对于小于 2¹⁴ 的数组，下面的方法 3 (accumarray) 更快.对于比下面的方法 2 (histcounts) 更大的数组.

更新:我也用

我们可以注意到以下几点:

1. 有趣的是，最快的方法发生了变化.对于小于 2¹⁴ 的数组，accumarray 是最快的.对于大于 2¹⁴ 的数组，histcounts 是最快的.
2. 正如预期的那样，原始的 for 循环在两个版本中都是最慢的，但是对于小于 2⁸ 的数组，unique & for"选项更慢.ndgrid 在大于 2¹¹ 的数组中变得最慢，可能是因为需要在内存中存储非常大的矩阵.
3. tabulate 处理小于 2⁹ 的数组的方式存在一些不规则性.这个结果在我进行的所有试验中都是一致的(在模式上有一些变化).

(bsxfun 和 ndgrid 曲线被截断，因为它让我的电脑卡在更高的值上，而且趋势已经很明显了)

另外，请注意 y 轴在 log₁₀ 中，因此单位减少(例如对于大小为 2¹⁹ 的数组，accumarray 和 histcounts) 表示操作速度提高 10 倍.

我很高兴听到有关此测试改进的评论，如果您有另一种概念上不同的方法，欢迎您提出建议作为答案.

代码

以下是封装在计时函数中的所有函数:

函数输出=timing_hist(N,n)M = 兰迪([0 n],N,1);func_times = {'for','unique &for ','tabulate','histcounts','accumarray','bsxfun','ndgrid';时间(@()循环(M，n))，...时间(@() uloop(M,n)),...timeit(@() tabi(M)),...timeit(@() histci(M,n)),...时间(@() accumi(M)),...时间(@() bsxi(M,n)),...timeit(@() gridi(M,n))};out = cell2mat(func_times(2,:));结尾函数 spp = 循环(M，n)spp = 零(n，1)；对于 k = 1:size(spp,1);spp(k) = sum(M==k);结尾结尾函数 spp = uloop(M,n)u = 唯一 (M);spp = 零(n，1)；对于 k = u(u>0).';spp(k) = sum(M==k);结尾结尾功能选项卡 = 分趾袜(M)制表符 = 制表(M)；如果选项卡(1)==0tab(1,:) = [];结尾结尾函数 spp = histci(M,n)spp = histcounts(M,1:n+1);结尾函数 spp = accumi(M)spp = accumarray(M(M>0),1);结尾函数 spp = bsxi(M,n)spp = bsxfun(@eq,M,1:n);spp = sum(spp,1);结尾函数 spp = gridi(M,n)[Mx,nx] = ndgrid(M,1:n);spp = sum(Mx==nx);结尾

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

N = 25;% 对于 `bsxfun` 和 `ndgrid` 函数，不建议使用 N>19 运行它.func_times = zeros(N,5);对于 n = 1:Nfunc_times(n,:) =timing_hist(2^n,500);结尾% 绘图:坚持，稍等标记 = 'xo*^dsp';对于 k = 1:size(func_times,2)plot(1:size(func_times,1),log10(func_times(:,k).*1000),['-' mark(k)],...'MarkerEdgeColor','k','LineWidth',1.5);结尾推迟xlabel('Log_2(Array size)','FontSize',16)ylabel('Log_{10}(执行时间) (ms)','FontSize',16)Legend({'for','unique & for','tabulate','histcounts','accumarray','bsxfun','ndgrid'},...'位置','西北','字体大小',14)网格开启

<小时>

¹ _{这个奇怪名字的原因来自我的领域，生态学.我的模型是一个细胞自动机，它通常模拟虚拟空间中的个体生物(上面的 M).这些个体属于不同的物种(因此是spp)，它们共同构成了所谓的生态群落".社区的状态"由每个物种的个体数量给出，这是本答案中的 spp 向量.在这个模型中，我们首先为要从中抽取的个体定义了一个物种池(上面的X)，群落状态考虑了物种池中的所有物种，而不仅仅是中存在的物种>M}

In my models, one of the most repeated tasks to be done is counting the number of each element within an array. The counting is from a closed set, so I know there are X types of elements, and all or some of them populate the array, along with zeros that represent 'empty' cells. The array is not sorted in any way, and could by quite long (about 1M elements), and this task is done thousands of times during one simulation (which is also part of hundreds of simulations). The result should be a vector r of size X, so r(k) is the amount of k in the array.

Example:

For X = 9, if I have the following input vector:

v = [0 7 8 3 0 4 4 5 3 4 4 8 3 0 6 8 5 5 0 3]

I would like to get this result:

r = [0 0 4 4 3 1 1 3 0]

Note that I don't want the count of zeros, and that elements that don't appear in the array (like 2) have a 0 in the corresponding position of the result vector (r(2) == 0).

What would be the fastest way to achieve this goal?

解决方案

tl;dr: The fastest method depend on the size of the array. For array smaller than 2¹⁴ method 3 below (accumarray) is faster. For arrays larger than that method 2 below (histcounts) is better.

UPDATE: I tested this also with implicit broadcasting, that was introduced in 2016b, and the results are almost equal to the bsxfun approach, with no significant difference in this method (relative to the other methods).

---

Let's see what are the available methods to perform this task. For the following examples we will assume X has n elements, from 1 to n, and our array of interest is M, which is a column array that can vary in size. Our result vector will be spp¹, such that spp(k) is the number of ks in M. Although I write here about X, there is no explicit implementation of it in the code below, I just define n = 500 and X is implicitly 1:500.

The naive for loop

The most simple and straightforward way to cope this task is by a for loop that iterate over the elements in X and count the number of elements in M that equal to it:

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

This is off course not so smart, especially if only little group of elements from X is populating M, so we better look first for those that are already in 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

---

Usually, in MATLAB, it is advisable to take advantage of the built-in functions as much as possible, since most of the times they are much faster. I thought of 5 options to do so:

1. The function tabulate

The function tabulate returns a very convenient frequency table that at first sight seem to be the perfect solution for this task:

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

The only fix to be done is to remove the first row of the table if it counts the 0 element (it could be that there are no zeros in M).

2. The function histcounts

Another option that can be tweaked quite easily to our need it histcounts:

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

here, in order to count all different elements between 1 to n separately, we define the edges to be 1:n+1, so every element in X has it's own bin. We could write also histcounts(M(M>0),'BinMethod','integers'), but I already tested it, and it takes more time (though it makes the function independent of n).

3. The function accumarray

The next option I'll bring here is the use of the function accumarray:

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

here we give the function M(M>0) as input, to skip the zeros, and use 1 as the vals input to count all unique elements.

4. The function bsxfun

We can even use binary operation @eq (i.e. ==) to look for all elements from each type:

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

if we keep the first input M and the second 1:n in different dimensions, so one is a column vector the other is a row vector, then the function compares each element in M with each element in 1:n, and create a length(M)-by-n logical matrix than we can sum to get the desired result.

5. The function ndgrid

Another option, similar to the bsxfun, is to explicitly create the two matrices of all possibilities using the ndgrid function:

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

then we compare them and sum over columns, to get the final result.

Benchmarking

I have done a little test to find the fastest method from all mentioned above, I defined n = 500 for all trails. For some (especially the naive for) there is a great impact of n on the time of execution, but this is not the issue here since we want to test it for a given n.

Here are the results:

We can notice several things:

1. Interestingly, there is a shift in the fastest method. For arrays smaller than 2¹⁴ accumarray is the fastest. For arrays larger than 2¹⁴ histcounts is the fastest.
2. As expected the naive for loops, in both versions are the slowest, but for arrays smaller than 2⁸ the "unique & for" option is slower. ndgrid become the slowest in arrays bigger than 2¹¹, probably because of the need to store very large matrices in memory.
3. There is some irregularity in the way tabulate works on arrays in size smaller than 2⁹. This result was consistent (with some variation in the pattern) in all the trials I conducted.

(the bsxfun and ndgrid curves are truncated because it makes my computer stuck in higher values, and the trend is quite clear already)

Also, notice that the y-axis is in log₁₀, so a decrease in unit (like for arrays in size 2¹⁹, between accumarray and histcounts) means a 10-times faster operation.

I'll be glad to hear in the comments for improvements to this test, and if you have another, conceptually different method, you are most welcome to suggest it as an answer.

The code

Here are all the functions wrapped in a timing function:

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

And here is the script to run this code and produce the graph:

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

---

¹ _{The reason for this weird name comes from my field, Ecology. My models are a cellular-automata, that typically simulate individual organisms in a virtual space (the M above). The individuals are of different species (hence spp) and all together form what is called "ecological community". The "state" of the community is given by the number of individuals from each species, which is the spp vector in this answer. In this models, we first define a species pool (X above) for the individuals to be drawn from, and the community state take into account all species in the species pool, not only those present in M}

这篇关于计算数组中元素的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！