Matlab - Ускорение Вложенного Для Цикла
Простой вопрос, но я не являюсь настолько великим с MATLAB. У меня есть векторы x, (n x 1) y, (m x 1) и w = [x;y]. Я хочу определить M (n+m x 1) как M (i) = число элементов x, которые меньше чем или равны w (i) (w отсортирован). Это просто не сокращает его:
N = n + m;
M = zeros(N,1);
for i = 1:N
for j = 1:n
if x(j) <= w(i)
M(i) = M(i) + 1;
end
end
end
Это не особенно умный способ сделать это, и некоторые мои векторы данных m и n - приблизительно 100 000.
Спасибо!
5 ответов
Это может выглядеть загадочно, но должно дать тот же результат, что и вложенные петли:
M = histc(-x(:)',[-fliplr(w(:)') inf]);
M = cumsum(fliplr(M(1:N)))';
Вышеприведенное предполагает, что w отсортирован по возрастанию.
Объяснение
Ваш отсортированный вектор w можно рассматривать как бинарные рёбра, которые можно использовать при создании гистограммы с функцией HISTC. После подсчета количества значений, которые попадают в каждый бинокль (т.е. между рёбрами), кумулятивная сумма по этим бинам с помощью функции CUMSUM даст вам вектор M. Причина, по которой приведенный выше код выглядит таким запутанным (с отрицаниями и функцией FLIPLR в нем), заключается в том, что Вы хотите найти значения в x меньше или равные каждому значению в w, но функция HISTC выводит бины данных следующим образом:
n(k)считает значениеx(i), есликрая(k) <= x(i) <края(k+1).
Обратите внимание, что для верхнего предела каждого бина используется меньше . Вы захотите перевернуть поведение так, чтобы бина соответствовала правилу edgeges(k) < x(i) <= edgeges(k+1), что может быть достигнуто отрицанием значений, которые будут бинарными, отрицанием edgeges, переворачиванием edge (так как входной фронт для HISTC должен быть монотонно безубыточным), а затем переворачиванием возвращаемых отсчетов бина. Значение inf используется в качестве значения фронта импульса для подсчета всех значений меньше, чем наименьшее значение в w в первом бине.
Если бы вы хотели найти значения в x, которые просто меньше каждого значения в w, код был бы намного проще:
M = histc(x(:)',[-inf w(:)']);
M = cumsum(M(1:N))';
Как минимум внутренний цикл можно заменить на:
M(i)=sum(x<=w(i))
это обеспечит существенное улучшение производительности. Тогда можно подумать об использовании массива arrayfun:
M = arrayfun(@(wi)( sum( x <= wi ) ), w);
arrayfun вряд ли даст существенный выигрыш во внешнем цикле, но стоит попробовать.
edit: Следует заметить, что ни w, ни x не нужно сортировать, чтобы эта операция работа работала корректно.
ed: fwiw, я решил сделать реальное тестирование производительности, поэтому запустил эту программу:
n = 100000; m = n;
N = n + m;
x = rand(n, 1);
w = [x; rand(m, 1)];
tic;
M = zeros(N,1);
for i = 1:N
for j = 1:n
if x(j) <= w(i)
M(i) = M(i) + 1;
end
end
end
perf = toc;
fprintf(1, 'Original : %4.3f sec\n', perf);
w = sort(w); % presorted, so don't incur time cost;
tic;
M = histc(-x(:)',[-fliplr(w(:)') inf]);
M = cumsum(fliplr(M(1:N)))';
perf = toc;
fprintf(1, 'gnovice : %4.3f sec\n', perf);
tic;
M = zeros(N,1);
for i = 1:N
M(i)=sum(x<=w(i));
end
perf = toc;
fprintf(1, 'mine/loop : %4.3f sec\n', perf);
tic;
M = arrayfun(@(wi)( sum( x <= wi ) ), w);
perf = toc;
fprintf(1, 'mine/arrayfun : %4.3f sec\n', perf);
и получил эти результаты для n = 1000:
Original : 0.086 sec
gnovice : 0.002 sec
mine/loop : 0.042 sec
mine/arrayfun : 0.070 sec
и для n = 100000:
Original : too long to tell ( >> 1m )
gnovice : 0.050 sec
mine/loop : too long to tell ( >> 1m )
mine/arrayfun : too long to tell ( >> 1m )
попробуйте вместо этого:
M = sum( bsxfun(@le, w', sort(w)) , 2 )
Давно не делал MATLAB, но это должно работать:
Сортировать х со встроенным алгоритмом сортировки вверх.
Использовать цикл с блуждающим индексом для итерации только один раз над x(j)
j = 1; для i = 1:N в то время как j <= n && x(j) <= w(i) M(i) = M(i) + 1; j = j+1; конец конецНаконец-то накапливаем сумму
для j =2:n M(j) = M(j-1) + M(j) конец
У меня нет перед глазами Матлаба, так что я не могу подтвердить, что он на 100% функционален, но вы можете попробовать что-нибудь вроде:
for i = 1:N
M(i) = arrayfun(@(ary,val)length(find(ary <= val)), x, w(i))
end