基本的なアルゴリズムを理解してプログラミングしよう：無償ソフトで技術計算しよう【プログラミング処理編】（2）（1/2 ページ）

アルゴリズムとは、問題を解くための手順を定式化して表現したもの。プログラミングにおける基本的なアルゴリズムには、探索やソート、マージなどがある。

[伊藤孝宏，MONOist]

　前回は、変数データの入出力やCSVファイルの入出力について解説しました。今回は、基本的なアルゴリズムに対応するコマンドを紹介します。

　アルゴリズムとは、“問題を解くための手順を定式化して表現したもの”で、プログラミングにおける基本的なアルゴリズムには、「探索（配列の中から目的のものを探し出すこと）」や「ソート（配列を並べ替えること）」、「マージ（複数の配列を結合し、並べ替えること）」などがあります。

　基本的なアルゴリズムを理解してプログラミングすることは、プログラミング学習には不可欠なことです。しかし、単に道具として使うだけであれば、同等の機能を実現するコマンドを使う方が簡単で確実です。ここでは、探索、ソートに対応するコマンドを紹介していきます。

• アルゴリズム（Wikipedia）

筆者注：FreeMatはコマンド入力後にエンターキーを押すとコマンドを実行します。本連載ではエンターキーの記述を省略しますが、操作の際にはコマンド入力後にエンターキーが必要です。

探索

　探索の初歩的なアルゴリズムは、配列の先頭から順に、目的のものと同じかどうかを比較していきます。

　「ex316.m」は、whileループを用いた探索プログラムです。始めに「randperm」コマンドで、1〜1000000までの整数がランダムに並んだ配列を生成します。次に、探索する目標（数値）をtarget=201311とします。

　後は、whileループで配列の要素（中身）とtargetを照らし合わせていきます。等しくなければ要素番号kに1を加えて次の要素と比較します。これを繰り返していき、targetと等しい要素が見つかったらその要素番号を取り出します。この際、b=[a,target]として、配列の最後にtargetの値を明示的に入れておくことで無限ループを避けることができます。要素とtargetが一致した際の要素番号kが、配列bの長さと等しい場合は、「要素は見つからなかった」と表示し、一致しなかったら「k番目にある」と表示します。

　コマンドの「tic」と「toc」はストップウオッチのスタート／ストップに相当するコマンドです。ticでストップウオッチをスタートさせ、tocでストップさせます。スタートからストップまでの時間は変数ansに格納されます。ここでは、whileループの前後にticとtocを置いて、time1=tocとして、計算に要した時間を計測しています。

clear;
a=randperm(1000000);
target=201311;
b=[a,target];
k=1;
tic;
while (b(k)~=target)
    k=k+1;
end;
time1=toc;
if (k==length(b))
    disp(['Could not find ',num2str(target)]);
else
    disp([num2str(target),' is ',num2str(k),'th element']);
end
disp(['The calculation needs ',num2str(time1),'second']);

ex316.m

＞＞「ex316.m」ダウンロード

　また、FreeMatは配列を扱うことができるため、論理式==で探索することも可能です。a==targetとすると、targetと等しい要素が1、その他は0の配列が出来上がります。後は「find」コマンドを使って、要素が1の位置を取り出します。なお、見つからない場合、findは空配列を返すため、変数が空配列かどうかを見分ける「isempty」コマンド（引数が空配列の場合は1を返す）で表示を使い分けています。findコマンドを使う方法で、ex316.mのwhileループ以降を書き換えたものが下記です。非常にシンプルであることが分かります。

tic;
pos=find(a==target);
time2=toc;
if (isempty(pos))
    disp(['Could not find ',num2str(target)]);
else
    disp([num2str(target),' is ',num2str(k),'th element']);
end
disp(['The calculation needs ',num2str(time2),'second']);

　双方の計算効率を調べてみます。ex316.mに上記のプログラムを付け加えて動作させると、例えば以下のような結果が得られます。

2.0131e+05 is 5.4299e+05th element
The calculation needs 0.173second
2.0131e+05 is 5.4299e+05th element
The calculation needs 0.087second

　whileループによる処理は0.173秒で、findによる処理は0.087秒であることが分かります。なお、これは数値をランダムに並べたものから該当の数値を見つけ出すプログラムであり、ハードウェアの処理能力の違いなども考えられるため、同様の計算を行っても同じ結果にはなりませんのであらかじめご了承ください。

　ちなみに、論理式とfindの組み合わせは、文字の検索にも使えます。例えば、find('How much wood would a woodchuck chuck?'=='m')とすると、ans = 5と、文字mは5番目であることが分かります。

　一方、文字列は配列となるため、論理式では検索できません。文字列の検索は、「strfind」コマンドを用います。idx=strfind(string、pattern)とすると、stringの中からpatternと同じ文字列が何番目かを変数idxに返します。例えば、strfind('How much wood would a woodstock chuck?','wood')とすると、ans = 10 23と、woodは10文字目と23文字目にあることが分かります。

　セル配列からの検索も同様です。例えば、strfind({'How much','wood would','a woodstock chuck?'},'wood')とすると、ans = [] [1] [3]と、2番目のセルの1文字目と3番目のセルの3文字目にあることが分かります。