python - 为什么 "yield"关键字没有在我的应用程序中生成预期的生成器？ (归并排序算法)

Question

为什么我的 yield 关键字没有产生预期的输出？

我正在使用递归算法(合并排序)并使用 yield 以便每次更改(排序)时我都可以遍历列表。

def MergeSort(lst):

    if len(lst) > 1:
        middle = len(lst)//2
        lefthalf = lst[:middle]
        righthalf = lst[middle:]

        MergeSort(lefthalf)
        MergeSort(righthalf)

        i,j,k= 0,0,0

        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] < righthalf[j]:
                lst[k] = lefthalf[i]
                i+=1
            else:
                lst[k] = righthalf[j]
                j+=1

            k+=1

        while i<len(lefthalf):
            lst[k]=lefthalf[i]
            i+=1
            k+=1

        while j<len(righthalf):
            lst[k]=righthalf[j]
            j+=1
            k+=1

        yield lst

a = MergeSort([2,3,566,78,8])
for i in a:
    print(i)
[2, 3, 566, 78, 8]

相反，我希望实现如下目标:(随着算法的运行)

[2, 3, 566, 78, 8]
[2, 3, 566, 8, 78]
[2, 3, 8, 78, 566]

如果我使用 return 语句，它将正常工作并按预期对列表进行排序，但是当我使用 yield 时，我无法获得合适的生成器。我还尝试将 yield 放在 while 语句和几乎所有其他地方。我怎样才能解决这个问题？我错过了什么？

Answer 1

因为您使 MergeSort 成为生成器，而生成器是惰性的，所以您的递归调用实际上不会进行任何排序；他们只是返回生成器，在您遍历它们之前不会做任何工作。你的整个函数也只产生一个列表，因为它只包含一个 yield 语句，而且它不在循环中所以它只执行一次。

解决这两个问题的方法是使用 yield from MergeSort(...) 来耗尽您递归创建的生成器。这将使它们耗尽，以便它们进行排序工作，并且还会导致外部生成器产生内部生成器产生的结果。因此，更改这两行:

        yield from MergeSort(lefthalf)
        yield from MergeSort(righthalf)

例子:

>>> for i in MergeSort([2, 3, 566, 78, 8]):
...     print(i)
... 
[2, 3]
[8, 78]
[8, 78, 566]
[2, 3, 8, 78, 566]

请注意，您没有看到相同长度的列表；递归调用在较短的列表中，因此它们会产生较短的列表。您也没有在基本情况下看到长度为 1 的列表，因为您的 yield lst 语句位于 if len(lst) > 1: block 内。如果您取消该行的缩进以便 yield lst 是无条件的，您可以看到每次调用的结果:

>>> for i in MergeSort([2, 3, 566, 78, 8]):
...     print(i)
... 
[2]
[3]
[2, 3]
[566]
[78]
[8]
[8, 78]
[8, 78, 566]
[2, 3, 8, 78, 566]