Я хочу создать график из трехмерных облаков точек, захваченных Microsoft Kinect в Matlab. Это всего лишь 100 тысяч очков. Я написал очень простую программу, которая только вложенным для т.е. O (N^2) следующим образом:Увеличение числа символов O (n^2) и O (n^3) в Matlab при n ~ 100K
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.
Другими словами простой цикл займет 122 секунд! Я запустить его с:
Matlab 2016a
для Windows 10 Enterprise 64 бит
Intel Core i7-3820 @ 3,6 ГГц с 16 Гб оперативной памяти
В этой скорости, я не могу даже думать о O (n^3)
Я хочу запустить всю программу менее 1 с. перед тестированием выше программы я ожидал, что будет работать менее 0,1 секунды.
Edit 1:
1) два пользователей комментарий о XY! Я хочу создать взвешенный график (структуру данных) из точек и использовать этот график для поиска объектов (размер, положение, направление).
2) один пользователь комментирует векторизовать вычисления, это очень хорошо. однако ПК имеет только 16 ГБ оперативной памяти. векторизация вычислений с n ~ 100K требует 128 ГБ!
3) другие комментарии пользователей к обозначению O (n^2) и времени работы. Любая пиограмма в O (n^3) должна занимать больше времени, чем только цикл. Я хочу сказать, что когда простой простой цикл занимает 122 секунды, если я добавлю больше строки, это займет более 122 секунд. Мне нужно уменьшить его до 0,1 секунды (если это возможно не более 1 секунды)
Что вы на самом деле хотите сделать? Прямо сейчас вы переписываете одни и те же переменные на каждой итерации. – hbaderts
Если вы не можете избежать больших циклов и вопросов скорости, возможно, Matlab - это не лучший язык программирования, который вы могли бы выбрать. В большинстве случаев вы можете частично или полностью векторизовать свои вычисления, что резко увеличивает скорость. Если вы не знаете, как проводить векторизации вычислений, вы можете [проверить эту страницу] (https://www.mathworks.com/help/matlab/matlab_prog/vectorization.html) или отредактировать свой вопрос и поделиться некоторыми из операций, которые вы выполняются в цикле. – erfan
Боковое примечание: нотация 'O' не говорит вам, как быстро идет алгоритм, но как он масштабируется с помощью ввода. Вы можете сделать алгоритм, который является «O (n)», и принимает milenia для вычисления, и алгоритмы, которые являются «O (n^2)», и работают в миллисекундах. Обозначение 'O' полезно знать, как только вы запустили алгоритм с 1 размером массива, сколько потребуется, по сравнению с массивом другого размера. –