Wolfram Computation Meets Knowledge

最新のWolfram言語には,このチュートリアルに関連する新機能が追加されている.最新情報は行列と線形代数を参照のこと.

線形代数計算のパフォーマンス

パックアレー式の効率
プログラミング効率

このチュートリアルでは,特性に関する問題を取り扱う.

パックアレー

Mathematica を構築する際の課題のひとつに,システムが一般的で記号計算が可能であり,計算が早くて数値計算が効率的であるということがある.これらの課題と,その他の目標については,「Mathematica の設計原理」に述べてある.Mathematica におけるひとつの方法に,Mathematica 式の重要な型の特別な表記方法を用いることが挙げられる.線形代数に関しては,パックアレー技術と呼ばれるものが関わってくる.これはMathematica 4.0で初めて導入されたものである.

次の例は,実数のベクトルである:
ここで,ベクトルに記号的な数量を挿入する.ベクトルと行列の要素の更新については「行列の要素の設定」に記述してある:
バイト数を求めると,ベクトルはより多くのメモリを必要とすることが分かる:
また,ベクトルに数学的な演算を施すと,さらに遅くなる:

最初のベクトルが使用するメモリ量の方が少なく,計算が速くなる.これはパックアレーで構築されたベクトルであるからである.パックアレーは機械整数,機械実数,機械実数の実部と虚部を持つ複素数の長方形テンソルを表す方法である.

機械サイズ整数
機械精度実数
機械精度複素数

パックアレー型

パックアレーを扱うことができる便利な関数は数多く存在する.Developer`PackedArrayQは引数がパックアレーであるかどうかを確かめるための関数である.以下の例では,Tableの計算結果がパックアレーであることを示す:
アレーに実数が挿入されても,結果はパックアレーである:
計算がパックアレーで行われると,結果もパックアレーになる:
しかし,パックアレーに一般的な記号的数量が挿入されると,結果はパックアレーではなくなる:
パックアレーのすべての要素は同じ型でなくてはならない.そのため,整数0が実数のパックアレーに挿入されると,結果はパックアレーではなくなる:

パックアレー関数

パックアレーが使える多くの関数を以下にまとめる.

Developer`PackedArrayQ[expr]expr がパックアレーならTrueを返す
Developer`ToPackedArray[expr]可能ならexpr をパックアレーに変換する
Developer`ToPackedArray[expr,t]可能ならexpr を型t のパックアレーに変換する
Developer`FromPackedArray[expr]expr をパックアレーから変換する
Developer`PackedArrayForm[expr]expr のパックアレーの概略を表示する

パックアレー関数

関数Developer`ToPackedArrayを使うと,パックアレーが作成できる:
リストの要素の型がすべて同じでない場合,結果はパックアレーにならない:
Real型を指定すると,整数は強制的に実数とされ,結果はパックアレーとなる:
packが3つの実数からなるパックアレーであることを示す:
引数が長方形テンソルでないので,パックアレーが作れない:

パックアレー操作

パックアレーの重要な点として,「パックアレー関数」のパックアレー専用の関数以外についてはリストと全く同様に動作するということが挙げられる.例えば,パックアレーのリストとパックアレーでないリストにSameQを適用すると,Trueが返される:
パックアレーのリストとパックアレーでないもののリストにパターンマッチを行うと,どちらも同じ結果となる:

多くの関数は,パックアレーを使うと,パックアレーでないもののリストを使う場合に比べて,より効率的に計算が行われる.しかし,パックアレーでもパックアレーでなくても結果は同じである.結果が同じであるためには,システムは時折パックアレーをアンパックしなければならない.これは効率を悪くする潜在的な原因であり,何かがアンパックされることを伝えるメッセージが用意されている.このメッセージはシステムオプションを設定すると利用できる.

以下のようにするとシステムオプションが設定され,例として使用するパックアレーが作られる:
パックアレーに実数を挿入すると,パックアレーをアンパックしなければならないので,メッセージが現れる.このメッセージは,コードが効率的に実行されないかもしれないことを警告する:
通常はメッセージを再びオフにするとよい:

パックアレーのまとめ

パックアレーについての注目すべき点は,Mathematica が適切な場所で自動的にパックアレーを使用するということである.これは線形代数関数でも大いに当てはまり,通常は同じ内部表記で動作する.そのため,入力がパックアレーでなくても,多くの関数がパックアレーの結果を返す.例として,関数Dotは内部ではパックアレーを使って動作するため,結果としてパックアレーを返す:

パックアレーを使用するのに,Developer`ToPackedArray等の関数を利用するのは通常難しい.重要なのは,使用する行列の要素がすべて一様であるということである.つまり,例えば要素に整数と実数が混在しないようにしなければならないということである.

