빈 행렬 곱셈을 통해 배열을 초기화하는 더 빠른 방법? (매트랩)
나는 Matlab이 빈 행렬을 다루는 이상한 방식을 우연히 발견했습니다 . 예를 들어, 두 개의 빈 행렬을 곱하면 결과는 다음과 같습니다.
zeros(3,0)*zeros(0,3)
ans =
0 0 0
0 0 0
0 0 0
자, 이것은 이미 저를 놀라게했습니다. 그러나 빠른 검색을 통해 위의 링크로 연결되었고 왜 이런 일이 일어나는지에 대한 다소 왜곡 된 논리에 대한 설명을 얻었습니다.
그러나 다음과 같은 관찰에 대비 한 것은 아무것도 없습니다. 나는 zeros(n)초기화 목적으로 이러한 유형의 곱셈이 함수를 사용 하는 것과 비교하여 얼마나 효율적 입니까? 나는 이것을 timeit대답 하는 데 사용 했습니다.
f=@() zeros(1000)
timeit(f)
ans =
0.0033
대 :
g=@() zeros(1000,0)*zeros(0,1000)
timeit(g)
ans =
9.2048e-06
둘 다 class의 0으로 구성된 1000x1000 행렬의 결과가 동일 double하지만 빈 행렬 곱셈 1은 ~ 350 배 더 빠릅니다! ( tic및 toc및 루프를 사용하여 유사한 결과가 발생 합니다)
어떻게 이럴 수있어? 있습니다 timeit또는 tic,toc허풍 또는 내가 행렬을 초기화하는 빠른 방법을 발견했다? (이것은 win7-64 시스템, intel-i5 650 3.2Ghz에서 matlab 2012a로 수행되었습니다 ...)
편집하다:
여러분의 피드백을 읽은 후, 저는이 특징을 좀 더주의 깊게 살펴보고 실행 시간과 행렬 n의 크기를 검사하는 코드를 두 대의 다른 컴퓨터 (2012a의 동일한 matlab 버전)에서 테스트했습니다. 이것이 내가 얻는 것입니다.
이것을 생성하는 코드 timeit는 이전과 같이 사용 되었지만 tic및 루프 toc는 동일하게 보입니다. 따라서 작은 크기의 경우 zeros(n)비슷합니다. 그러나 n=400빈 행렬 곱셈에 대한 성능이 뛰어납니다. 해당 플롯을 생성하는 데 사용한 코드는 다음과 같습니다.
n=unique(round(logspace(0,4,200)));
for k=1:length(n)
f=@() zeros(n(k));
t1(k)=timeit(f);
g=@() zeros(n(k),0)*zeros(0,n(k));
t2(k)=timeit(g);
end
loglog(n,t1,'b',n,t2,'r');
legend('zeros(n)','zeros(n,0)*zeros(0,n)',2);
xlabel('matrix size (n)'); ylabel('time [sec]');
여러분도 이것을 경험하고 있습니까?
# 2 수정 :
덧붙여서,이 효과를 얻기 위해 빈 행렬 곱셈이 필요하지 않습니다. 간단하게 다음을 수행 할 수 있습니다.
z(n,n)=0;
여기서 n> 이전 그래프에 표시된 일부 임계 값 행렬 크기, 빈 행렬 곱셈 (다시 timeit 사용)에서와 같이 정확한 효율성 프로필을 얻습니다 .
다음은 코드의 효율성을 향상시키는 예입니다.
n = 1e4;
clear z1
tic
z1 = zeros( n );
for cc = 1 : n
z1(:,cc)=cc;
end
toc % Elapsed time is 0.445780 seconds.
%%
clear z0
tic
z0 = zeros(n,0)*zeros(0,n);
for cc = 1 : n
z0(:,cc)=cc;
end
toc % Elapsed time is 0.297953 seconds.
그러나 z(n,n)=0;대신 사용 하면 zeros(n)케이스 와 유사한 결과가 생성 됩니다.
이것은 이상합니다. f는 더 빠르고 g는 여러분이보고있는 것보다 느립니다. 그러나 둘 다 나에게 동일합니다. 다른 버전의 MATLAB일까요?
>> g = @() zeros(1000, 0) * zeros(0, 1000);
>> f = @() zeros(1000)
f =
@()zeros(1000)
>> timeit(f)
ans =
8.5019e-04
>> timeit(f)
ans =
8.4627e-04
>> timeit(g)
ans =
8.4627e-04
편집 하면 f와 g의 끝에 + 1을 더할 수 있고 몇 시간인지 확인할 수 있습니다.
2013 년 1 월 6 일 7:42 EST 수정
나는 기계를 원격으로 사용하고있다. 그래서 낮은 품질의 그래프에 대해 유감이다.
머신 구성 :
i7 920. 2.653GHz. 리눅스. 12GB RAM. 8MB 캐시.
더 큰 크기 (1979 년에서 2073 년 사이)를 제외하고는 내가 액세스 할 수있는 컴퓨터에서도 이러한 동작이 나타나는 것 같습니다. 지금 당장 빈 행렬 곱셈이 더 큰 크기에서 더 빨라질 것이라고 생각할 이유가 없습니다.
돌아 오기 전에 좀 더 조사 할 것입니다.
2013 년 1 월 11 일 수정
@EitanT의 포스트 이후, 좀 더 파고 싶었습니다. matlab이 0 행렬을 만드는 방법을보기 위해 C 코드를 작성했습니다. 다음은 내가 사용한 C ++ 코드입니다.
int main(int argc, char **argv)
{
for (int i = 1975; i <= 2100; i+=25) {
timer::start();
double *foo = (double *)malloc(i * i * sizeof(double));
for (int k = 0; k < i * i; k++) foo[k] = 0;
double mftime = timer::stop();
free(foo);
timer::start();
double *bar = (double *)malloc(i * i * sizeof(double));
memset(bar, 0, i * i * sizeof(double));
double mmtime = timer::stop();
free(bar);
timer::start();
double *baz = (double *)calloc(i * i, sizeof(double));
double catime = timer::stop();
free(baz);
printf("%d, %lf, %lf, %lf\n", i, mftime, mmtime, catime);
}
}
결과는 다음과 같습니다.
$ ./test
1975, 0.013812, 0.013578, 0.003321
2000, 0.014144, 0.013879, 0.003408
2025, 0.014396, 0.014219, 0.003490
2050, 0.014732, 0.013784, 0.000043
2075, 0.015022, 0.014122, 0.000045
2100, 0.014606, 0.014480, 0.000045
보시다시피 calloc(4 번째 열)이 가장 빠른 방법 인 것 같습니다. 또한 2025 년에서 2050 년 사이에 상당히 빨라지고 있습니다 (약 2048?).
이제 동일한 사항을 확인하기 위해 matlab으로 돌아갔습니다. 결과는 다음과 같습니다.
>> test
1975, 0.003296, 0.003297
2000, 0.003377, 0.003385
2025, 0.003465, 0.003464
2050, 0.015987, 0.000019
2075, 0.016373, 0.000019
2100, 0.016762, 0.000020
f ()와 g () 모두 calloc더 작은 크기 (<2048?)에서 사용하는 것처럼 보입니다 . 그러나 더 큰 크기에서 f () (zeros (m, n))은 malloc+ 를 사용하기 시작 memset하고 g () (zeros (m, 0) * zeros (0, n))는 calloc.
따라서 차이는 다음과 같이 설명됩니다.
- 0 (..)은 더 큰 크기에서 다른 (느린?) 체계를 사용하기 시작합니다.
calloc또한 다소 예기치 않게 작동하여 성능이 향상됩니다.
이것은 Linux에서의 동작입니다. 누군가 다른 컴퓨터 (및 아마도 다른 OS)에서 동일한 실험을 수행하고 실험이 유지되는지 확인할 수 있습니까?
결과는 약간 오해의 소지가 있습니다. 두 개의 빈 행렬을 곱하면 결과 행렬이 즉시 "할당"되고 "초기화"되는 것이 아니라 처음 사용할 때까지 연기됩니다 (지연 평가와 유사).
변수 를 늘리기 위해 범위를 벗어나 인덱싱 할 때도 마찬가지입니다. 숫자 배열의 경우 누락 된 항목을 0으로 채 웁니다 (이후에 숫자가 아닌 경우에 대해 설명합니다). 물론 이런 식으로 행렬을 늘려도 기존 요소를 덮어 쓰지 않습니다.
따라서 더 빠르게 보일 수 있지만 실제로 매트릭스를 처음 사용할 때까지 할당 시간을 지연시키는 것입니다. 결국 당신은 처음부터 할당을 한 것처럼 비슷한 타이밍을 갖게 될 것입니다.
다른 몇 가지 대안 과 비교하여이 동작을 보여주는 예 :
N = 1000;
clear z
tic, z = zeros(N,N); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
tic, z = zeros(N,0)*zeros(0,N); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
tic, z(N,N) = 0; toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
tic, z = full(spalloc(N,N,0)); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
tic, z(1:N,1:N) = 0; toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
val = 0;
tic, z = val(ones(N)); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
clear z
tic, z = repmat(0, [N N]); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))
결과는 각 경우에 두 지침에 대한 경과 시간을 합산하면 비슷한 총 타이밍이됩니다.
// zeros(N,N)
Elapsed time is 0.004525 seconds.
Elapsed time is 0.000792 seconds.
// zeros(N,0)*zeros(0,N)
Elapsed time is 0.000052 seconds.
Elapsed time is 0.004365 seconds.
// z(N,N) = 0
Elapsed time is 0.000053 seconds.
Elapsed time is 0.004119 seconds.
다른 타이밍은 다음과 같습니다.
// full(spalloc(N,N,0))
Elapsed time is 0.001463 seconds.
Elapsed time is 0.003751 seconds.
// z(1:N,1:N) = 0
Elapsed time is 0.006820 seconds.
Elapsed time is 0.000647 seconds.
// val(ones(N))
Elapsed time is 0.034880 seconds.
Elapsed time is 0.000911 seconds.
// repmat(0, [N N])
Elapsed time is 0.001320 seconds.
Elapsed time is 0.003749 seconds.
이러한 측정은 밀리 초 단위로 너무 작아서 매우 정확하지 않을 수 있으므로 이러한 명령을 루프에서 수천 번 실행하고 평균을 계산할 수 있습니다. 또한 때때로 저장된 M- 함수를 실행하는 것이 스크립트 나 명령 프롬프트를 실행하는 것보다 빠릅니다. 특정 최적화는 그런 방식으로 만 발생하기 때문입니다.
어느 쪽이든 할당은 일반적으로 한 번 수행되므로 추가 30ms가 걸리면 누가 신경 쓰겠습니까? :)
유사한 동작은 셀형 배열 또는 구조 배열에서 볼 수 있습니다. 다음 예를 고려하십시오.
N = 1000;
tic, a = cell(N,N); toc
tic, b = repmat({[]}, [N,N]); toc
tic, c{N,N} = []; toc
다음을 제공합니다.
Elapsed time is 0.001245 seconds.
Elapsed time is 0.040698 seconds.
Elapsed time is 0.004846 seconds.
모두 동일하더라도 다른 양의 메모리를 차지합니다.
>> assert(isequal(a,b,c))
>> whos a b c
Name Size Bytes Class Attributes
a 1000x1000 8000000 cell
b 1000x1000 112000000 cell
c 1000x1000 8000104 cell
실제로 MATLAB은 여러 복사본을 생성하는 대신 모든 셀에 대해 동일한 빈 행렬을 공유 하기 때문에 상황이 좀 더 복잡합니다 .
셀형 배열 a은 실제로 초기화되지 않은 셀의 배열 (NULL 포인터 b배열)이고 각 셀이 빈 배열 인 셀형 배열입니다 [](내부적으로 데이터 공유로 인해 첫 번째 셀만 b{1}가리키고 []나머지는 모두 첫 번째 셀에 대한 참조). 최종 배열 c은 a(초기화되지 않은 셀) 과 유사하지만 마지막 배열 은 빈 숫자 형 행렬을 포함합니다 [].
libmx.dll( Dependency Walker 도구 사용) 에서 내 보낸 C 함수 목록을 살펴 보았는데 몇 가지 흥미로운 점을 발견했습니다.
이 초기화되지 않은 배열을 만들기위한 문서화되지 않은 기능은 다음과 같습니다
mxCreateUninitDoubleMatrix,mxCreateUninitNumericArray그리고mxCreateUninitNumericMatrix. 사실 파일 교환 에 대한 제출 은 이러한 기능을 사용하여 기능에 대한 더 빠른 대안을 제공zeros합니다.라는 문서화되지 않은 함수가
mxFastZeros있습니다. 온라인 검색을 통해이 질문을 MATLAB Answers에 교차 게시 한 것을 볼 수 있습니다. James Tursa (이전의 UNINIT의 동일한 저자) 가이 문서화되지 않은 함수를 사용하는 방법에 대한 예제 를 제공했습니다.libmx.dlltbbmalloc.dll공유 라이브러리에 연결 됩니다. 이것은 Intel TBB 확장 가능 메모리 할당 자입니다. 이 라이브러리는 메모리 할당 동등한 기능을 제공한다 (malloc,calloc,free) 병렬 어플리케이션에 최적화. 많은 MATLAB 함수는 자동으로 다중 스레드 되므로zeros(..)행렬 크기가 충분히 크면 다중 스레드이고 Intel의 메모리 할당자를 사용하는 경우 놀라지 않을 것 입니다 ( 이 사실을 확인 하는 Loren Shure의 최근 댓글입니다 ).
메모리 할당 자에 대한 마지막 요점과 관련하여 @PavanYalamanchili 가 한 것과 유사한 C / C ++로 유사한 벤치 마크를 작성하고 사용 가능한 다양한 할당자를 비교할 수 있습니다. 이와 같은 것 . MEX-파일이 약간 더 높은이 기억 메모리 관리 MATLAB에서 자동으로 사용 MEX-파일에 할당 된 모든 메모리를 해제하기 때문에, 오버 헤드 mxCalloc, mxMalloc또는 mxRealloc기능을. 그만한 가치가 있기 때문에 이전 버전에서 내부 메모리 관리자 를 변경할 수 있었습니다.
편집하다:
다음은 논의 된 대안을 비교하기위한보다 철저한 벤치 마크입니다. 특히 할당 된 전체 행렬의 사용을 강조하면 세 가지 방법이 모두 동일한 기반에 있고 그 차이는 무시할 수 있음을 보여줍니다.
function compare_zeros_init()
iter = 100;
for N = 512.*(1:8)
% ZEROS(N,N)
t = zeros(iter,3);
for i=1:iter
clear z
tic, z = zeros(N,N); t(i,1) = toc;
tic, z(:) = 9; t(i,2) = toc;
tic, z = z + 1; t(i,3) = toc;
end
fprintf('N = %4d, ZEROS = %.9f\n', N, mean(sum(t,2)))
% z(N,N)=0
t = zeros(iter,3);
for i=1:iter
clear z
tic, z(N,N) = 0; t(i,1) = toc;
tic, z(:) = 9; t(i,2) = toc;
tic, z = z + 1; t(i,3) = toc;
end
fprintf('N = %4d, GROW = %.9f\n', N, mean(sum(t,2)))
% ZEROS(N,0)*ZEROS(0,N)
t = zeros(iter,3);
for i=1:iter
clear z
tic, z = zeros(N,0)*zeros(0,N); t(i,1) = toc;
tic, z(:) = 9; t(i,2) = toc;
tic, z = z + 1; t(i,3) = toc;
end
fprintf('N = %4d, MULT = %.9f\n\n', N, mean(sum(t,2)))
end
end
Below are the timings averaged over 100 iterations in terms of increasing matrix size. I performed the tests in R2013a.
>> compare_zeros_init
N = 512, ZEROS = 0.001560168
N = 512, GROW = 0.001479991
N = 512, MULT = 0.001457031
N = 1024, ZEROS = 0.005744873
N = 1024, GROW = 0.005352638
N = 1024, MULT = 0.005359236
N = 1536, ZEROS = 0.011950846
N = 1536, GROW = 0.009051589
N = 1536, MULT = 0.008418878
N = 2048, ZEROS = 0.012154002
N = 2048, GROW = 0.010996315
N = 2048, MULT = 0.011002169
N = 2560, ZEROS = 0.017940950
N = 2560, GROW = 0.017641046
N = 2560, MULT = 0.017640323
N = 3072, ZEROS = 0.025657999
N = 3072, GROW = 0.025836506
N = 3072, MULT = 0.051533432
N = 3584, ZEROS = 0.074739924
N = 3584, GROW = 0.070486857
N = 3584, MULT = 0.072822335
N = 4096, ZEROS = 0.098791732
N = 4096, GROW = 0.095849788
N = 4096, MULT = 0.102148452
After doing some research, I've found this article in "Undocumented Matlab", in which Mr. Yair Altman had already come to the conclusion that MathWork's way of preallocating matrices using zeros(M, N) is indeed not the most efficient way.
He timed x = zeros(M,N) vs. clear x, x(M,N) = 0 and found that the latter is ~500 times faster. According to his explanation, the second method simply creates an M-by-N matrix, the elements of which being automatically initialized to 0. The first method however, creates x (with x having automatic zero elements) and then assigns a zero to every element in x again, and that is a redundant operation that takes more time.
In the case of empty matrix multiplication, such as what you've shown in your question, MATLAB expects the product to be an M×N matrix, and therefore it allocates an M×N matrix. Consequently, the output matrix is automatically initialized to zeroes. Since the original matrices are empty, no further calculations are performed, and hence the elements in the output matrix remain unchanged and equal to zero.
Interesting question, apparently there are several ways to 'beat' the built-in zeros function. My only guess as to why this is happening would be that it could be more memory efficient (after all, zeros(LargeNumer) will sooner cause Matlab to hit the memory limit than form a devestating speed bottleneck in most code), or more robust somehow.
희소 행렬을 사용하는 또 다른 빠른 할당 방법은 다음과 같습니다. 일반 0 함수를 벤치 마크로 추가했습니다.
tic; x=zeros(1000,1000); toc
Elapsed time is 0.002863 seconds.
tic; clear x; x(1000,1000)=0; toc
Elapsed time is 0.000282 seconds.
tic; x=full(spalloc(1000,1000,0)); toc
Elapsed time is 0.000273 seconds.
tic; x=spalloc(1000,1000,1000000); toc %Is this the same for practical purposes?
Elapsed time is 0.000281 seconds.
'Nice programing' 카테고리의 다른 글
| Psql 출력에서 결과 집합 장식을 숨기는 방법 (0) | 2020.12.01 |
|---|---|
| xUnit.net의 모든 테스트 전후에 한 번 코드 실행 (0) | 2020.12.01 |
| Vim에 NERD Commenter를 사용하는 방법 — 사용 방법 (0) | 2020.12.01 |
| NotifyIcon은 응용 프로그램을 닫은 후에도 트레이에 남아 있지만 마우스를 가리키면 사라집니다. (0) | 2020.12.01 |
| Android Studio에서 기존 프로젝트를 라이브러리 프로젝트로 변환 (0) | 2020.12.01 |