为什么在Python中处理已排序数组的速度不比未排序数组快？

Question

在这篇文章为什么排序数组的处理速度比随机数组快中，提到分支预测是排好序的数组性能优化的原因。

但我刚刚用Python试了一下这个例子；我认为排序和随机数组没有区别（我尝试了bytearray和array；使用line_profile来分析计算）。

我是否遗漏了什么？

这是我的代码：

from array import array
import random
array_size = 1024
loop_cnt = 1000
# I also tried 'array', and it's almost the same
a = bytearray(array_size)
for i in xrange(array_size):
    a.append(random.randint(0, 255))
#sorted                                                                         
a = sorted(a)
@profile
def computation():
    sum = 0
    for i in xrange(loop_cnt):
        for j in xrange(size):
            if a[j] >= 128:
                sum += a[j]

computation()
print 'done'

- ming.kernel

---

sorted(a)会返回一个已排序的列表，但它不会修改a。为了使代码按你想象的那样工作，你需要使用a = sorted(a)或更好的方法是使用a.sort()。 - Jeremy Roman

你可能想在这里查看Python的结果：http://stackoverflow.com/a/18419405/1903116 - thefourtheye

看这个。这可能会有所帮助。 - piyush

Python使用Timsort，这可能会产生一些影响...顺便说一下。 - rogerdpack

@rogerdpack：排序算法并不重要；所有稳定的算法都会产生相同的结果。这里没有对排序时间进行分析。 - jfs

Answer 1

我可能错了，但我认为链接的问题和你的例子之间存在根本性的区别: Python 解释字节码，而 C++ 则编译成原生代码。

在 C++ 代码中，`if` 直接翻译成一个 `cmp`/`jl` 序列，这可以被 CPU 分支预测器视为单个“预测点”，特定于该周期。

在 Python 中，这种比较实际上是几个函数调用，因此有(1)更多的开销和(2)我认为执行该比较的代码是用于每个其他整数比较的解释器中的函数，因此它是一个不特定于当前块的“预测点”，这使得分支预测器难以正确猜测。

编辑: 此外，正如这篇论文所概述的那样，在解释器内部存在更多的间接分支，因此你的 Python 代码中这样的优化可能会被解释器本身的分支错误 bury。

- Matteo Italia

Answer 2

两个原因：

• 你的数组大小太小，无法显示效果。
• Python 比 C 有更多的开销，因此总体上效果不会那么明显。

- Mark Ransom

---

这个程序在我的Mac Air上需要1.5秒，更大的数组会消耗太多时间；我只是不想等待。 - ming.kernel

我只是不想等待，你更喜欢我们替你完成吗？ - dda

@dda 抱歉，我的意思是当配置如上所述时，该函数已经需要1.5秒的时间；如果我们可以从排序数组中获得一些性能提升，我们肯定会看到它。实际上，我已经将数组大小增加了10倍，或者循环次数增加了10倍，执行时间呈线性增长。 - ming.kernel

我在我的MBP上进行了一项测试，将array_size和loop_cnt乘以10，这是结果： 随机数组：9.97857904434 排序后的数组：7.98291707039 - dda

Answer 3

我将原始代码移植到Python并使用PyPy运行。我可以确认排序后的数组比未排序的数组处理速度更快，无分支方法也适用于消除分支，其运行时间类似于排序数组。我认为这是因为PyPy是一个JIT编译器，所以分支预测正在发生。

[编辑]

以下是我使用的代码：

import random import time def runme(data): sum = 0 start = time.time()

for i in xrange(100000): for c in data: if c >= 128: sum += c

end = time.time() print end - start print sum

def runme_branchless(data): sum = 0 start = time.time()

for i in xrange(100000): for c in data: t = (c - 128) >> 31 sum += ~t & c

end = time.time() print end - start print sum

data = list()

for i in xrange(32768): data.append(random.randint(0, 256))

sorted_data = sorted(data) runme(sorted_data) runme(data) runme_branchless(sorted_data) runme_branchless(data)

- user1591276

---

在一台配备2.53 GHz英特尔Core 2 Duo和PyPy 1.9.0的MBP上，结果如下：`// 分支 - 随机 秒数 = 36.2439880371// 分支 - 排序 秒数 = 18.3833880424// 无分支 - 随机 秒数 = 13.1689388752// 无分支 - 排序 秒数 = 12.3706789017` - user1591276

Answer 4

sorted() 返回一个已排序的数组，而不是就地排序。这意味着你实际上测量了相同的数组两次。

- user622367

---

我刚刚把它改成了"a = sorted(a)"；它仍然是一样的。 - ming.kernel

Answer 5

点击这里查看更多答案和类似问题。当数据排序时性能显著提高的原因在于，分支预测惩罚被消除了，正如Mysticial的回答中所美妙地解释的那样。

- Evenure