효율성을 위해 코드 최적화

Question

유클리드 거리를 기반으로 한 벡터에서 다른 벡터로 점을 매핑하는 코드를 작성하고 올바르게 작동하는지 확인했습니다.

그러나 너무 많은 시간이 걸립니다. 본질적으로 나는 A와 B 벡터의 유클리드 거리에 대한 행렬을 만들고 그것의 최소값을 찾았습니다. 이 점의 매핑을 표시 한 후, 다음 매핑이 발생하기 위해 NaN으로 표시하여 유클리드 행렬의 행과 열을 삭제합니다. 그것은 지금 굉장히 느리기 때문에

이 코드는 ...

Euclid = distance(A,B); % calculates euclid distance column v/s column wise. 
for var = 1 : value 
    %# finds the min of Euclid and its position, when Euclid is viewed as a 1D array 
    [~, position] = min(Euclid(:)); 

    %#transform the index in the 1D view to 2 indices 
    [i,j] = ind2sub(size(Euclid),position); 

    %display(strcat(num2str(i),32, num2str(j))); 

    mapping = [A(1,i) A(2,i) B(1,j) B(2,j)]; 
    fprintf(FID,'%d %d %d %d\n', mapping); 

    Euclid(i , :) = NaN; 
    Euclid(: , j) = NaN; 
    %counter = counter + 1; 
end  

문제는 5000 X 5000 매트릭스의 코드는 단지 오랜 시간 동안 달려 있다는 것입니다 ... 더 효과적 일 수

누군가가 나를 도울 수 있습니까?

Answer 1

거리 배열을 1 차원 배열로 재구성하면 새로운 1 차원 인덱스가 어떻게 다시 1 차원 배열로 매핑되는지주의 깊게 기록 할 수 있습니다. 2 차원 색인. 그런 다음 1 차원 배열에서 정렬 함수를 호출하여 오름차순으로 정렬합니다. 정렬을 일으키는 인덱스의 순열을 저장 한 다음 정렬 순열의 1-D 좌표에 해당하는 2 차원 배열 좌표를 반드시 읽어야합니다. 이 방법을 사용하면 Matlab의 정렬 알고리즘이 유용 할 것이므로 인덱스 변경 사항을 신중하게 추적해야합니다.

이렇게하면 고려 대상에서 포인트를 제거 할 때 문제가 발생합니다. 이미 선택된 점에 대한 인덱스의 실행 목록을 유지해야하며, (1 차원 순열을 탐색 할 때) 이미 선택된 인덱스에 해당하는 것이 있으면 건너 뜁니다 (예 : NaN으로 설정하지 않으면 고려하지 않습니다.)

이렇게하면 매번 최소값을 계산하지 않아도됩니다. 1-D 정렬 치환을 가로 지르는 for-loop의 각 반복에서 유일한 실제 검사는 현재 위치가 이전에 선택되었는지 여부를 논리적으로 검사하는 것입니다 (점 중 하나가 더 작은 거리 위치에 관련되기 때문에). 반복 i에서이 검사는 최대 i-1 비교를 취하므로 O (n^2)보다 약간 작습니다.

이 방법은 매번 전체 배열의 최소값을 계산하지만 아래 링크에서 언급 한 O (n log n) 방법만큼 빠르지 않은 현재 방법보다 빠릅니다.

보다 일반적으로는 to this question에 링크 된 논문을 읽고 싶습니다. 이것은 사소한 문제는 아니며, RAM 집약적 인 Matlab 세션에는 적합하지 않으며 아마도이 모든 접근 방식을 다시 작성해야 할 것입니다.

또 다른 아이디어는 모든 배열 A을 일련의 프로세서에 브로드 캐스팅하면 어레이 B에있는 지점에 당황스럽게 병렬화된다는 것입니다. B 조각을 다른 프로세서에 보내고 모든 거리 목록을 가져올 수 있습니다. 헤드 노드에서 먼 거리에 대한 인덱스를 선택하고 그 포인트를 제거하기 위해 약간의 처리를해야하지만 너무 많이하지 않아야합니다. 아마 당신은 거리를 여러 번 계산할 필요가 없도록 그 부분을 다시 쓸 수 있습니다.

예를 들어 Python 또는 C++에서이 코드를 작성하면 MPI 라이브러리를 빠르게 사용하고 Amazon Web Services의 클라우드 클러스터 또는 액세스 할 수있는 경우 로컬 클러스터에서 실행할 수 있습니다.