쌍방향 유클리드 거리를 찾는 빠른 알고리즘

Question

matlab에는 pairwise distance를 계산할 수있는 pdist 함수가 내장되어 있습니다. 그러나, 내 매트릭스는 너무 커서 60000 by 300과 matlab 메모리가 부족합니다.

이 질문은 후속 조치 Matlab euclidean pairwise square distance function입니다.

이 계산상의 비효율에 대한 해결 방법이 있습니까? 나는 pairwise 거리 계산을 수동으로 코딩하려고 시도했고, 보통 하루 종일 (때때로 6 ~ 7 시간) 걸립니다.

도움을 주시면 대단히 감사하겠습니다.

Answer 1

컴퓨터가 무한히 크거나 무한대로 빠르지는 않습니다. 사람들은 메모리가 크고 CPU가 많아서 크고 큰 문제를 만든 다음 결국 문제가 왜 천천히 실행되는지 궁금해합니다. 사실, 이것은 계산상의 비 능률이 아닙니다. 그것은 오버로드 된 CPU입니다.

올리 (Oli)가 의견에서 지적한 것처럼 거리 매트릭스의 위쪽 또는 아래쪽 절반 만 계산한다고 가정해도 계산할 2e9 값과 같은 것이 있습니다. (6e4^2/2는 약 2e9입니다.) 메모리에 하나의 배열 사본 만 생성되었다고 가정하면 약 16 기가의 RAM이 필요합니다. 코드가 엉성한 경우 쉽게 두 배 또는 세 배로 늘릴 수 있습니다. 가상 메모리에 들어가 자마자 상황이 훨씬 느려집니다.

빨리 달리는 데 큰 문제가있는 것은 아닙니다. 실제로 도움이 되려면 사용 가능한 RAM의 양을 알아야합니다. 가상 메모리 문제입니까? 필요한 모든 RAM을 처리 할 수있는 CPU에서 64 비트 MATLAB을 사용하고 있습니까?

Answer 2

글쎄, 나는 놀기를 거부 할 수 없었다. 저는 단 정밀도와 배정도를 위해 pairwise 유클리드 거리를 구현하는 pdistc이라는 Matlab mex C file을 만들었습니다. 내 컴퓨터에서 Matlab R2012b 및 R2015a를 사용하면 큰 입력 (예 : 60,000 x 300)의 경우 pdist (기본 도우미도우미 기능)보다 20 % 더 빨라 20 –입니다.

지적했듯이이 문제는 근본적으로 메모리에 국한되어 있으므로 많은 것을 요구하고 있습니다. 내 mex C 코드는 출력에 필요한 최소한의 메모리를 사용합니다. 메모리 사용량을 pdist의 메모리 사용량과 비교할 때 두 메모리가 거의 같아 보입니다. 즉, pdist은 많은 추가 메모리를 사용하지 않습니다. 메모리 문제는 메모리가 많아서 pdist (큰 배열을 제거하려면 clear을 사용할 수 있습니까?)을 호출하기 전에 사용했거나 작은 하드웨어에서 큰 계산 문제를 해결하려고하기 때문에 발생했을 수 있습니다.

따라서 pdistc 함수는 전체 메모리를 절약 할 수는 없지만 내장 된 다른 기능을 사용할 수는 있습니다. 전체 쌍 거리 벡터의 덩어리를 계산할 수 있습니다. 이런 식으로 뭔가 :

m = 6e3; 
n = 3e2; 
X = rand(m,n); 
sz = m*(m-1)/2; 

for i = 1:m:sz-m 
    D = pdistc(X', i, i+m); % mex C function, X is transposed relative to pdist 
    ...      % Process chunk of pairwise distances 
end 

이 상당히 느린 (10 회 정도) 내 C 코드의이 부분이 잘 최적화되어 있지 않습니다,하지만 당신은 필요하지 않습니다 가정 훨씬 적은 메모리 사용 –을 허용합니다 한 번에 전체 배열. pdist (또는 pdistc)을 사용하면 모두가 아닌 X의 하위 집합을 직접 전달한 루프를 만들어 훨씬 더 효율적으로 동일한 작업을 수행 할 수 있습니다.

64 비트 Intel Mac을 사용하는 경우 .mexmaci64 바이너리가 포함되어 있으므로 컴파일 할 필요가 없지만 컴퓨터 코드를 컴파일하는 방법을 알아야합니다. 나는 너를 도울 수 없어.컴파일 할 수 없거나 직접 코드를 편집하여 해결해야하는 호환성 문제가있을 수 있습니다. 버그가 있고 코드가 Matlab을 파괴 할 수도 있습니다. 또한 기계 엡실론 (eps)의 범위에서 차이가있는 pdist에 대해 약간 다른 출력이 나올 수 있습니다. pdist은 큰 입력 및 기타 숫자 문제로 인한 오버플로를 피하기 위해 멋진 일을 할 수도 있고하지 않을 수도 있지만 내 코드는 그렇지 않습니다.

또한 간단한 pure Matlab implementation을 만들었습니다. 그것은 mex 코드보다 훨씬 느리지 만 순진한 구현이나 pdist에있는 코드보다 빠릅니다.

모든 파일 can be found here. ZIP 아카이브에는 모든 파일이 포함됩니다. BSD 라이센스입니다. 자유롭게 느껴보십시오 (BLAS 호출과 OpenMP를 C 코드로 사용해 보았습니다. – 포인터 마술이나 GPU/OpenCL로 속도를 높일 수 있습니다). 나는 그것이 당신이나 다른 누군가에게 도움이되기를 바랍니다. 다음 내 시스템에서

Answer 3

는 (심지어 빠르게 C 코드 pdistc보다 @horchler으로) 가장 빠른 :

function [ mD ] = CalcDistMtx (mX)  
    vSsqX = sum(mX .^ 2); 
    mD = sqrt(bsxfun(@plus, vSsqX.', vSsqX) - (2 * (mX.' * mX)));  
end 

당신이 이길 수있는 아주 잘 조정 된 C 코드가 필요합니다, 나는 생각한다. squareform(pdist(mX.'))CalcDistMtx(mX)하는 것과 같습니다 MATLAB의 비교 pdist가 사용

P. S.
.
즉, 입력을 전치해야합니다.