为什么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() 中的界限时，排序列表上的循环会变慢。为什么？

缓存未命中。什么时候Nint 对象是连续分配的，保留用于保存它们的内存往往位于连续的块中。因此，按分配顺序爬行列表往往也会访问按顺序、连续、递增顺序保存 int 值的内存。

将其打乱，并且在列表上爬行时的访问模式也是随机的。缓存未命中的情况比比皆是，只要有足够多的不同 int 对象，而它们并不全部适合缓存。

At r==1, and 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