来自 here - a branching prediction problem ，我开始编写程序的 Python 版本来检查 Python 中已排序/未排序版本的运行时间。 我先尝试排序。
代码如下:
import time
from random import *
arraysize = 327
data = []
for c in range(arraysize):
data.append( randint( 1 , 256 ) )
## !!! with this, the next loop runs faster
data.sort()
## test
start_time = time.clock()
sum = 0
for i in range(100000):
for c in range(arraysize):
if data[c] >= 128:
sum += data[c]
print time.clock() - start_time
我不确定我的简单计时方法的准确性，但它似乎还不错。
当我设置 arraysize = 32768 时，我第一次等待了 >20 分钟! 20多分钟!
但是使用 arraysize = 327，我得到了 8.141656691s 的时间。
如果我的代码某处有误，或者以某种方式使用 Numpy/Scipy 是否会加快速度，请纠正我。 谢谢。
最佳答案
我从@mgilson 的回答开始，然后稍微修改了一下。我想测试在我对原始问题的回答中讨论的“决策位”和查找表技术:https://stackoverflow.com/a/17782979/166949
我对原作做了一些改动。有些只是反射(reflect)我个人喜好的风格。但是，我发现了原始代码中的错误，我认为衡量正确的代码很重要。
我让 Python 代码现在从命令行获取参数，并编写了一个 shell 脚本，使用 Python 2.x、Python 3.x 和 PyPy 运行 Python 脚本。确切的版本是:Python 2.7.6、Python 3.4.0 和 PyPy 2.7.3
我在 64 位版本的 Linux Mint 17 上运行了测试。 CPU 是 AMD Phenom 9850，运行频率为 2.5 GHz，内存为 16 GB。根据 uname -r，Linux 内核版本为:3.13.0-24-generic
我让代码从命令行获取参数的原因是 327 是一个非常短的列表。我认为当列表更长时 sum() 和生成器表达式会做得更好，所以我让列表大小和试验次数从命令行传递。结果显示是哪个 Python，以及列表长度和试验次数。
结论:令我惊讶的是，即使列表很长，Python 也是最快的使用 sum() 和列表理解!运行生成器的开销似乎比构建列表然后将其拆除的开销慢。
但是，如果列表变得非常大，我预计生成器将开始超越列表理解。对于一百万个随机值的列表，listcomp 仍然更快，但是当我达到 1600 万个随机值时，genexp 变得更快。对于较短的列表，生成器表达式的速度损失并不大。所以我仍然赞成生成器表达式作为在 Python 中解决这个问题的首选方法。
有趣的是，PyPy 的表查找速度最快。这是有道理的:这是我在 C 中发现的最快方式，而且 PyPy 正在从 JIT 生成 native 代码。
对于 CPython，通过其虚拟机，调用单个操作比调用多个操作更快； Python VM 的开销可能超过更昂贵的基本操作。因此整数除法比位掩码加位移更快，因为除法是一个单一的操作。但在 PyPy 中，位掩码+移位比除法快得多。
此外，在 CPython 中，使用 sum() 可以让您的代码在 C 内部运行，因此它可以非常快；但是在 PyPy 中，sum() 比只编写一个简单的循环要慢，JIT 可以将其变成一个邪恶的快速 native 循环。我的猜测是 PyPy 很难理解生成器机制并将其优化为 native 代码。
shell脚本:
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()
关于python - 如何使这个 python 脚本更快？ (与此处帖子的分支预测相关的基准测试)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12530812/