2

私はより大きなプログラムを書いていますが、3x3行列の行列式をできるだけ速く取得することは、それがうまく機能するために非常に重要です。numPyを使用してそれを実行できることを読みましたが、CompSciの3学期にいるので、自分でコードを書く方が教育的だと思いました。

そこで、2つの関数を作成し、time.clock（）（win7マシンを使用）を使用して、各関数が値を返すのにかかる時間を計測します。

これが最初の関数です。

def dete(a):
   x = (a[0][0] * a[1][1] * a[2][2]) + (a[1][0] * a[2][1] * a[3][2]) + (a[2][0] * a[3][1] * a[4][2])
   y = (a[0][2] * a[1][1] * a[2][0]) + (a[1][2] * a[2][1] * a[3][0]) + (a[2][2] * a[3][1] * a[4][0])
   return x - y

そしてこれは2番目の関数です：

def det(a):
    a.append(a[0]); a.append(a[1]);
    x = 0
    for i in range(0, len(a)-2):
        y=1;        
        for j in range(0, len(a)-2):    
            y *= a[i+j][j]      
        x += y

    p = 0
    for i in range(0, len(a)-2):
        y=1;
        z = 0;
        for j in range(2, -1, -1):  
            y *= a[i+z][j]  
            z+=1        
        z += 1
        p += y  
    return x - p

どちらも正しい答えを示していますが、最初の方が少し速いようです。これにより、forループの方が使いやすく、通常は高速であるため、間違ったことをしていると思います。ループが遅すぎて太くなりすぎたのです。 。トリミングしてみましたが、*=と+=の操作に時間がかかりすぎて多すぎるようです。numPyがこの問題をどれだけ速く処理するかはまだ確認していませんが、効率的なコードの記述を上手にしたいと思っています。それらのループをより速くする方法についてのアイデアはありますか？

4

5 に答える 5

3

ループは-よりエレガントでより一般的ですが、単一の式での2つのインライン乗算よりも「通常は高速」ではありません。

1つは、forPythonのループは、相互作用するオブジェクト（の呼び出し）を介してオブジェクトをアセンブルrangeし、ループ上のすべてのアイテムに対してそのイテレーターのメソッドを呼び出す必要があります。

したがって、実行している内容に応じて、インライン形式がそれを維持するのに十分な速度である場合、それでも遅すぎる場合（Pythonで数値計算を実行している場合のように）、数値ライブラリを使用する必要があります（たとえば、NumpY）は、ネイティブコードで行列式を計算できます。このような数値操作コードの場合、ネイティブコードを使用すると数百倍速く実行できます。

yo9uが、すでに作成されたライブラリでは実行できない数値計算を必要とする場合、速度を求める場合（たとえば、画像処理でのピクセル操作）、ネイティブコードで実行される拡張機能を作成することをお勧めします（いずれかのCを使用） 、Cython、または他の何か）それを速くするために。

一方、速度が重要ではなく、インライン式が「わずかに高速」であることに気付いた場合は、完全なループを使用するだけで、より読みやすく保守しやすいコードが得られます。これが、結局のところPythonを使用する主な理由です。

与えた特定の例では、タプルへの「範囲」呼び出しをハードコーディングすることで、ループコードの速度をいくらか向上させることができます。たとえば、次のように変更し ます。インラインの場合と同様に、行列を操作する機能が失われることfor i in range(0, len(a)-2):に注意してください。for i in (0, 1, 2)さまざまなサイズの。

于 2012-02-26T17:35:56.270 に答える
3

まず、マイクロスケールの速度の最適化は別の言語で行う必要があることに注意してください。したがって、c-written機能を採用したライブラリを使用することをお勧めします。

forループについて：高速化のために（小さな）ループを展開するのは一般的な手法であるため、ループに処理を任せる方が常に速いとは限りません。通常、それはより一般的です（そして、ほとんどの一般的なアルゴリズムは、実際には特殊なアルゴリズムよりも低速です）。

コメントで述べられているように、Pythonで置き換える場合、速度は向上-し*ませんが、関係する算術演算が少ない場合は速度が向上する可能性があります。したがって、ここで因数分解された用語を投稿します。

def dete(a):
    return (a[0][0] * (a[1][1] * a[2][2] - a[2][1] * a[1][2])
           -a[1][0] * (a[0][1] * a[2][2] - a[2][1] * a[0][2])
           +a[2][0] * (a[0][1] * a[1][2] - a[1][1] * a[0][2]))

ご覧のとおり、5+/-と9*がありますが、元のバージョンと同様に5+/-と12があり*ます。aまた、このバージョンは15回しかアクセスせず、元のバージョンは18回アクセスしたことに注意してください。

これを要約すると、完全に乗算されたバージョンよりも少ない3つの算術演算と3つの変数アクセスが得られます。

于 2012-02-26T17:29:13.867 に答える
1

ループが明示的な長い式よりも高速になることはほとんど不可能なので、最初のバリアントが高速であることも不思議ではありません。最初の関数よりも速くsmtを思い付くことができるとは思えません。

于 2012-02-26T17:32:06.513 に答える
1

上で提案したように、展開している間、2つのブロックの間に依存関係がないことが一目でわかるので、2つのブロックを1つに結合することもできます（間違っている場合は修正してください）

于 2012-02-26T17:31:30.063 に答える
0

ループを展開して、 nxn行列ではなく3x3行列を処理するという事実を利用できます。

この最適化を使用すると、行列のサイズの決定を取り除くことができます。あなたは少しスピードアップして柔軟性を交換します。結果マトリックスの各セルの具体的な数式を簡単に書き留めることができます。ところで：（c ++）コンパイラはそのような最適化を行います。

そのような小さな最適化が特殊なコードの価値があると本当に確信している場合にのみ、そうすることをお勧めします。確実に、コードの正しい部分を最適化するために、たとえばプロファイリングツールを使用してください。http： //docs.python.org/library/profile.htmlまたはtimeitを参照してください。

于 2012-02-26T17:28:33.600 に答える