희소 색인 생성에 대한 세부 정보

Question

나는 희소 색인 생성을 사용하는 코드를 가지고있다. 이 함수를 함수에서 실행하고 관련된 모든 변수의 크기가 변경되지 않는 두 가지 문제에 사용합니다. 그러나 한 가지 문제에 대해 스파 스 색인 생성 부분은 5 초가 걸리고 다른 한 부분은 25 초가 걸립니다.

관련된 모든 변수의 크기를 확인했는데 두 문제 모두에서 동일합니다. 또한 xv가 두 가지 문제 유형에 대한 전체 행렬임을 확인했습니다.

그래서 다른 누구도 이런 이상한 상황에 처했을까요? 이것이 일어날 이유에 대한 아이디어가 있습니까? 주로 코드를보다 효율적으로 만들려고 노력하고 있으며, 특정 응용 프로그램에 5 초가 걸리는 반면 25 초 (특히 설명 할 수없는 경우)는 매우 나쁩니다.

편집 : 다음은이 이상한 행동을 묘사하는 사진에 대한 링크입니다. 런타임 값은 세 번째 실행에서 기록되어 X의 크기도 변경되지 않도록합니다. 그리고 xv가 조밀 한 (희소하지 않은) 행렬인지 두 번 확인했습니다.

https://www.dropbox.com/s/i41j6afanzbjdyg/weird_bcd_thing.png?dl=0

덕분에 어떤 도움을 너무 많이!

아래 코드는 for 루프에서 실행됩니다. ptype = 1을 사용하면 5 초, ptype = 3은 25 초입니다.

clvec = cliques{k}; 
xcurr = full(X(clvec)); 
xv = reshape(xcurr - Z(offset_index(k) + 1 : offset_index(k) + ncl^2),ncl,ncl); 

%these two functions both take a dense symmetric matrix and return a dense symmetric matrix, and in both cases the size is the same for a given k. 
if ptype == 1 
    xv = proj_PSD(xv,0,0); 
elseif ptype == 3 
    xv = proj_Schoenberg(xv,0); 
end 
Xd = vec(xv) - xcurr; 

%THIS IS THE WEIRD LINE    
tic 
X(clvec) = xv; 
toc; 

Answer 1

'WEIRD LINE'에서 : X (clvec) = xv; 스파 스 매트릭스에 임의 액세스를 사용 중입니다. 스파 스 매트릭스에서이 액세스는 일정하지 않으며 데이터에 따라 다릅니다. 시간은 매트릭스 값과 액세스하려는 인덱스에 따라 달라질 수 있습니다. 일반적으로 안정적인 액세스 시간을 얻는 빠른 매트릭스의 경우에는 그렇지 않습니다. 안정적인 상수 액세스를 보장하려면 특정 매트릭스 사용량에 따라 구현을 변경하고 무작위 액세스로 할당 된 값을 피하십시오. 에 대한 참조로 다음 코드를 참조하십시오

---

X = sparse(randi(100,50,1),randi(100,50,1),randn(1),100,100); 
for i=1:10000 
    rand_inds{i} = randperm(10000,100); 
end 
for i=1:100 
    ti = tic; 
    X(rand_inds{i}) = 3; 
    to_X(i) = toc(ti);  
end 

Xf = full(X); 
for i=1:100 
    ti = tic; 
    Xf(rand_inds{i}) = 3; 
    to_Xf(i) = toc(ti);  
end 

figure;plot(to_X);hold on;plot(to_Xf,'r'); 

Answer 2

나는 내 문제를 해결! 나는 그것이 재미 있다고 생각하기 때문에 대답을 게시하고있다.

내가 언급하지 않은 한 가지는 루프가 k = 1에서 k = L로 바뀌고 ptype = 3 인 경우 하나 더 단계가 추가되어 모든 대각선 인덱스를 0으로 지정한다는 것입니다.

X(diag_index) = 0 

여기서 diag_index는 미리 계산됩니다.

문제는 0으로 값을 할당하는 대신 MATLAB이 자동으로 이러한 인덱스를 무시하고 다음 루프가 대각선 인덱스에 액세스 할 때 X에 대해 다시 할당해야한다는 것입니다.

X(diag_index) = eps; 

이제 둘 다 똑같이 빠르게 실행됩니다. (그것은 최선의 해결책은 나중에 오류의 원천이 될 것,하지만 더 이상 비밀이 없기 때문에, 아니에요!)

는 대답은 당신이 될 것이라고 생각 결코 ...