find()与for循环的性能比较

Question

我有一个很大的(4000个值)未排序的正态分布点集合。我将这些数据点都放入限制在BinLimit数组中的存储箱中。然后，我会将每一个bin中的值数列成表格。

X是原始数据的数组，N是数据点的数量。所需的仓位数(TotalBins)由用户指定。

方法#1

for i=1:TotalBins
    Freq(i) = length(find(X >= BinLimit(j) & X <= BinLimit(j+1)));
    j = j + 1;
end

方法#2：

sort(X);

for i=1:N
    if (X(i) >= BinLimit(j) && X(i) <= BinLimit(j+1))
        Freq(j) = freq(j) + 1;
    elseif (j < TotalBins)
        Freq(j+1) = freq(j+1) + 1;
        j = j + 1;
    end
end

现在，我知道第一个解决方案更慢-对于Total Bins (25-50)的正常值，它大约慢8倍，但我想知道是否有比我在方法2中所做的更快、更有效的解决方案。

Answer 1

使用histc。

对于向量X，

N= HISTC(X，EDGES)计算X中落在边向量(必须包含单调非递减值)元素之间的值的数量。N是包含这些计数的长度(边)向量。N(k)如果边(K) <= X(i) <边(k+1)，则计数值X(i)。最后一个框将计算与边匹配的X的任何值(结束)。边值之外的值不会被计算在内。在边中使用-inf和inf可包含所有非NaN值。

例如。

BinLimit = sort(rand(50,1));
X = rand(4000,1);
Freq = histc(X,BinLimit);

为了好玩：

%%# Generating data
X = rand(1000000,1);
BinLimit = sort(rand(50,1));

%%# OP's method
disp('Method #1');
disp('=========');
tic;
j =1;
TotalBins = numel(BinLimit)-1;
for i=1:TotalBins
    Freq(i) = length(find(X >= BinLimit(j) & X <= BinLimit(j+1)));
    j = j + 1;
end
toc

%%# histc
disp('histc');
disp('=====');
tic;
histc(X,BinLimit);
toc

%%# My method
disp('Alternative');
disp('===========');
tic;
TotalBins = numel(BinLimit)-1;
Freq = zeros(TotalBins,1);
for i = 1:TotalBins
    Freq(i) = sum(X >= BinLimit(i) & X <= BinLimit(i+1));
end
toc

跑了几次热身后：

Method #1
=========
Elapsed time is 0.803120 seconds.
histc
=====
Elapsed time is 0.030633 seconds.
Alternative
===========
Elapsed time is 0.704808 seconds.

Answer 2

除了使用HISTC之外，这里还有一个矢量化的单行解决方案：

X = randn(4000,1);                %# column vector
BinLimits = linspace(-4,4,10);    %# row vector

Freq = sum( bsxfun(@ge, X, BinLimits(1:end-1)) & bsxfun(@le, X, BinLimits(2:end)) )

请注意，它并不节省空间，因为它创建了一个大小为：length(X) by length(BinLimits)-1的矩阵

Answer 3

我认为当你检查X是否属于一个bin时，你可能有一个错误。对于落入BinLimits的X值，您可能会得到多个存储箱。

X >= BinLimit(j) & X <= BinLimit(j+1)

无论如何，既然你要求一个循环解决方案，这里有一个比你的方法2执行得更好的解决方案。

j=1;
i=1;
while i<=N
    while i<=N && X(i)<=BinLimit(j+1)
        i=i+1;
    end
    Freq(j) = i-1;
    j = j+1;
end
Freq=diff([0 Freq]);

它需要对X进行排序，就像在您的代码中一样。下面是用于排序X数组的所有讨论方法的时序(对于排序的X，histc也更快，因此这是一个公平的比较)：

Sort
===========
Elapsed time is 0.019205 seconds.
Method #1
=========
Elapsed time is 0.209979 seconds.
histc
=====
Elapsed time is 0.009595 seconds.
Alternative
===========
Elapsed time is 0.228400 seconds.
Method 2
===========
Elapsed time is 0.025400 seconds.
my method
===========
Elapsed time is 0.011920 seconds.
bsxfun by Amro
===========
Elapsed time is 0.179937 seconds.

如你所见，这种循环结构的性能几乎和histc一样好(差25%)。

这是针对排序的X的(排序时间也在上面的结果中给出)。下面是未排序数组的histc结果(与上面相同的X，用随机排列进行排列)

histc
=====
Elapsed time is 0.030367 seconds.

正如您所看到的，对已排序的数组同时执行排序和histc的时间与对未排序的数组运行histc的时间相似。