如何观看Timsort移动元素？

Question

我想对列表进行排序，并观察/可视化Python的排序算法蒂姆塞德是如何移动元素的。

第一次尝试：list的一个子类，它在每次更改之后打印自己：

class List(list):
    def __setitem__(self, index, value):
        list.__setitem__(self, index, value)
        print(self)

当我自己改变元素时，这是可行的，但是在sort .什么也没有：

>>> a = List([None] * 2)
>>> a[0] = 'S'
['S', None]
>>> a[1] = 'P'
['S', 'P']
>>> a.sort()
>>>

第二次尝试：在元素的每个比较处打印列表(在全局变量a中)：

class Str(str):
    def __lt__(self, other):
        print(a)
        return other > self

但名单上总是..。空的？

>>> a = list(map(Str, 'test'))
>>> a.sort()
[]
[]
[]
[]
[]
[]
>>>

为什么这些尝试失败了，有什么方法可以观察Timsort在做什么吗？

Answer 1

是的，可以观察到。我做了，这里有一个可视化：

​

​

另一个元素更多：

​

​

为什么你的尝试失败了？

• list子类失败是因为sort在C代码级别“在列表中”工作，而不是通过公共__setitem__接口。
• 比较尝试失败了，因为列表在排序期间确实是空的，正如源代码解释的那样: /*列表暂时为空，因此通过比较函数执行的突变不会影响我们正在排序的内存片(允许排序期间的突变是一个核心转储*工厂，因为ob_item可能会改变)。

但是，如果列表是空的，我们如何在排序过程中观察它呢？简单点:我们没有。在分类的时候没有。但经过部分分类。

Timsort是：

• 确定性，因此对某一输入进行排序总是会导致相同的步骤。
• 如果出现异常，就不会销毁列表。相反，它只是“停留在它所在的地方”，并使列表处于未完全排序的状态。正如代码所说: /* ..。即使出现错误，*列表也将是其输入状态的某种排列(没有丢失或*复制)。

所以我的想法是：

• 排序，并在第一次比较时引发异常，以便Timsort停止。捕获异常并打印部分排序列表。
• 再次排序，从相同的初始状态，并在第二次比较时引发异常，以便Timsort停止。捕获异常并打印部分排序列表。
• 同样，但在第三次比较时有例外。
• 等等，允许越来越多的比较，直到列表被完全排序。

这样做的代码(除非它没有显示重复的状态，这是在Timsort在下一步之前进行几次比较时发生的)：

import string
from random import shuffle
from itertools import count

class Str(str):
    def __lt__(self, other):
        global allowed_comparisons
        if allowed_comparisons == 0:
            raise Exception
        allowed_comparisons -= 1
        return other > self

a = list(string.ascii_letters + string.digits + '<>')
shuffle(a)

shown = None
for allowed_comparisons in count():
    try:
        b = list(map(Str, a))
        b.sort()
    except:
        pass
    state = ''.join(b)
    if state != shown:
        print(state)
        shown = state
    if list(state) == sorted(state):
        break

产出，下文讨论：

k1z5Qi>jCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1kz5Qi>jCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15kzQi>jCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15Qkzi>jCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15Qikz>jCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>QikzjCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>QijkzCVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQijkzVsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQVijkzsfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQVijkszfRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQVfijkszRbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQRVfijkszbBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>CQRVbfijkszBWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCQRVbfijkszWSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCQRVWbfijkszSnJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCQRSVWbfijksznJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCQRSVWbfijknszJOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCJQRSVWbfijknszOD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCJOQRSVWbfijknszD6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
15>BCDJOQRSVWbfijknsz6AZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
156>BCDJOQRSVWbfijknszAZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
156>ABCDJOQRSVWbfijknszZ3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
156>ABCDJOQRSVWZbfijknsz3cGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDJOQRSVWZbfijknszcGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDJOQRSVWZbcfijknszGTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGJOQRSVWZbcfijknszTaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGJOQRSTVWZbcfijknszaIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGJOQRSTVWZabcfijknszIrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknszrvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrszvw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvzw0pePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0wpePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0pwePH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0epwPH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0PepwH94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0HPepw94UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz09HPepw4UgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049HPepwUgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049HPUepwgqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049HPUegpwqEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049HPUegpqwEK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049EHPUegpqwK2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz049EHKPUegpqw2FNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0249EHKPUegpqwFNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0249EFHKPUegpqwNYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0249EFHKNPUegpqwYL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0249EFHKNPUYegpqwL7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz0249EFHKLNPUYegpqw7Xdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUYegpqwXdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUXYegpqwdltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUXYdegpqwltoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUXYdeglpqwtoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUXYdeglpqtwoxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz02479EFHKLNPUXYdeglopqtwxy8uM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789EFHKLNPUXYdeglopqtwxyuM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789EFHKLNPUXYdeglopqtuwxyM<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789EFHKLMNPUXYdeglopqtuwxy<hm
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeglopqtuwxyhm
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeghlopqtuwxym
1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeghlmopqtuwxy
01356>ABCDGIJOQRSTVWZabcfijknrsvz24789<EFHKLMNPUXYdeghlmopqtuwxy
012356>ABCDGIJOQRSTVWZabcfijknrsvz4789<EFHKLMNPUXYdeghlmopqtuwxy
0123456>ABCDGIJOQRSTVWZabcfijknrsvz789<EFHKLMNPUXYdeghlmopqtuwxy
01234567>ABCDGIJOQRSTVWZabcfijknrsvz89<EFHKLMNPUXYdeghlmopqtuwxy
012345678>ABCDGIJOQRSTVWZabcfijknrsvz9<EFHKLMNPUXYdeghlmopqtuwxy
0123456789>ABCDGIJOQRSTVWZabcfijknrsvz<EFHKLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDGIJOQRSTVWZabcfijknrsvzEFHKLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEGIJOQRSTVWZabcfijknrsvzFHKLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGIJOQRSTVWZabcfijknrsvzHKLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJOQRSTVWZabcfijknrsvzKLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKOQRSTVWZabcfijknrsvzLMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLOQRSTVWZabcfijknrsvzMNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMOQRSTVWZabcfijknrsvzNPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOQRSTVWZabcfijknrsvzPUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTVWZabcfijknrsvzUXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWZabcfijknrsvzXYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXZabcfijknrsvzYdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcfijknrsvzdeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdfijknrsvzeghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefijknrsvzghlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefgijknrsvzhlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijknrsvzlmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklnrsvzmopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnrsvzopqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnorsvzpqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnoprsvzqtuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrsvztuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstvzuwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvzwxy
0123456789<>ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

在上面的输出中，注意有三个阶段：

1. 前半部分(32个元素)被排序，直到它是1356>ABCDGIJOQRSTVWZabcfijknrsvz。Timsort使用二进制插入排序来实现这一点。输出中的每一行对应于一个插入。
2. 后半段(32个元素)被排序，直到它是024789<EFHKLMNPUXYdeghlmopqtuwxy。再次使用二进制插入排序。
3. 蒂姆塞德合并了这两部分。输出中的这些行在排序过程中不太显示实际状态。让我们看一下第一步： 1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeghlmopqtuwxy 01356>ABCDGIJOQRSTVWZabcfijknrsvz24789<EFHKLMNPUXYdeghlmopqtuwxy 蒂姆塞德真正合并两半的方式是将上半场移出，移到临时空间。然后将这两个部分从左到右合并到给定的列表中。因此，在下半场的0被移到最前面之后，列表看起来如下： 0--------------------------------24789<EFHKLMNPUXYdeghlmopqtuwxy 所有的破折号都是空的。现在，当我提出我的异常时，Timsort不只是这样离开列表，而且至少很好地将第一部分的剩余元素移回了未占用的空间。这就是为什么在我的输出中，Timsort将0向左移动，并将整个前半部分移动到一个指数的右边。这将是低效的，而且不是Timsort正常运行时所发生的情况，除了我的例外。

你也可以在我的动画形象上面看到这三个阶段。在这个“屏幕保护程序”版本中，我向下滚动上面的输出。我认为它看起来很酷(希望它看起来有点像矩阵码雨)，但我发现它不那么清晰：

​

​

请注意，在这里，第三阶段从右向左合并(右半移到临时空间)，Timsort会在更好的情况下这样做。

在将状态存储在列表枕头中而不是打印状态之后，使用states生成该映像的代码：

from PIL import Image, ImageDraw

images = []
for i in range(len(states) - 14):
    img = Image.new('RGB', (384, 225), (0, 0, 0))
    text = '\n'.join(states[i:i+15])
    d = ImageDraw.Draw(img)
    d.multiline_text((0,0), text, fill=(0, 200, 0))
    img = img.resize((384*2, 225*2), 0)
    images.append(img)
images[0].save('timatrix.png', save_all=True, append_images=images[1:],
               optimize=False, duration=100, loop=0)

Answer 2

如果您的目标是了解算法的操作，那么了解元素的特定值和位置比查看堆栈上的运行长度更重要。这些长度在Stefan Pochmann的动画中的锯齿上是可见的。

这些游程揭示了数据数组中指针(索引)堆栈增长的对数极限，这是基本时间排序算法的一个重要特征。下面是一个更清晰的表示方式的示例，它只显示堆栈索引：

  entry [0, 53, 106]
   exit [0, 106]
  entry [0, 106, 159, 212]
   exit [0, 106, 212]
  entry [0, 106, 212]
   exit [0, 212]
  entry [0, 212, 265, 318]
   exit [0, 212, 318]
  entry [0, 212, 318, 371, 424]
   exit [0, 212, 318, 424]
  entry [0, 212, 318, 424]
   exit [0, 212, 424]
  entry [0, 212, 424]
   exit [0, 424]
  entry [0, 424, 477, 530]
   exit [0, 424, 530]
  entry [0, 424, 530, 583, 636]
   exit [0, 424, 530, 636]
  entry [0, 424, 530, 636]
   exit [0, 424, 636]
  entry [0, 424, 636, 689, 742]
   exit [0, 424, 636, 742]
  entry [0, 424, 636, 742, 795, 836]
   exit [0, 424, 636, 742, 836]
  entry [0, 424, 636, 742, 836]
   exit [0, 424, 636, 836]
  entry [0, 424, 636, 836]
   exit [0, 424, 836]
  entry [0, 424, 836]
   exit [0, 836]
Functional trial 0 sorted 836 random data items.

索引之间的数据已按升序排序。标签entry显示合并例程入口点的堆栈状态，exit显示退出时的状态。当entry等于上一次exit时，由于不变量在继续创建下一次运行之前多次失败，将合并多个运行。从堆栈顶部索引到数组大小的数据是timsort在数组的线性扫描中尚未检查的数据。当堆栈顶部索引等于数组大小时，timsort已经完成扫描，但可能需要通过一些合并来完成。在本例中，tim排序在不变量第一次失败和合并开始之前生成两次运行，并通过合并五次运行来完成。

虽然这种类型的输出可以通过使用Stefan Pochmann的代码进行更复杂的后期分析来生成，但是这些数据是通过以下timsort的实现生成的：

https://gist.github.com/ruminations/89a045dc0ef7edfb92304a0de0752ee0

通过取消对merge方法中的两个merge语句( 263和303行)的注释，并在测试套件的末尾添加一个break语句。该代码对于处理算法和获得对其操作的一些直观理解非常有用。