Производительность find () и цикл for

Question

У меня большой (4000 значений) набор несортированных, нормально распределенных точек.Я беру каждую из этих точек данных в контейнеры, пределы которых находятся в массиве BinLimit.Затем я суммирую количество значений в каждом бине.

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 .

N = HISTC (X, EDGES) для вектора X подсчитывает количество значений в X, попадающих между элементами в векторе EDGES.(который должен содержать монотонно неубывающие значения).N представляет вектор длины (EDGES), содержащий эти числа.

N (k) будет считать значение X (i), если EDGES (k) <= X (i) <EDGES (k + 1).Последний бин будет считать любые значения X, которые соответствуют EDGES (конец).Значения за пределами значений в EDGES не учитываются.Используйте -inf и inf в EDGES, чтобы включить все значения, отличные от NaN. </p>

Например

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 бункеру.Вы можете получить несколько корзин для значений X, которые попадают в BinLimits.

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 (Histc также работает быстрее для отсортированного X, так что это справедливое сравнение):

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 (время сортировки также указано в приведенном выше результате).Вот результаты работы с отчетами для несортированных массивов (тот же X, что и выше, перестановка со случайной перестановкой)

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

Как вы видите, время сортировки и подсчета в отсортированных массивах вместе аналогично запускув несортированном массиве.