내가 좋아하는 코드 블록을 수행 할 필요가

Question

너무 계산 비용이 다음

x = some_number; 
y = some_other_number; 

u = a_vector_of_numbers; 
v = another_vector_of_numbers; 
% u and v are of equal size 

r1 = ((x == u) | (x == v)); % Expensive! 
r2 = ((y == u) | (y == v)); % Expensive! 

q = any(r1 & r2); 

당신은로 생각할 수 있습니다

: x 및 y 그래프에 두 개의 노드, 그리고 나는하지 않는 한 착각하면 인접 목록 인 [r1, r2]을 사용하여 x과 y이 연결되어 있는지 확인합니다. 즉, 질문에 대한 대답을 시도합니다. "ir1(i) 또는 r2(i)에 x과 y 두 가지를 찾을 수 있습니까?"

이 작업을 반복해야합니다. r1과 r2은 모두 수천 개의 고유 값 (1의 순서로 그래프에있는 노드 수)을 포함 할 수 있으며 길이는 수십만 (1 정도의 가장자리 수)입니다.

내 프로파일 러는 주석으로 표시 한 두 줄은 실행 시간의 99 %를 소비하며 프로그램 실행에는 상당한 시간이 걸리므로 궁금합니다. 얼마나 더 최적화 할 수 있습니까? 최소한의 계산 시간에 대한 근본적인 제한은 무엇이며, 그것과 얼마나 가깝습니까?

또한이 특정 코드를 다른 언어로 아웃소싱하는 것이 매우 쉽습니다. 상당한 성능 향상을 가져올 수 있습니까?

Answer 1

나는

당신이 당신의 그래프에 대한 인접 행렬을 작성하고 귀하의 문의를 위해 그것을 사용하여 시도 해 봤나 ...이 제안, 일부 사실적인 테스트 데이터를 설정하는 너무 많은 노력을 테스트,하지만하지? 매트릭스를 생성하는 것은 비교적 비싼 작업이지만 가장자리가 있는지 확인하는 것은 두 인접 목록을 모두 읽는 것보다 훨씬 저렴합니다 (필자는 생각합니다).

현재의 알고리즘 (또는 더 중요한 것은 현재 데이터 구조)을 고수한다면 단순히 다른 언어로 구현 된 코드로 작업 속도를 높이면 훨씬 놀랄 것입니다. 다른 언어를 사용해도 값을 찾고있는 긴 벡터 벡터를 읽는 것은 변하지 않습니다.

Answer 2

첫 번째 검사()가 대부분의 결과를 제거하는 경우 두 번째 검사를 미리 필터링하여 가능한 일치 항목 만 검사하도록 할 수 있습니다. 그에 대한 코드는 다음과 같습니다

mask_r1 = ((x == u) | (x == v)); % Expensive! 
r2 = ((y == u(mask_r1)) | (y == v(mask_r1))); % Less expensive! 
q = any(r2); 

심지어 본 경우를 첫 번째 줄 성능 향상에 find를 추가, (일반적으로 matlab에 이전 버전에서). 그러나 나는 더 이상 사실이 아니라고 생각합니다. (파서로 그 최적화를 가져 왔습니다.) 세 가지 방법 (원래, 논리 마스크를 사용하고 명시 적 인덱스 목록을 사용하여)의 일부 타이밍 결과는 다음과 같습니다.

x = 2; 
y = 3; 
v = randi(200,1e5,1); 
u = randi(200,1e5,1); 

tic; 
for ix = 1:1000 
    r1 = ((x == u) | (x == v)); % Expensive! 
    r2 = ((y == u) | (y == v)); % Expensive! 
    q = any(r1 & r2); 
end 
toc; %1.175234 


tic; 
for ix = 1:1000 
    mask_r1 = ((x == u) | (x == v)); % Expensive! 
    r2 = ((y == u(mask_r1)) | (y == v(mask_r1))); % Less expensive! 
    q = any(r2); 
end 
toc; %0.878857 

tic; 
for ix = 1:1000 
    ixs_r1 = find(((x == u) | (x == v))); % Expensive! 
    r2 = ((y == u(r1)) | (y == v(r1))); % Less expensive! 
    q = any(r2); 
end 
toc; %1.118103