forループに関する計算速度について

簡単な数値計算をfor文で作成したのち、ある程度複雑化してくると計算時間が長くなってきます。

そんなときfor文を単純な配列計算になおすと速度向上される場合があるのですが、

計算速度がなぜそこまで変化するのかがわかりません。

例えば1×Nの配列Xについて各要素の二乗を計算してYに格納しようとしたとします。

その場合

Y=zeros(1,N);

for i=1,N

Y(i)=X(i)^2;

end

というコードを作成するのと

Y=X.*X

と計算するのでは計算速度はどのくらい早くなるのでしょうか。

またその速度差はmatlab上でどういった手順で計算することで発生しているのでしょうか。

Answer 1

[Kojiro Saito]

質問のforループと配列演算の計算速度についてですが、

N = 10の場合、forループ(t1)だと1.6907e-06 sec、配列演算(t2)だと1.8452e-07 sec。

N = 1000の場合、t1 = 2.4441e-06、t2 = 5.7508e-07

N = 100000の場合、t1 = 2.2313e-04、t2 = 2.2722e-05

N = 10000000の場合、t1 = 0.0306、t2 = 0.0172

の結果となったので、Nの値にも寄りますがforループから配列演算にすることで、10倍から2倍くらいは速くなります。

ticのドキュメントによると、実行時間が0.1 sec以下の場合は厳密に測定できないので、timeitを使って測定しています。

測定コード

clear
N = 10;
X = randn([1,N]);
f = @() forLoopFunc(X, N);
t1 = timeit(f, 1)

f = @() vectorizedFunc(X);
t2 = timeit(f, 1)

%% function definition
function Y = forLoopFunc(X, N)
    Y=zeros(1,N);
    for i = 1:N
        Y(i) = X(i) ^ 2;
    end
end

function Y = vectorizedFunc(X)
    Y=X.*X;
end

MATLABは配列・ベクトル演算の内部実装で高速化、最適化されたライブラリを使用しています。forループだと要素ごとの処理となってしまいその恩恵が受けられないのですが、Y=X.*Xのように配列演算でおこなうとその恩恵が大きいためです。

ただ、リリースノートのPerformanceのカテゴリにあるように、forループでも関数によってはバージョンアップで劇的に速くなっているものもあります。

2006年の記事で古いですが、配列演算についてはこちらも参考になるかもしれません。

Answer 2

[Atsushi Ueno]

>計算速度はどのくらい早くなるのでしょうか。

単純に、MATLAB上で実行してみました

N = 10000000;
X = randi(N,[1,N]);
tic; for i = 1:N, Y(i) = X(i) ^ 2; end
toc;
tic; Y=X.*X; toc;

local PC(R2017a@windows)での実行結果

経過時間は 0.051485 秒です。

経過時間は 0.011703 秒です。

MATLAB online(R2021a@linux)での実行結果

経過時間は 0.222043 秒です。

経過時間は 0.038554 秒です。

実行時間は様々な条件で異なります。メカニズムを逐一解明すれば「こっちの方が何ステップ早くなる」と断言できますが、マルチタスクOS上では実行する度に上記時間が変動してしまい、理論通りの時間短縮を再現する事は出来ません。

>またその速度差はmatlab上でどういった手順で計算することで発生しているのでしょうか。

私自身がMATLABの手順を確認した事が無いので直接の回答を控えます。

下記はtimes.mの内容です。下記ソースコードはコメントのみで、実体はオブジェクトファイルとしてしか存在しないのでしょう。つまりMATLABに組み込まれた演算子のソースコードは閲覧できないと思います。

%.*  Array multiply.
%   X.*Y denotes element-by-element multiplication. X and Y must have
%   compatible sizes. In the simplest cases, they can be the same size or
%   one can be a scalar. Two inputs have compatible sizes if, for every
%   dimension, the dimension sizes of the inputs are either the same or one
%   of them is 1.
%
%   C = TIMES(A,B) is called for the syntax 'A .* B' when A or B is an
%   object.
%
%   See also MTIMES.

%   Copyright 1984-2015 The MathWorks, Inc.

高速化プログラミングについて下記のような知識を得る事をお勧めします。

高速化プログラミング (webサイト)

高速化プログラミング入門 (書籍)

MATLABの高速化についてもドキュメントは豊富にあります。

パフォーマンスとメモリ - MATLAB & Simulink - MathWorks 日本