python - 为什么 reversed(mylist) 这么慢？

Question

( 更新: 可能只发生在 CPython 3.8 32 位的 Windows 中，所以如果您不能在其他版本中重现它，请不要感到惊讶。请参阅更新部分中的表格。)

两者 iter和 reversed导致列表的专门迭代器:

>>> iter([1, 2, 3])
<list_iterator object at 0x031495C8>

>>> reversed([1, 2, 3])
<list_reverseiterator object at 0x03168310>

但是reversed一个要慢得多:

> python -m timeit -s "a = list(range(1000))" "list(iter(a))"
50000 loops, best of 5: 5.76 usec per loop

> python -m timeit -s "a = list(range(1000))" "list(reversed(a))"
20000 loops, best of 5: 14.2 usec per loop

而且我可以始终如一地重现它。后来我试了iter再五次，拿了 5.98、5.84、5.85、5.87、5.86。然后reversed再五次，拿了 14.3、14.4、14.4、14.5、14.3。

我想也许 iter受益于增加列表元素的内存位置，所以我事先尝试反转列表。同一张图:

> python -m timeit -s "a = list(range(1000)); a.reverse()" "list(iter(a))"
50000 loops, best of 5: 5.73 usec per loop

> python -m timeit -s "a = list(range(1000)); a.reverse()" "list(reversed(a))"
20000 loops, best of 5: 14.1 usec per loop

同图 sum还有:

> python -m timeit -s "a = list(range(1000))" "sum(iter(a))"
20000 loops, best of 5: 10.7 usec per loop

> python -m timeit -s "a = list(range(1000))" "sum(reversed(a))"
10000 loops, best of 5: 20.9 usec per loop

并且具有相同的元素:

> python -m timeit -s "a = [None] * 1000" "list(iter(a))"
50000 loops, best of 5: 6.35 usec per loop

> python -m timeit -s "a = [None] * 1000" "list(reversed(a))"
20000 loops, best of 5: 14.5 usec per loop

为什么反向迭代器这么慢？

我在 Windows 10 pro 64 位版本 1903 上使用 CPython 3.8.1 32 位和 Intel i5-7200U(它是 HUAWEI MateBook X)。没有特殊的配置，只是在正常的 Windows 安装上进行正常的 Python 安装。

更新:
我在另一台机器(Pentium N3700、Windows 10 Pro 64 位 1903)上使用八个不同的 Python 版本(全部以默认设置全新安装)运行了一个更大的自动化测试。每个循环中使用的时间:

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      16.6     17.0       15.2     16.2
 3.6.8      16.8     17.2       14.9     15.8
 3.7.6      16.5     16.9       14.8     15.5
 3.8.1      16.3     22.1       14.6     15.5

有两点需要注意:

Python 3.8.1 32 位 reversed是唯一一个慢得多的。可以解释为什么几乎没有其他人可以复制它。

在所有其他七个版本中，reversed比 iter 慢一点. 32 位约 0.4 usec，64 位约 0.9 usec。

我以循环方式运行了这 16 个测试十轮，上面显示的每次都是十个源时间中最好的一次。 160 个源时间中的每一个都是这样完成的:

python.exe -m timeit -r 5 -s "a = list(range(1000))" "list(iter(a))"
or
python.exe -m timeit -r 5 -s "a = list(range(1000))" "list(reversed(a))"

16 次测试中每一次的时间都非常一致。全表(请注意，循环意味着我逐列运行这些列，而不是逐行):

3.5.4 32-bit iter     [16.7, 16.6, 17.3, 16.6, 16.7, 16.6, 16.6, 16.6, 16.6, 16.7]
3.5.4 32-bit reversed [17.1, 17.1, 17.1, 17.2, 17.1, 17.1, 17.0, 17.1, 17.1, 17.1]
3.5.4 64-bit iter     [15.2, 15.4, 15.4, 15.4, 15.4, 15.4, 15.4, 15.3, 15.4, 15.3]
3.5.4 64-bit reversed [16.8, 16.2, 16.3, 16.3, 16.2, 16.2, 16.2, 16.2, 16.2, 16.3]
3.6.8 32-bit iter     [17.3, 16.9, 16.8, 16.9, 16.9, 16.8, 16.9, 16.9, 16.8, 16.8]
3.6.8 32-bit reversed [17.2, 17.2, 17.2, 17.3, 17.3, 17.3, 17.3, 17.2, 17.2, 17.2]
3.6.8 64-bit iter     [15.0, 14.9, 15.9, 14.9, 14.9, 15.0, 14.9, 14.9, 14.9, 14.9]
3.6.8 64-bit reversed [15.8, 15.9, 16.4, 15.9, 15.9, 16.0, 15.8, 15.9, 15.9, 15.8]
3.7.6 32-bit iter     [16.6, 17.2, 16.6, 16.5, 16.7, 16.7, 16.5, 16.5, 16.5, 16.7]
3.7.6 32-bit reversed [17.2, 17.6, 17.0, 17.0, 16.9, 17.2, 17.3, 17.0, 17.5, 17.0]
3.7.6 64-bit iter     [14.8, 15.1, 14.9, 14.9, 14.8, 15.1, 14.9, 14.8, 15.0, 14.9]
3.7.6 64-bit reversed [16.0, 20.1, 15.7, 15.6, 15.6, 15.6, 15.7, 15.7, 15.8, 15.5]
3.8.1 32-bit iter     [16.4, 16.6, 16.3, 16.4, 16.5, 16.4, 16.5, 16.4, 16.8, 16.4]
3.8.1 32-bit reversed [22.3, 22.4, 22.2, 22.3, 22.3, 22.3, 22.5, 22.4, 22.3, 22.1]
3.8.1 64-bit iter     [14.6, 15.1, 14.6, 14.7, 14.7, 14.7, 14.7, 14.6, 14.6, 14.6]
3.8.1 64-bit reversed [15.5, 16.1, 15.5, 15.6, 15.5, 15.5, 15.5, 15.5, 15.5, 15.5]

对具有一百万个值 ( list(range(250)) * 4000 ) 的列表进行相同的测试。每个循环的时间是毫秒:

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      19.8     19.9       22.4     22.7
 3.6.8      19.8     19.9       22.3     22.6
 3.7.6      19.9     19.9       22.3     22.5
 3.8.1      19.8     24.9       22.4     22.6

除了 reversed 之外，变化甚至更小。在 3.8.1 32 位上再次慢得多。

还有一个，只是使用 CPython 3.8.0 而不是 3.8.1，它也会发生。

                32-bit              64-bit
CPython     iter   reversed     iter   reversed
 3.5.4      19.5     19.6       21.9     22.2
 3.6.8      19.5     19.7       21.8     22.1
 3.7.6      19.5     19.6       21.7     22.0
 3.8.0      19.4     24.5       21.7     22.1

Answer 1

我一直在看python文档，发现这个:

If the __reversed__() method is not provided, the reversed() built-in will fall back to using the sequence protocol (__len__() and __getitem__()). Objects that support the sequence protocol should only provide __reversed__() if they can provide an implementation that is more efficient than the one provided by reversed().

大概就是因为这个。
我不是专家，但我看到这个问题是 7 个月没有答案，并试图根据 python 文档给你一个。
这些是我使用的资源:
https://docs.python.org/3/library/functions.html#reversed
https://docs.python.org/3/reference/datamodel.html#object