python - 为什么排序时 Python 列表会变慢?
问题描述
在下面的代码中,我创建了两个具有相同值的列表:一个列表未排序 (s_not),另一个列表已排序 (s_yes)。这些值由 randint() 创建。我为每个列表运行一些循环并计时。
import random
import time
for x in range(1,9):
r = 10**x # do different val for the bound in randint()
m = int(r/2)
print("For rand", r)
# s_not is non sorted list
s_not = [random.randint(1,r) for i in range(10**7)]
# s_yes is sorted
s_yes = sorted(s_not)
# do some loop over the sorted list
start = time.time()
for i in s_yes:
if i > m:
_ = 1
else:
_ = 1
end = time.time()
print("yes", end-start)
# do the same to the unsorted list
start = time.time()
for i in s_not:
if i > m:
_ = 1
else:
_ = 1
end = time.time()
print("not", end-start)
print()
带输出:
For rand 10
yes 1.0437555313110352
not 1.1074268817901611
For rand 100
yes 1.0802974700927734
not 1.1524150371551514
For rand 1000
yes 2.5082249641418457
not 1.129960298538208
For rand 10000
yes 3.145440101623535
not 1.1366300582885742
For rand 100000
yes 3.313387393951416
not 1.1393756866455078
For rand 1000000
yes 3.3180911540985107
not 1.1336982250213623
For rand 10000000
yes 3.3231537342071533
not 1.13503098487854
For rand 100000000
yes 3.311596393585205
not 1.1345293521881104
因此,当增加 randint() 中的界限时,排序列表上的循环会变慢。为什么?
解决方案
缓存未命中。当N
int 对象被背靠背分配时,为保存它们而保留的内存往往位于连续的块中。因此,按分配顺序遍历列表往往会访问按顺序、连续、递增顺序保存整数值的内存。
随机播放它,爬过列表时的访问模式也是随机的。缓存未命中比比皆是,只要有足够多不同的 int 对象,它们并不都适合缓存。
在r==1
, 和r==2
处,CPython 碰巧将这样的小整数视为单例,因此,例如,尽管列表中有 1000 万个元素,r==2
但它只包含(最多)100 个不同的 int 对象。那些同时适合缓存的所有数据。
但是,除此之外,您可能会获得更多、更多、更多不同的 int 对象。当访问模式是随机的时,硬件缓存变得越来越没用。
说明:
>>> from random import randint, seed
>>> seed(987987987)
>>> for x in range(1, 9):
... r = 10 ** x
... js = [randint(1, r) for _ in range(10_000_000)]
... unique = set(map(id, js))
... print(f"{r:12,} {len(unique):12,}")
...
10 10
100 100
1,000 7,440,909
10,000 9,744,400
100,000 9,974,838
1,000,000 9,997,739
10,000,000 9,999,908
100,000,000 9,999,998
推荐阅读
- c - 是否最好每次都刷新标准输出/标准错误?
- ruby-on-rails - Rails 6 - Phusion error for uninitialized constant URI::Generic
- python - 仅执行大型 jupyter 笔记本中的一些单元格
- rest - LinkedIn API :: 如何获取不记名访问令牌
- python - 键盘 HID 报告
- react-native - 无法将道具传递给外部常量?
- c++ - 如何在系统上使用并行 std::for_each
不见了? - c# - 找不到文件?C# - 获取资源
- python - 根据另一个列表中的值获取列表值
- python-3.x - 如何在异常/错误后继续在 Python 中继续执行程序