Увеличение скорости O (n ^ 2) и O (n ^ 3) в Matlab, когда n ~ 100K

Я хочу создать график из облаков 3D-точек, захваченных Microsoft Kinect в Matlab. Речь идет всего лишь о 100 тысячах баллов. Я написал очень простую программу, которая является только вложенной, т.е. O (n ^ 2) следующим образом:

load('Points_Sample1.mat')
Points=single(Points);
x=Points(1,:);
y=Points(2,:);
z=Points(3,:);

tic
for i=1:n
    xi=x(i);
    yi=y(i);
    zi=z(i);
   for j=1:n
        xj=x(j);
        yj=y(j);
        zj=z(j);
   end
end
toc

результат:

Elapsed time is 122.398886 seconds.

Другими словами, простой цикл for занимает 122 секунды! Я запускаю его с помощью:

Матлаб 2016а

Windows 10 Корпоративная 64 бит

Intel Core i7-3820 @ 3,6 ГГц с 16 ГБ ОЗУ

На такой скорости я даже не могу думать об O(n^3)

Я хочу запустить всю программу менее чем за 1 с. перед тестированием вышеуказанной программы я ожидал, что она будет работать менее 0,1 секунды.

Редактировать 1:

1) два пользователя комментируют XY! Я хочу создать взвешенный график (структуру данных) из точек и использовать этот график для поиска объектов (размер, положение, направление).

2) один пользователь прокомментировал векторизацию вычислений, это очень хорошо. однако у ПК всего 16 ГБ ОЗУ. для векторизации вычислений с n ~ 100K требуется 128 ГБ!

3) другие комментарии пользователей по нотации O(n^2) и времени выполнения. Любая пеограмма в O (n ^ 3) должна занимать больше времени, чем просто цикл. Я хочу сказать, что когда простой цикл занимает 122 секунды, если я добавлю больше строк, это займет более 122 секунд. Мне нужно уменьшить его до 0,1 секунды (если это невозможно, не более 1 секунды)


person some1    schedule 04.10.2016    source источник
comment
Что вы на самом деле хотите сделать? Прямо сейчас вы перезаписываете одни и те же три переменные на каждой итерации.   -  person hbaderts    schedule 05.10.2016
comment
Если вы не можете избежать больших циклов и для вас важна скорость, возможно, Matlab — не лучший язык программирования, который вы могли бы выбрать. В большинстве случаев вы можете частично или полностью векторизовать свои вычисления, что значительно увеличивает скорость. Если вы не знаете, как векторизовать вычисления, вы можете посетить эту страницу или отредактируйте свой вопрос и поделитесь некоторыми операциями, которые вы выполняете в цикле.   -  person erfan    schedule 05.10.2016
comment
Примечание: нотация O говорит не о том, насколько быстро работает алгоритм, а о том, как он масштабируется с входными данными. Вы можете создать алгоритм O(n), вычисляющий миллионы, и алгоритмы O(n^2), работающие за миллисекунды. Обозначение O полезно знать, когда вы запускаете алгоритм с массивом размером 1, сколько это займет по сравнению с массивом другого размера.   -  person Ander Biguri    schedule 05.10.2016
comment
Тем не менее, я бы перефразировал вопрос, поскольку вы просто предполагаете, что 2 цикла-> O(n^2) -> каждый O(n^2) займет одинаковое время, и это просто неправильно. Поместите код, с которым вы хотите работать, и хорошо помогите оптимизировать   -  person Ander Biguri    schedule 05.10.2016
comment
В дополнение к словам моих уважаемых коллег, прочитайте (и помните) о проблеме XY и убедитесь, что вы на эти грабли не наступишь...   -  person Dev-iL    schedule 05.10.2016
comment
Пока вы не расскажете нам, что вы на самом деле пытаетесь сделать, мы не сможем вам помочь. В нынешнем виде это просто вопрос, почему большие циклы занимают много времени? и на него нет конструктивного ответа.   -  person beaker    schedule 30.10.2016


Ответы (1)


Вам действительно нужно сравнить все N точек со всеми N-1 другими точками? Или достаточно обработать пары точек, находящихся относительно близко друг к другу? Большинство физических явлений быстро уменьшаются по мере увеличения расстояния, поэтому можно либо пренебречь влиянием удаленных точек, либо рассматривать комбинированный эффект большого числа удаленных точек, как если бы все они были расположены в одном направлении и на одном расстоянии.

Взгляните на структуры данных, такие как октодеревья, которые позволяют эффективно находить близлежащие точки, группируя дальние точки в кластеры.

person Ben Voigt    schedule 29.10.2016