python heapq merge的内部工作.如何在不生成列表的情况下对列表进行排序 [英] Internal working of python heapq merge. How does it sort a list without generating the list

问题描述

heapq.merge()如何在不生成列表的情况下对列表进行排序?

How does heapq.merge() sort a list even without generate the list?

不确定我是否明确表示.
因此，这是从 leetcode中的超级丑数问题.

Not sure if I stated clear.
So, this is raised from the Super Ugly Number problem at leetcode.

还有这个python代码

And this python code

class Solution(object):
    def nthSuperUglyNumber(self, n, primes):
        """
        :type n: int
        :type primes: List[int]
        :rtype: int
        """
        uglies = [1]
        def gen(prime):
            for ugly in uglies:
                yield ugly * prime
        merged = heapq.merge(*map(gen, primes))
        while len(uglies) < n:
            ugly = next(merged)
            if ugly != uglies[-1]:
                uglies.append(ugly)
        return uglies[-1]

让我很难理解它.在我搜索了收益"的概念后，和"heapq"，在while循环中我还是没有得到，merged如何知道ugly in uglies>n不会小于uglies[n-1].

gave me a hard time understanding it. After I searched the concepts of "yield" and "heapq", I still don't get that in the while loop, how merged know that ugly in uglies>n will not be smaller than uglies[n-1].

推荐答案

heapq.merge的实现是纯Python，您可以

The implementation of heapq.merge is pure Python, you can read its code directly if you want.

，它使用堆来合并传递的可迭代对象.如果迭代器(在这种情况下为生成器)各自按顺序产生其值，则将它们组合在一起，以便其产生的值也按顺序产生.它不会消除重复的值，这就是为什么您显示的代码会检查最新值是否等于上一个值的原因.

As you might guess from the module it's implemented in, it uses a heap to merge the iterables it's passed. If the iterables (generators in this case) each yield their values in order, it will combine them so that the values it yields are also in order. It doesn't eliminate duplicate values, which is why the code you show checks to see if the latest value is equal to the previous one.

这篇关于python heapq merge的内部工作.如何在不生成列表的情况下对列表进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！