为什么Python中的排序后的列表比原始列表更慢？

问题出现的原因是数据的局部性。当整数超过一定大小限制时，它们会被动态分配。当你创建列表时，整数对象会从（主要）附近的内存分配。因此，当你遍历列表时，数据往往会在缓存中，硬件预取器可以将它们放入缓存中。

而在排序后的情况下，对象会被重新排列，导致缓存错失更多。

当然。在按照给定顺序分配内存后随机访问数据比按照原始顺序顺序访问数据更慢。反过来做也可以看到排序与性能无关（除了通过改变访问顺序）。即以s_yes作为范围的起点，s_not作为s_yes的洗牌副本，结果s_not的时间更长。

这个“某个大小”是256。

当然可以改变，我记得它在过去已经改变过一次了。

解决方法：

为了解决排序后列表较慢的问题，可以考虑以下解决方法：

1. 尽量避免在排序后的列表上进行随机访问。由于数据的局部性导致缓存错失，随机访问会导致更多的缓存错失，从而降低性能。如果需要频繁访问排序后的列表中的元素，可以考虑使用其他数据结构或者提前将需要的元素保存到另一个数组中。

2. 如果需要在排序后的列表中进行频繁的插入和删除操作，可以考虑使用其他数据结构，如平衡二叉树或散列表，以获得更高的性能。

3. 如果排序后的列表的长度较小，可以考虑使用其他排序算法，如插入排序或冒泡排序，这些算法在小规模数据上的性能可能更好。

总之，要提高排序后列表的性能，需要注意数据的局部性以及选择合适的数据结构和算法。

为什么Python在排序时列表变慢？

当N个整数对象依次分配时，用于保存它们的内存往往是连续的。因此，按照分配顺序遍历列表时，访问内存中的整数值的顺序也是连续递增的。

但是，如果打乱列表，遍历列表时的访问模式也会被随机化。如果有足够多的不同整数对象，它们无法全部适应缓存中，那么就会出现缓存未命中。

当r等于1或者r等于2时，CPython将这些小整数视为单例，所以即使列表中有1000万个元素，r等于2时，它只包含（最多）100个不同的整数对象，这些数据都可以同时适应缓存。

然而，超过这个范围，你可能会得到越来越多不同的整数对象。当访问模式是随机的时候，硬件缓存变得越来越无用。

具体表现如下：

>>> 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

但是这真的是一个问题吗？我认为按照我的理解，列表`s_yes`是按顺序访问的。我认为实际的排序处理缓存未命中。我希望排序只在第一次访问时发生（当`for`循环开始时），至少我会这样实现。

如果循环为空，那么确实如此。然而，循环中使用了元素的值作为条件，这要求解释器获取实际的值，这就是缓存未命中发生的地方。元素按顺序分配，但它们的值是随机的。因此，当你对列表进行排序时，你得到的是指向随机内存位置的元素，这意味着在获取元素0时加载的缓存在获取元素1时是无用的。在随机情况下，获取元素0时加载的缓存对于获取元素1、2等是有用的。

如果循环体为空（即`pass`），你将看到相同的效果。并且它将更大（比例大于3），因为它不会被额外的语句稀释。

`sorted`会立即进行排序。因此，在循环和计时开始之前。你似乎是一个C++的人。Python整数是对象，列表只存储它们的地址。不要将其视为`vector`，而应视为`vector`。按顺序读取指针对缓存友好。但指向的整数的缓存友好性取决于整数在内存中的位置。

这是C++和Python之间的差异之一，我经常忘记。

记住这个差异对于深入理解Python的工作原理至关重要。

那么，如果OP按顺序创建数字，然后使用`shuffle()`，效果会完全相反。我的理解正确吗？

最终效果是一样的：原始列表按分配顺序访问，打乱后按内存块的“随机”顺序访问。

我要补充一点，即“sorted”并不是真正的驱动因素：任何影响随机排序的方式都会产生相同的效果。在原始情况下，由于值本身是随机的，排序会导致一种随机的排列。

我不完全同意这一点。这绝对是在性能方面需要牢记的一点，但对于日常使用，我并不关心内存表示。

我的评论不仅仅是关于性能的问题。我发现了解底层工作原理是有用的。你可能不同意，并认为在不了解这些知识的情况下，Python仍然可以完美地使用，但我认为你错过了一些东西。

按分配顺序迭代也会减少页面（TLB）未命中。

为什么Python的列表在排序时会变慢？

正如其他人所说，这是因为缓存未命中。而不是因为值的排序性。同样排序的值，但是用新创建的连续对象创建的话，速度会变快（实际上比not情况下还要快一点）：

s_new = [--x for x in s_yes]

只选择一个大小：

对于随机数1000000：
yes 3.6270992755889893
not 1.198620080947876
new 1.02010178565979

查看从一个元素到下一个元素的地址差异（只有10⁶个元素），可以发现，特别是对于s_new，元素在内存中是按顺序排列的（99.2%的时间下一个元素是在32个字节之后），而对于s_yes来说，它们完全不是这样的（只有0.01%的元素是在32个字节之后）：

s_yes:
    741022个不同的地址差异发生。前5个：
    地址差异32发生了102次。
    地址差异0发生了90次。
    地址差异64发生了37次。
    地址差异96发生了17次。
    地址差异128发生了9次。
s_not:
    1048个不同的地址差异发生。前5个：
    地址差异32发生了906649次。
    地址差异96发生了8931次。
    地址差异64发生了1845次。
    地址差异-32发生了1816次。
    地址差异-64发生了1812次。
s_new:
    19个不同的地址差异发生。前5个：
    地址差异32发生了991911次。
    地址差异96发生了7825次。
    地址差异-524192发生了117次。
    地址差异0发生了90次。
    地址差异64发生了37次。

代码如下：

from collections import Counter
for s in 's_yes', 's_not', 's_new':
    print(s + ':')
    ids = list(map(id, eval(s)))
    ctr = Counter(j - i for i, j in zip(ids, ids[1:]))
    print('   ', len(ctr), '个不同的地址差异发生。前5个：')
    for delta, count in ctr.most_common(5):
        print(f'    地址差异{delta}发生了{count}次。')
    print()

一个更好的说明为什么这是关于局部性的例子是，使s_yes = list(range(10**7))，s_not = s_yes[:]，random.shuffle(s_not)。现在，已排序的数组也是连续分配的，而未排序的数组是非连续的，因此计时应该相反。

嗯，我不认为这个例子更好。也许差不多。但它离他们的数据更远。