プログラミング効率

このセクションでは線形代数問題を解く効率的なMathematica プログラムの書き方について述べる.

パフォーマンスの計測

Mathematica には,コードのパフォーマンスについて学ぶ際に利用できる,計算時間に関する数多くの関数がある.

Timing[expr]expr を評価し,所要CPU時間と得られた結果のリストを返す
AbsoluteTiming[expr]expr を評価し,所要絶対時間を返す

Mathematica 操作の所要時間

Timing関数は計算に必要なCPU時間が求められるので,特に有用である:

TimeConstrainedも便利である.

TimeConstrained[expr,t]expr の評価を試み,t 秒後に計算を放棄する
TimeConstrained[expr,t,failexpr]制限時間で終らなかったらfailexpr を返す

時間を制約した計算

これはあらかじめ設定した時間を越えると強制終了するため,コードを開発してテストする際に便利である:

ループのベクトル化

通常の計算において,行列の要素に対してある操作を繰返し適用するということはよくある.行列は大きいこともあり,その場合は効率が重要になってくる.

効率的なコードを書く重要な方法のひとつに,特に内部ループにおいて明らかな部分参照は避けるということが挙げられる.このような部分参照は効率を劣化させる主因となり,行列やベクトルのすべての要素に一度で作用できる関数を使うことで回避できる.以下のようなベクトル化操作を使うと,Mathematica はより速く実行できる,高度に最適化されたコードを使うことができる.

リストの作成

次の問題では,リストを作り,それを特定の値で初期化する.例として,以下の計算を考える.

        vi  Sin[i]

リストの初期化のひとつの方法として,リストを作成し,Forループで繰り返し要素に値を割り当てる.

    n = 10;    
    v = Table[0, {n}];
    For[i = 1, i <= n, i++, v[[i]] = Sin[2.0 Pi i]];

リストの初期化(遅い方法)

リストを作成し,一度にリストを初期化できたらずっと速い上に,整然とする.

    n = 10;
    v = Table[ Sin[2.0 Pi i], {i, 1, n}]

リストの初期化(速い方法)

さらに速くするには,最適化された関数Rangeを使ってリストを作成し,ベクトル化操作を行う.

    n = 10;
    v = Sin[2.0 Pi Range[1., n]]

リストの初期化(さらに速い方法)

TableRange等のコマンドはリスト,行列の構築に非常に最適化されている.これらについては「行列の構築」のセクションで述べた.

リストの更新

次の問題では,リストの要素を更新する.例えば,各要素のSinを計算する.

        vi  Sin[vi]

これを行うひとつの方法は,リストの各要素を繰返し更新していくというものである.

    Do[v[[i]] = Sin[v[[i]]], {i, n}];

リストの更新(遅い方法)

これはベクトル化操作を用いると速くなる.コードもすっきりする.

    v = Sin[v]

リストの更新(速い方法)

引数をもう1つ使う別の方法がある.この引数はリスト全体で定数である訳ではない.

        vi  vi/i^2

これを行う方法のひとつとして,指標の2条で各要素を割るというものがある.

    n = Length[v];
    Do[ v[[i]] = v[[i]]/i^2 , {i, n}];

リストの更新(遅い方法)

更新の計算を行ってからベクトル化した割り算を実行する方が速い.

    d=Range[n]^2;
    v=v/d

リストの更新(速い方法)

リストへの縫込み操作については「リストへの縫込み」で説明してある.

組込みサポートの使用

