Matlab에서 O (n^2) 및 O (n^3) 증가 spurs n ~ 100K

Question

Matlab에서 Microsoft Kinect로 캡처 한 3D 점 구름에서 그래프를 만들고 싶습니다. 약 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 초가 걸릴 I는 다음과 같이, 즉 O (N^2)에만 중첩 매우 간단한 프로그램을 작성! 나는 그것을 실행

의 MATLAB 2016a 윈도우 10 기업 64 비트

인텔 코어 i7-3820이 속도에서 16기가바이트 RAM

3.6 GHz의

@, 그럴 수 없어 O (n^3)에 대해서도 생각해보십시오.

전체 프로그램을 1 미만으로 실행하고 싶습니다. 위의 프로그램을 테스트하기 전에 0.1 초 미만으로 실행할 것으로 예상됩니다.

편집 1 :

1) 두 사용자가 XY에 대해 언급! 포인트로부터 가중 그래프 (데이터 구조)를 만들고이 그래프를 사용하여 객체 (크기, 위치, 방향)를 찾고 싶습니다.

2) 한 사용자가 벡터화 계산에 댓글을 달았습니다. 매우 좋습니다. 그러나 PC에는 16GB RAM 만 있습니다. n ~ 100K로 계산을 벡터화하려면 128GB가 필요합니다!

3) O (n^2) 표기법 및 실행 시간에 대한 다른 사용자 의견. O (n^3)의 모든 peogram은 단지 loop보다 많은 시간이 걸립니다. 나는 단순한 루프가 122 초 걸릴 때 더 많은 라인을 추가하면 122 초 이상 걸린다 고 말하고 싶다. 0.1 초로 줄여야합니다 (최대 1 초까지 가능하지 않은 경우)

Answer 1

모든 N-1 점을 모두 비교해야합니까? 또는 서로 상대적으로 가까운 쌍의 점을 처리하는 것으로 충분합니까? 대부분의 물리적 현상은 분리가 증가함에 따라 급격히 감소하므로 먼 지점의 효과를 무시하거나 많은 수의 먼 지점의 결합 효과를 모두가 한 방향과 거리에있는 것처럼 생각할 수도 있습니다.

먼 지점을 효율적으로 클러스터링 할 수있는 동시에 가까운 지점을 효율적으로 찾을 수있는 옥타브와 같은 데이터 구조를 살펴보십시오.