@mgilson の回答から始めて、少し作り直しました。元の質問への回答で説明したように、「決定ビット」とルックアップ テーブルの手法をテストしたかった: https://stackoverflow.com/a/17782979/166949
オリジナルにいくつかの変更を加えました。いくつかは、私の個人的な好みを反映したスタイルのものでした. しかし、オリジナルでバグを発見したので、正しいコードを測定することが重要だと思います。
Python コードがコマンド ラインから引数を取るようにし、Python 2.x、Python 3.x、および PyPy を使用して Python スクリプトを実行するシェル スクリプトを作成しました。正確なバージョンは、Python 2.7.6、Python 3.4.0、および PyPy 2.7.3 でした。
Linux Mint 17、64 ビット バージョンでテストを実行しました。CPU は AMD Phenom 9850 で、2.5 GHz で 16 GB の RAM を搭載しています。あたりの Linux カーネルのバージョンuname -rは次のとおりです: 3.13.0-24-generic
コードがコマンド ラインから引数を取るようにした理由は、327 がかなり短いリストだからです。sum()リストがはるかに長い場合は and ジェネレーター式の方がうまくいくと考えたので、コマンド ラインからリストのサイズと試行回数を渡すようにしました。結果には、どの Python か、リストの長さと試行回数が表示されます。
結論: 驚いたことに、リストが長くても、Python はsum()リスト内包表記を使用するのが最速でした! ジェネレーターを実行すると、リストを作成して破棄するオーバーヘッドよりも遅いと思われるオーバーヘッドがあります。
ただし、リストが本当に大きくなった場合、ジェネレーターがリスト内包表記よりも優れたパフォーマンスを発揮し始めると予想しました。100 万個のランダム値のリストでは、listcomp はさらに高速でしたが、1,600 万個のランダム値になると、genexp の方が高速になりました。また、ジェネレーター式の速度のペナルティは、短いリストでは大きくありません。そのため、Python でこの問題を解決するための頼りになる方法として、ジェネレーター式を今でも支持しています。
興味深いことに、PyPy はテーブル ルックアップで最速でした。これは理にかなっています。これは私が C で見つけた最速の方法であり、PyPy は JIT からネイティブ コードを生成しています。
仮想マシンを備えた CPython の場合、複数の操作よりも 1 つの操作を呼び出す方が高速です。Python VM のオーバーヘッドは、より高価な基本的な操作を上回る可能性があります。したがって、整数除算はビット マスキングとビット シフトよりも高速です。これは、除算が 1 回の演算であるためです。しかし、PyPy では、ビット マスキング + シフトは除算よりもはるかに高速です。
また、CPython では、 using をsum()使用するとコードを C 内部で実行できるため、非常に高速になります。しかし、PyPy ではsum()、JIT が非常に高速なネイティブ ループに変わる可能性がある単純なループを記述するよりも遅くなります。私の推測では、ジェネレーターの機構は、PyPy が理解してネイティブ コードに最適化するのが難しいということです。
シェルスクリプト:
for P in python python3 pypy; do
echo "$P ($1, $2)"
$P test_branches.py $1 $2
echo
done
Python コード:
import random
import sys
import timeit
try:
RANGE = xrange
except NameError:
RANGE = range
if len(sys.argv) != 3:
print("Usage: python test_branches.py <length_of_array> <number_of_trials>")
sys.exit(1)
TEST_DATA_LEN = int(sys.argv[1])
NUM_REPEATS = int(sys.argv[2])
_test_data = [random.randint(0,255) for _ in RANGE(TEST_DATA_LEN)]
def test0(data):
"""original way"""
total = 0
for i in RANGE(TEST_DATA_LEN):
if data[i] >= 128:
total += data[i]
return total
def test1(data):
"""better loop"""
total = 0
for n in data:
if n >= 128:
total += n
return total
def test2(data):
"""sum + generator"""
return sum(n for n in data if n >= 128)
def test3(data):
"""sum + listcomp"""
return sum([n for n in data if n >= 128])
def test4(data):
"""decision bit -- bit mask and shift"""
lst = [0, 0]
for n in data:
lst[(n & 0x80) >> 7] += n
return lst[1]
def test5(data):
"""decision bit -- division"""
lst = [0, 0]
for n in data:
lst[n // 128] += n
return lst[1]
_lut = [0 if n < 128 else n for n in RANGE(256)]
def test6(data):
"""lookup table"""
total = 0
for n in data:
total += _lut[n]
return total
def test7(data):
"""lookup table with sum()"""
return sum(_lut[n] for n in data)
test_functions = [v for k,v in globals().items() if k.startswith("test")]
test_functions.sort(key=lambda x: x.__name__)
correct = test0(_test_data)
for fn in test_functions:
name = fn.__name__
doc = fn.__doc__
if fn(_test_data) != correct:
print("{}() not correct!!!".format(name))
s_call = "{}(_test_data)".format(name)
s_import = "from __main__ import {},_test_data".format(name)
t = timeit.timeit(s_call,s_import,number=NUM_REPEATS)
print("{:7.03f}: {}".format(t, doc))
結果：
python (327, 100000)
3.170: original way
2.211: better loop
2.378: sum + generator
2.188: sum + listcomp
5.321: decision bit -- bit mask and shift
4.977: decision bit -- division
2.937: lookup table
3.464: lookup table with sum()
python3 (327, 100000)
5.786: original way
3.444: better loop
3.286: sum + generator
2.968: sum + listcomp
8.858: decision bit -- bit mask and shift
7.056: decision bit -- division
4.640: lookup table
4.783: lookup table with sum()
pypy (327, 100000)
0.296: original way
0.312: better loop
1.932: sum + generator
1.011: sum + listcomp
0.172: decision bit -- bit mask and shift
0.613: decision bit -- division
0.140: lookup table
1.977: lookup table with sum()
python (65536, 1000)
6.528: original way
4.661: better loop
4.974: sum + generator
4.150: sum + listcomp
10.971: decision bit -- bit mask and shift
10.218: decision bit -- division
6.052: lookup table
7.070: lookup table with sum()
python3 (65536, 1000)
12.999: original way
7.618: better loop
6.826: sum + generator
5.587: sum + listcomp
19.326: decision bit -- bit mask and shift
14.917: decision bit -- division
9.779: lookup table
9.575: lookup table with sum()
pypy (65536, 1000)
0.681: original way
0.884: better loop
2.640: sum + generator
2.642: sum + listcomp
0.316: decision bit -- bit mask and shift
1.573: decision bit -- division
0.280: lookup table
1.561: lookup table with sum()
python (1048576, 100)
10.371: original way
7.065: better loop
7.910: sum + generator
6.579: sum + listcomp
17.583: decision bit -- bit mask and shift
15.426: decision bit -- division
9.285: lookup table
10.850: lookup table with sum()
python3 (1048576, 100)
20.435: original way
11.221: better loop
10.162: sum + generator
8.981: sum + listcomp
29.108: decision bit -- bit mask and shift
23.626: decision bit -- division
14.706: lookup table
14.173: lookup table with sum()
pypy (1048576, 100)
0.985: original way
0.926: better loop
5.462: sum + generator
6.623: sum + listcomp
0.527: decision bit -- bit mask and shift
2.334: decision bit -- division
0.481: lookup table
5.800: lookup table with sum()
python (16777216, 10)
15.704: original way
11.331: better loop
11.995: sum + generator
13.787: sum + listcomp
28.527: decision bit -- bit mask and shift
25.204: decision bit -- division
15.349: lookup table
17.607: lookup table with sum()
python3 (16777216, 10)
32.822: original way
18.530: better loop
16.339: sum + generator
14.999: sum + listcomp
47.755: decision bit -- bit mask and shift
38.930: decision bit -- division
23.704: lookup table
22.693: lookup table with sum()
pypy (16777216, 10)
1.559: original way
2.234: better loop
6.586: sum + generator
10.931: sum + listcomp
0.817: decision bit -- bit mask and shift
3.714: decision bit -- division
0.752: lookup table
3.837: lookup table with sum()