Mathematica には非常に多岐に渡る関数がある.行列の計算を書く重要な用途を持つリスト操作ができるものもたくさんある.使い始める前に,組込み関数で使えるものがないかどうかを見てみるとよい.例えば,たたみ込みや相関等を行っているなら,それに適した関数を使うと,確実に計算が速くなる.

Mathematica が広範な数学オブジェクトを表すことができるということも特筆すべき点である.例えばMathematica は行列を使って表されている実際の線形方程式も扱える.方程式の形は時に,より表現力に富んで便利であり,より効率的になることもある.これについては「式の疎配列への変換」に説明してある.

線形代数計算に応用できる組込み関数の分野のひとつに,リストの構造操作がある.PartTakeDropTransposePadLeftPadRightRotateLeftRotateRight等のMathematica の関数は非常に最適化されており,広く応用できる.詳細は「構造操作」を参照のこと.一般には,これらの関数を使って計算をした方がよい.

ここで,行列のコピーを並べて拡張するさまざまな方法について取り上げる.例として,次の入力行列

            

を充填すると次の行列が返される.

            

この問題を解く3つの方法を例示する.

遅い方法

最も遅いのは,これをステップごとに直接すべての要素を操作するように書く方法である:

この方法はスピードが極めて遅い.その中でも,部分指標に対する内部ループが最も遅くなる.これらはベクトル化したコードと置き換えると速くなる.これについては内部ループで部分参照を行うと,非効率なコードになると「パフォーマンスの計測」に述べられている.

関数は疎行列を入力として与えるても動作するが,結果として密行列を返すということに留意のこと:

速い方法

行列を複製するはるかに速い方法として,その行列をMathematica のベクトル化関数を使って書くというものがある:

この方法は,非常に柔軟で,高度に最適化されている関数Partを使っているため,はるかに速い.詳細は「行列の一部の抽出」に記述してある.

この関数は疎行列の入力にも使え,結果として同程度の疎配列を返す:

速く,かつ整った方法

行列の展開を行い,プログラムしなくてもよい別の方法は,組込み関数PadRightを使う方法である:

この方法はより整っており,入力行列が小さいときは速いことが多い.大きい入力行列については,上記Partを使った例と同程度の速度である.PadRightの使い方については「行列の拡張」で述べた.

この関数は疎行列入力にも使え,結果として同程度の疎配列を返す:

行列の内容

Mathematica の行列は,Mathematica がサポートしているさまざまなすべてのオブジェクトの型を使って構築できる.行列は機械精度の浮動小数点数,任意精度の浮動小数点数,複素浮動小数点数,整数,有理数,一般の記号的数量を含むことができる.これらの型については「行列の型」を参照のこと.

Mathematica がこれらの多岐に渡る型の行列を扱えるということは,システムの強みである.しかし,数値的な浮動小数点計算の効率に影響を与える.まず,記号および数値的な要素の混在,次に異なる型の数の混在,そして整数行列がその要因である.

記号・数値が混在した行列

記号的,数値的要素を1つの行列の中に混在させると,「モード混在行列」で説明しているように,線形代数関数はその行列を記号的であるとみなす.記号行列を扱うための技術は通常数値行列用に高度に最適化されたものと比べて遅い.

次の例は200×200の2つの行列の掛け算を比較する.2つ目は記号行列の計算であるが,ずっと遅いことがわかる:

これを解決するには,行列が数値のみを含んでいるようにすればよい.

数値の型が混在した行列

行列の中に異なる型の数を混在させると,線形代数関数はその行列を数値行列として扱い,精度を最も低いものに合わせる.これについては「モード混在行列」に記述してある.これは線形代数関数に対して,記号行列のときほどのパフォーマンスへの影響はない(これについてはセクションで述べた).

次の例では,200×200の2つの行列の掛け算を比較する.2つ目の行列は整数を含んでいるが,行列同士の掛け算を行うと遅い.操作がよりコストの高いものの場合,この差は顕著ではないこともある.

