3

从这里 - 一个分支预测问题，我开始编写程序的 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 是否会加快速度，请纠正我。谢谢。

4

2 回答 2

8

我从@mgilson 的答案开始，并对其进行了一些修改。我想测试我对原始问题的回答中讨论的“决策位”和查找表技术：https ://stackoverflow.com/a/17782979/166949

我对原作做了一些改动。有些只是反映我个人喜好的风格。然而，我发现了原始的错误，我认为测量正确的代码很重要。

我让 Python 代码现在从命令行获取参数，并编写了一个 shell 脚本，该脚本使用 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。Linux 内核版本 peruname -r为：3.13.0-24-generic

我让代码从命令行获取参数的原因是 327 是一个非常短的列表。我认为sum()当列表更长时，and generator 表达式会做得更好，所以我让列表大小和试验次数从命令行传递。结果显示了哪个 Python，以及列表长度和试验次数。

结论：令我惊讶的是，即使列表很长，Python 使用sum()列表理解也是最快的！运行生成器的开销似乎比构建列表然后将其拆除的开销要慢。

但是，如果列表真的很大，我预计生成器将开始超越列表理解。对于一百万个随机值的列表，listcomp 仍然更快，但是当我达到 1600 万个随机值时，genexp 变得更快。对于较短的列表，生成器表达式的速度损失并不大。所以我仍然倾向于将生成器表达式作为在 Python 中解决这个问题的首选方法。

有趣的是，PyPy 的查表速度最快。这是有道理的：这是我在 C 中发现的最快的方式，而 PyPy 正在从 JIT 生成本机代码。

对于 CPython，使用它的虚拟机，调用单个操作比调用多个操作要快；Python VM 的开销可能超过更昂贵的基本操作。因此整数除法比位掩码加位移更快，因为除法是一个单一的操作。但是在 PyPy 中，位掩码+移位比除法快得多。

此外，在 CPython 中， usingsum()可以让您的代码在 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()
于 2014-06-25T03:20:22.260 回答
4

一个小的优化，也是风格问题，列表可以直接迭代，而不需要索引它们：

for d in data:
    if d >= 128:
        sum += d

这节省了一些函数调用。

如果您使用内置sum函数，此循环也可能会更快：

my_sum += sum( d for d in data if d>=128 )

列表组合可能比上面的生成器更快（以额外的内存为代价）：

my_sum += sum( [d for d in data if d>=128] )

当然，从算法的角度来看，我们可以去掉最外层循环，因为内层循环的总和不会改变：

my_sum = 100000 * sum( d for d in data if d>=128 )

但我猜你已经知道了...

最后，这是我将如何进行基准测试：

import random
import timeit

N = 327
testarr = [random.randint(1,256) for _ in range(N)]

def test1(data):
    """Original way"""
    s = 0
    for c in range(N):
        if data[c] >= 128:
            s += data[c]


def test2(data):
    """better loop"""
    s = 0
    for d in data:
        if d >= 128:
            s += d

def test3(data):
    """ sum + generator """
    sum( d for d in data if d >= 128 )

def test4(data):
    """ sum + listcomp """
    sum( [ d for d in data if d >= 128 ])

NNUMBER = 100000
print timeit.timeit('test1(testarr)','from __main__ import test1,testarr',number=NNUMBER)
print timeit.timeit('test2(testarr)','from __main__ import test2,testarr',number=NNUMBER)
print timeit.timeit('test3(testarr)','from __main__ import test3,testarr',number=NNUMBER)
print timeit.timeit('test4(testarr)','from __main__ import test4,testarr',number=NNUMBER)

我的结果（OS-X Mavericks，python 2.7.5 - 里程可能会有所不同）：

2.80526804924  # loop with range
2.04129099846  # loop over elements
1.91441488266  # sum with generator
2.05234098434  # sum with list

对我来说，发电机以sum微弱优势获胜。list-comp withsum和显式循环大致相等。循环遍历索引（毫不奇怪）是最慢的。

于 2012-09-21T12:47:37.120 回答