如何观看 Timsort 移动元素？

Question

我想对列表进行排序并观察/可视化 Python 的排序算法Timsort如何移动元素。

第一次尝试：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代码级别，而不是通过公共的Python要去__setitem__接口。
• 比较尝试失败，因为在排序期间列表确实为空，如源代码所述：

   /* The list is temporarily made empty, so that mutations performed
   * by comparison functions can't affect the slice of memory we're
   * sorting (allowing mutations during sorting is a core-dump
   * factory, since ob_item may change).
  

但是，如果列表为空，我们如何在排序过程中观察列表？简单：我们没有。不是在排序期间。但经过部分排序。

Timsort 是：

• 确定性，因此对某个输入进行排序总是导致相同的步骤。
• 如果发生异常，就不会破坏列表。相反，它只是“停在原地”，并使列表处于未完全排序的状态。正如代码所说：

  /* [...]  Even in case of error, the
   * list will be some permutation of its input state (nothing is lost or
   * duplicated).
  

所以这个想法是：

• 排序，并在第一次比较时引发异常，以便 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

输出，讨论如下：

 /* The list is temporarily made empty, so that mutations performed
 * by comparison functions can't affect the slice of memory we're
 * sorting (allowing mutations during sorting is a core-dump
 * factory, since ob_item may change).

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

1. 前半部分（32 个元素）被排序，直到它是1356>ABCDGIJOQRSTVWZabcfijknrsvz. Timsort 使用二进制插入排序来做到这一点。输出中的每一行对应一个插入。
2. 后半部分（32 个元素）被排序，直到它是024789<EFHKLMNPUXYdeghlmopqtuwxy. 再次使用二进制插入排序。
3. Timsort 合并了这两部分。输出中的这些行并没有完全显示排序期间的真实状态。让我们看第一步：
   1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeghlmopqtuwxy
01356>ABCDGIJOQRSTVWZabcfijknrsvz24789<EFHKLMNPUXYdeghlmopqtuwxy
   Timsort 真正合并两半的方式是将前半移到临时空间。然后将两半从左到右合并到给定的列表中。所以真的在0从下半场移到前面之后，列表看起来像这样：
   0--------------------------------24789<EFHKLMNPUXYdeghlmopqtuwxy
   所有的破折号都没有被占用。现在，当我提出我的异常时，Timsort 不仅像那样离开列表，而且至少将前半部分的剩余元素移回未占用的空间。这就是为什么在我的输出中，看起来 Timsort 正在移动0将整个前半部分向右移动一个索引。那将是低效的，而且在 Timsort 正常运行时不会发生这种情况，没有我的例外。

您还可以在顶部的动画图像中看到这三个阶段。在这个“屏幕保护程序”版本中，我向下滚动上面的输出。我认为它看起来很酷（希望它看起来有点像Matrix coderain）但我发现它不太清楚：

请注意，这里的第三阶段从右到左合并（右半部分移出到临时空间），Timsort 在更好的时候这样做。

在将状态存储在列表中而不是打印它们之后，使用Pillow生成该图像的代码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)