SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

NativeとRussian Peasantsの処理速度の差。

アルゴリズムで全然処理速度違ってくるよ、という基本的な話。
乗算演算のNative AlgorithmとRussian Peasants Algorithmで処理速度の差を見ていく。

Native Algorithm


一番シンプルな掛け算。xの数分yの値を足していく。

def native(a, b):
    x = a; y = b
    z = 0
    while x > 0:
        z = z + y
        x = x - 1
    return z

if __name__ == "__main__":
    print native(14, 11)

この乗算にあたって、ループ前とループ後で演算処理の条件が変わらないことを確認する。
もし { \displaystyle
ab = xy + z
} であれば、 { \displaystyle
ab = x'y' + z'
} である。

{ \displaystyle
x'y' + z' = (x-1) * y + (z+y)
}
{ \displaystyle
x'y' + z' = xy -y + z + y
}
{ \displaystyle
x'y' + z' = xy + z
}

このことからループ前とループ後での条件が変わらないことが確認できる。
つまり、ループを回している最中、 { \displaystyle
ab = xy + z
} の条件は変わらないままループは回り続け、x=0となったタイミングでループが終了して乗算結果が出力される。

sot0:IntroAlgolithm sotoshigoto$ python native.py
154

Russian Peasants Algorithm


ロシア農民のアルゴリズム*1と呼ばれている。
構成自体はNativeと同じであり、xが0以下になるまでループを行い乗算結果を算出している。nativeと違うところとしては、ビット演算のシフトを使っているところと、モジュロ演算子を使って、奇数であればyの値を加算するアルゴリズムであるというところである。

def russian(a, b):
    x = a; y = b
    z = 0
    while x >0:
        if x % 2 == 1: z = z + y
        y = y << 1
        x = x >> 1
    return z

if __name__ == "__main__":
    print russian(14, 11)

native同様、この乗算にあたって、ループ前とループ後で演算処理の条件が変わらないことを確認する。
もし { \displaystyle
ab = xy + z
} であれば、 { \displaystyle
ab = x'y' + z'
} である。

russianアルゴリズムの場合、奇数と偶数の2つのパターンが考えられる。

x is odd

{ \displaystyle
x'y' + z' = \frac{(x-1)}{2} * 2y + (z+y)
}
{ \displaystyle
x'y' + z' = xy -y + z + y
}
{ \displaystyle
x'y' + z' = xy + z
}

x is even

{ \displaystyle
x'y' + z' = \frac{x}{2} * 2y + z
}
{ \displaystyle
x'y' + z' = xy + z
}

たとえxが奇数であっても偶数であっても、ループ後のは正しく積が行わることがわかる。

sot0:IntroAlgolithm sotoshigoto$ python russian.py
154

以下実際に154の結果が出るまでのループ中の値の変動である。奇数の場合のみ加算されることによって乗算が成り立っている。

xyz
14110
7220
34422
18866
0176154


Who is better ?


NativeとRussian、この二つの乗算アルゴリズムはどちらが速いだろうか。
処理速度で比較をしてみる。

russianは2の1000乗同士の乗算を行い、nativeは2の23乗同士の乗算を行った。russianの方がnativeと比べて圧倒的に計算量が大きい値となっているが、それでも結果はrussianの方が圧倒的に速いことがわかる。russianには巨大な数値を入れても一瞬で答えが返ってくるが、nativeは体感的にも処理の遅さを感じる。

sot0:IntroAlgolithm sotoshigoto$ python russian.py
russian was executed, it took 0.00172090530396 sec
114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376
-----------------
native was executed, it took 0.780112981796 sec
70368744177664

このようにアルゴリズムによって処理の速度は全く変わってくる。
可読性という点においては、Nativeの方が良くて、処理速度的にはRussianの方が良いと言えるが、一般的に優れたアルゴリズムというものは後者を指すことが多い。Nativeにもっと巨大な数値を扱わせようとした際には、僕らは年老いてしまうかもしれないけれど、Russianなら若いうちに答えを見ることができてしまう。Russianは分割統治法を用いて計算しているため、愚直にxの数分を加算をしているNativeよりも計算量が少なくなっている。分割した副問題の答えを合わせてあげれば元々の答えとなるためである。
また、分割統治法の考えを用いて再帰的にrussianを表現すると以下のようになる。

def rec_russian(a, b):
    if a == 0: return 0
    if a % 2 == 0: return 2*rec_russian(a/2, b)
    return b + 2*rec_russian((a-1)/2, b)

if __name__ == "__main__":
    print rec_russian(2**10, 2**10)

再帰処理を行っている箇所を見ると、2が乗算されており、副問題で返ってきた答えに対して2を掛けてあげることで元々の問題の答えが返ってくるようになっている。

sot0:IntroAlgolithm sotoshigoto$ python rec_russian.py
1048576

このようにして労力を半分にしてあげることもできるようになることがわかった。
怠惰は美徳ということで。


参考

https://www.udacity.com/course/viewer#!/c-cs215/

Remove all ads