2012年2月10日金曜日

matlab: find いらずの一発参照・代入

matlab では,配列の要素のうち特定の条件を満たすものを参照する際,ものすごく効率的な方法が用意されている.それが Logical Subscripting だ(logical indexing という人もいる).基本的な説明は Matlab の help の Getting Started や mathworks のページにも載っているが,もう少し掘り下げてみよう.

ここでいう Logical とは,論理値配列の意味の論理である.早速やってみよう.

例: 行列 A のうち,値が 0.5 未満の要素は 0 にする.閾値処理ですな.
>> A = rand(3)
A =
    0.8147    0.9134    0.2785
    0.9058    0.6324    0.5469
    0.1270    0.0975    0.9575

>> A(A<0.5) = 0
A =
    0.8147    0.9134         0
    0.9058    0.6324    0.5469
         0         0    0.9575

その通り,find は使わなくてよいのである.今まで使いまくってたよ‥
A(find(A<0.5)) = 0
とか書いてたよ‥.はずかちー.

[多次元インデクス自体については matlab: 一目で分かる多次元インデクス をどうぞ]

もちろん,A の参照に A に関する論理式を使う必要はない.他のものでも使える.
例:同サイズの別配列による条件づけ
>> Score = [60,55,80]
Score =
    60    55    80

>> Effort = [50,75,60]
Effort =
    50    75    60

>> Score(Effort>70) = Score(Effort>70) + 20
Score =
    60    75    80

頑張った人に+20点とかね.Score(Effort>70)が2回出てくるのがなんとも野暮ったいけど,何とかならないだろうか?以下,速度と効率を追求してみよう.

* 速度の検討

logical は比較的小さい容量になる(1byte/element)ので,保存して使いまわしてもよさそうだ.

例: 大きな配列の論理参照における論理配列の使いまわしの効果


>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;S1(S>0.5)=S(S>0.5)+2;T(n)=toc;end;mean(T)
ans =
    1.7190

>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;LS=S>0.5;S1(LS)=S(LS)+2;T(n)=toc;end;mean(T)
ans =
    1.3880

2割以上速くなる.ちなみに,自分の過去のやり方(findする)だと

>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;IS=find(S>0.5);S1(IS)=S(IS)+2;T(n)=toc;end;mean(T)
ans =
    1.6312

あれ?意外と速い.個数の問題か?




例: 参照個数による処理時間の変化(find vs. logical subscripting)


>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;IS=find(S>0.9);S1(IS)=S(IS)+2;T(n)=toc;end;mean(T)
ans =
    0.6060

うおっ.てきめん.一方の logical subscripting はどうか?

>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;LS=S>0.9;S1(LS)=S(LS)+2;T(n)=toc;end;mean(T)
ans =
    0.6400

>> S=rand(5000);S1=S;N=10;T=zeros(N,1);
>> for n=1:N,tic;LS=S>0.1;S1(LS)=S(LS)+2;T(n)=toc;end;mean(T)
ans =
    1.1668

な ん で だ よ
なんで速度に差が出るのよ.たとえば,裏で find や sparse 的なことをしてて,対象個数が少ないほうに合わせてどうこうしてるのか?

条件に引っかかる個数を減らしながら,かかる時間をプロットしてみよう.

例: 参照個数による処理時間の変化(Logical Subscripting)

>> S=rand(5000);S1=S;N=4;LN=15;LVLs=linspace(0,1,LN);T=zeros(N,LN);
>> for ln=1:LN,for n=1:N,tic;LS=S>LVLs(ln);S1(LS)=S(LS)+2;T(n,ln)=toc;end;end;
>> figure;plot(LVLs,mean(T,1),'o-','linewidth',3);set(gca,'fontsize',20);grid on;
>> ylabel('elapsed time');xlabel('the threshold used');
>> print(gcf,'-dpng','logical_subscripting_etimes');

そうしてできたプロットがこれである.

参照される要素数が,
多い(グラフ左):半分より多くなるほど線形に速くなるが,係数は小さい.
半分(グラフ中央):一番遅い
少ない(グラフ右):半分より少なくなるほど,おおむね比例的に速くなる.
という結果が得られた.

例: 参照個数による処理時間の変化(find)

>> S=rand(5000);S1=S;N=4;LN=15;LVLs=linspace(0,1,LN);T=zeros(N,LN); >> for ln=1:LN,for n=1:N,tic;IS=find(S>LVLs(ln));S1(IS)=S(IS)+2;T(n,ln)=toc;end;end;
>> figure;plot(LVLs,mean(T,1),'o-','linewidth',3);set(gca,'fontsize',20);grid on;
>> ylabel('elapsed time');xlabel('the threshold used');
>> print(gcf,'-dpng','find_etimes');
find でやると素直に

要素が少なくなると処理が早く済む,となる.
二つの結果を重ねると
基本的には logical subscripting を使っていればよさそうだ.要素が少なくなってくると find がわずかに早いこともあるが,その差は微小だ.


