python - 如何观看 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 代码级别的列表“内部”工作，而不是通过公共(public) Python __setitem__ 接口(interface)。

比较尝试失败，因为在排序过程中列表确实为空，正如 the source code 解释的那样:

 /* 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 是:

确定性，因此对某个输入进行排序总是会产生相同的步骤。

如果发生异常，很好，不会破坏列表。相反，它只是“停在原处”并使列表处于未完全排序的状态。正如 the code 所说:

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

所以这个想法是:

排序，并在第一次比较时引发异常，以便 Timsort 停止。捕获异常并打印部分排序的列表。

从相同的初始状态再次排序，并在第二次比较时引发异常，以便 Timsort 停止。捕获异常并打印部分排序的列表。

同样，但在第三次比较时异常(exception)。

以此类推，允许越来越多的比较，直到列表完全排序。

这样做的代码(除了它不显示重复的状态，当 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

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

前半部分(32 个元素)被排序，直到它是 1356>ABCDGIJOQRSTVWZabcfijknrsvz 。 Timsort 通过二进制插入排序来做到这一点。输出中的每一行对应一个插入。

后半部分(32 个元素)被排序，直到它是 024789<EFHKLMNPUXYdeghlmopqtuwxy 。再次使用二进制插入排序。

Timsort 合并了两半。输出中的这些行并没有完全显示排序期间的真实状态。我们来看第一步:1356>ABCDGIJOQRSTVWZabcfijknrsvz024789<EFHKLMNPUXYdeghlmopqtuwxy01356>ABCDGIJOQRSTVWZabcfijknrsvz24789<EFHKLMNPUXYdeghlmopqtuwxyTimsort 真正合并两半的方式是将前半移到临时空间。然后从左到右将两半合并到给定的列表中。所以真正在后半部分的 0 移到前面之后，列表看起来像这样:0--------------------------------24789<EFHKLMNPUXYdeghlmopqtuwxy所有破折号都是未占用的空间。现在，当我提出我的异常时，Timsort 不仅像那样离开列表，而且至少将前半部分的剩余元素移回那个未占用的空间。这就是为什么在我的输出中，Timsort 似乎将 0 向左移动，并将整个前半部分向右移动一个索引。那将是低效的，当 Timsort 正常运行时不会发生这种情况，没有我的异常(exception)。

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

请注意，这里的第三阶段从右到左合并(右半部分移到临时空间)，当这更好时，Timsort 会这样做。
在将状态存储在列表 states 中而不是打印它们之后，使用 Pillow 生成该图像的代码:

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)