混在数値行列のコストは,Mathematica が効率的な保管技術を使うことができないために生じる.これについては「パックアレー」で説明している.これを以下で例示する.数値のベクトルがあり,処理を行ってそれを更新するとする.更新後の値は実数であり,初期ベクトルは整数を含んでいるため,この処理においてパックアレーを使うことは不可能である:
次はベクトルを実数で初期化する.計算ではパックアレーが使用でき,より速く実行される:

この問題を解決するには,実数で処理したいときは実数で初期化すればよい.

整数行列

最後に,完全に整数の行列を考える.Mathematica は整数と近似実数は区別して扱う.これについては「Mathematica における行列」で述べている.整数行列には記号計算技術が使われるため遅くなる.もちろんMathematica で整数行列に整数行列技術を使わないことは一般的ではない:
2つの計算の違いを比べてみる.整数行列の固有値は厳密地で返される.この場合は有理数を含む.実行列の固有値は近似実数として返される:

整数行列を含む計算において厳密な結果を返すことはMathematica の利点である.しかし,純粋な数値系の多くに対しては近似の結果が返される.

近似実数の行列を扱う際は,計算を近似実数で始めなければならない.

式の効率

「Mathematica 式としての行列」ではMathematica が行列を式として表すことについて述べてある.この式は,システム全般に渡って一貫して使われるデータ型である.このシステム内での一貫した形式の利点についてはすでに述べた.Mathematica 式の使用は,効率にさまざまに影響する.

行列の更新

Mathematica 式の一般的な原理は,直接変更できないというものである.このような式の不変性はとても便利である.この性質により,式を多くの場所で共有でき,そのそれぞれの場所において,コードの他の部分が式を変更してしまう心配がない.つまり,式が更新されたら(これについては「行列の要素の設定」を参照),それをコピーする必要があるかもしれない.次の例ではベクトルを作成し,2つの異なるシンボルに割り当てる:
1つのシンボルの内容を変更する:
しかし,もう1つは変更しない.これは変更の前に式をコピーしたからである:
このようなコピーは,特に行列の要素に繰返し更新操作を行ったときに,効率に影響を及ぼすことがある.これを行い,さらにその行列のコピーが別にある場合,それをコピーする必要がある.以下の2つの例を使ってこの原理について解説する.最初の例では,ベクトルのコピーがないためコピーする必要がなく,ループは速く実行される:
次の例ではベクトルのコピーがあるため,各ステップにおいてコピーしなければならない.そのためループは遅い:
要素を更新する別の遅い方法として,ReplacePartを使用することが挙げられる.これも各ステップでコピーしなければならない:

前述のベクトル化操作を使うと,行列に対する繰返しの操作が回避でき,コピー回数が最小に抑えられる.行列に対する繰返し操作が回避不可能な場合は,そのループをできるだけ簡単にし,行列の無駄なコピーを避けるとよい.

全体の処理に必要な時間は,各ステップでコピーしなければならないリストの長さの2乗に比例して増加する.コピーしなくてもよい場合は線形的に増加する.入力リストが長くなると,その影響も大きくなり,コードのパフォーマンスが劣化し始める.

行列への追加

Mathematica では,式は配列として実装されている.これにより,式のある特定の要素に素早くアクセスできる.行列はMathematica 式なので,配列でもある.配列は要素に素早くアクセスできるが,要素を追加するのには時間がかかる.一般にこの操作にはコピーが必要とされるが,それは避けるべきことである.次の例では,要素を加えるためのコストを示す.

ベクトル全体を一度に生成するほうがはるかに効率がよい:
引数が一度に分からなくても,他の方法が使えることがある.これを以下に例示する.まず乱数のリストを作る:
1つめの方法では,AppendToを使う:
リストを蓄積し,空のリストを挿入して最後にFlattenを使ってそれを削除すると,はるかに速くなる:
Flattenはリストの構造を妨害することがあるので,不便なことがある.その場合,SowReapを使うとよいことがある.これはFlattenを使った方法より柔軟である:
3つの方法はすべて同じ結果となる:

全体の処理に必要な時間は,各ステップでコピーしなければならないリストの長さの2乗に比例して増加する.コピーしなくてもよい場合は線形的に増加する.入力リストが長くなると,その影響も大きくなり,コードのパフォーマンスが劣化し始める.