Я хочу создать график из облаков 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 секунды)
O
говорит не о том, насколько быстро работает алгоритм, а о том, как он масштабируется с входными данными. Вы можете создать алгоритмO(n)
, вычисляющий миллионы, и алгоритмыO(n^2)
, работающие за миллисекунды. ОбозначениеO
полезно знать, когда вы запускаете алгоритм с массивом размером 1, сколько это займет по сравнению с массивом другого размера. - person Ander Biguri   schedule 05.10.2016O(n^2)
-> каждыйO(n^2)
займет одинаковое время, и это просто неправильно. Поместите код, с которым вы хотите работать, и хорошо помогите оптимизировать - person Ander Biguri   schedule 05.10.2016