logical subscripting の挙動の理由はいまいちわかりませんが,パフォーマンスにこだわる方は参考にしてみてください.ちなみに,R2007b on Win7 x64 on core2duo (mobile) です.

*プログラミング上の性質の検討


この Logical Subscripting の要点は,まさに logical 型の配列を括弧内に与えることにある.カッコ内に与えられた配列が logical かどうかはちゃんとチェックされ,数値 0 と論理値 false は区別される.
例:0 と false の区別
>> a=1
a =
     1

>> a(0)=3
??? Subscript indices must either be real positive
integers or logicals.

>> a(logical(0))=3
a =
     1

>> a(logical(1))=3
a =
     3

また,少なくとも R2007b では,参照に使う論理配列は,元の配列より小さくてもよいようだ.

例:参照に使う論理配列と入れ物の配列の大小

>> B=reshape([1:6],[3,2])
B =
     1     4
     2     5
     3     6

>> B(logical([0,0,0,1]))=9
B =
     1     9
     2     5
     3     6

逆に,大きいと怒られる.

>> B(logical([0,0,0,0,0,0,1]))=9
???  In an assignment  A(I) = B, a matrix A cannot
be resized.

ご参考まで.

-- 当ブログの matlab 関係へはこちらからどうぞ.--

2 件のコメント:

  1. 興味深い結果のご紹介ありがとうございます。
    気になったので追調査したところ、次のような結果が得られました。

    冒頭の S=rand(5000); を次に差し替える。
    S = reshape(linspace(0, 1, 5000.^2), 5000, 5000);

    つまりSは、[0, 1]区間を5000^2個に分割した等差数列を、
    2次元行列に整形したものです。この行列の重要な性質は、
    コンピュータのメモリ上での表現において、
    数値が大きい順にならんでいることです。

    この S に対してご提示の処理とプロットを行うと、
    処理時間結果は(通常想定されるような)ほぼ線形になります。

    この結果から次のようなことが起きていると予想します;

    1) MATLABはLogical Subscriptingを複数の要素を同時に処理している
      おそらくこれはSIMD命令による処理に由来すると考えられる
    2) たとえば8要素を同時に処理する場合、
      すべての要素についてLogical Subscriptingが0または1のときは
      処理を簡単にすることができる。
      つまり、8要素をスキップするか、8要素すべてを計算すればよい。
    3) (2)ではない場合、Logical Subscriptingの0/1の状況により、
      8要素の一部分を計算して、部分的に置き換えるという追加の処理が
      必要になる。これは数値演算処理よりも高負荷になる可能性がある。

    4) ご提示のコードは、Logical Subscriptingの状態を確率的に決定する。
      そのため、th=0.5のとき、0/1の混合状態がもっとも乱雑になり、
      上記(3)に該当する処理の量が多くなる→したがって計算量が増える。
    5) th=0 より th=1 のほうが処理時間が少ないのは、
      th=1 のときはLogical Subscriptingへのメモリアクセスが支配的であるのに対し
      th=0 のときは数値行列と計算が支配的になることによる。
      Logical Subscripting行列は1バイトで8要素分格納できることから、
      メモリアクセス効率が良い。

    以上ご参考になれば幸いです。
    貴重な記事ありがとうございました。

    返信削除
    返信
    1. うわっ,ほんとにほぼリニアな単調になった(グラフを見ながら)!
      鋭いコメントありがとうございます.検証までして頂いて感激です!勉強になります.

      なるほど,SIMD に由来する同時処理要素数の単位内で,どれだけ同じ処理が揃っているかがまず問題になってくる(のであろう)ということですね.うなづけます.SIMDなどを自分で直接扱うことがないので,全く思いつきませんでした.出てきたグラフから見るに,要素の順序にちょっと気を付けておけば,計算時間が1/3ほどになる可能性も出てきますね(最悪値を抑えられると言った方が正しいでしょうか).かなり大きいですね.

      ところで,logical 型のメモリ使用量ですが,どうもbyte単位に思えます.手もとの matlab (R2007b x64 on win 8.1)では,
      >> a = true(128,64);
      >> whos a
      Name Size Bytes Class Attributes
      a 128x64 8192 logical
      >>
      てな感じになりまして,1bit の情報のために何故か贅沢にも1byteを割り当てているようです.プログラミング上有利な理由があるのかもしれませんが,個人的にはミステリーのひとつです.ちなみに,内部の bit 構成はどうかと思って bitget したところ,
      >> bitget(logical(1),1:8)
      ??? Error using ==> bitget
      Inputs must be non-negative integers.
      とあっさり跳ね返されました.ガード堅いです.

      拙い記事にお付き合いいただきありがとうございました.
      更新の少ないblogですが,お目に留まる記事などありましたら今後ともコメント頂ければ幸いです.

      削除