python - "sorted 1-d iterator"基于 "2-d iterator"(迭代器的笛卡尔积)

Question

我正在寻找一种在 Python 中执行此操作的简洁方法:

假设我有两个迭代器“iter1”和“iter2”:可能是素数生成器和 itertools.count()。我先验地知道两者都是无限的并且单调递增。现在我想对两个参数“op”(可能是 operator.add 或 operator.mul)进行一些简单的操作，并用 every element 计算第一个迭代器的 every element接下来，使用所述操作，然后一次生成一个，排序。显然，这本身就是一个无限序列。 (正如@RyanThompson 在评论中提到的:这将被称为这些序列的 Cartesian Product...或者，更确切地说，该产品的一维排序。)

最好的方法是:

• 在可迭代中总结“iter1”、“iter2”和“op”，它本身产生单调递增输出的值。

允许的简化假设:

• 如果有帮助，我们可以假设 op(a,b) >= a 和 op(a,b) >= b。
• 如果有帮助，我们可以假设 op(a,b) > op(a,c) 对于所有 b > c。

也允许:

• 同样可以接受的是一个迭代器，它以“通常增加”的顺序产生值......我的意思是 iterable 偶尔会给我一个比前一个少的数字，但它会以某种方式使“辅助信息”可用(通过对象上的方法)会说“我不保证我给你的下一个值会大于我刚刚给你的值，但我确信所有 future 的值至少会大于 N。 “....并且“N”本身是单调递增的。

我能想到的唯一方法是一种“对角化”过程，我在其中保留越来越多的部分处理的可迭代对象，并“向前看”所有可能的 next() 值中的最小值，并产生那个。但是，即使在我开始编写代码之前，heapq 和一堆 deque 的这种奇怪的聚集看起来也很古怪。

请:不要根据我的例子提到素数或计数() 的事实来回答你的问题....我对这个概念有多种用途，但与素数和计数无关( ).

---

更新:天啊!多么好的讨论!还有一些很好的答案，解释得很透彻。非常感谢。 StackOverflow 摇滚；你们摇滚。

我将很快更深入地研究每个答案，并为示例代码注入(inject)活力。从我目前所读的内容来看，我最初的怀疑得到证实，没有“简单的 Python 惯用语”可以做到这一点。相反，无论如何，我无法避免无限期地保留 iter1 和 iter2 的所有生成值。

FWIW:如果您想尝试您的解决方案，这里有一个官方“测试用例”。

import operator

def powers_of_ten():
    n = 0
    while True:
        yield 10**n
        n += 1

def series_of_nines():
    yield 1
    n = 1
    while True:
        yield int("9"*n)
        n += 1

op = operator.mul
iter1 = powers_of_ten()
iter2 = series_of_nines()

# given (iter1, iter2, op), create an iterator that yields:
# [1, 9, 10, 90, 99, 100, 900, 990, 999, 1000, 9000, 9900, 9990, 9999, 10000, ...]

Answer 1

import heapq
import itertools
import operator


def increasing(fn, left, right):
    """
    Given two never decreasing iterators produce another iterator
    resulting from passing the value from left and right to fn.
    This iterator should also be never decreasing.
    """
    # Imagine an infinite 2D-grid.
    # Each column corresponds to an entry from right
    # Each row corresponds to an entry from left
    # Each cell correspond to apply fn to those two values

    # If the number of columns were finite, then we could easily solve
    # this problem by keeping track of our current position in each column
    # in each iteration, we'd take the smallest value report it, and then
    # move down in that column. This works because the values must increase
    # as we move down the column. That means the current set of values
    # under consideration must include the lowest value not yet reported

    # To extend this to infinite columns, at any point we always track a finite
    # number of columns. The last column current tracked is always in the top row
    # if it moves down from the top row, we add a new column which starts at the top row
    # because the values are increasing as we move to the right, we know that
    # this last column is always lower then any columns that come after it





    # Due to infinities, we need to keep track of all
    # items we've ever seen. So we put them in this list
    # The list contains the first part of the incoming iterators that
    # we have explored
    left_items = [next(left)]
    right_items = [next(right)]

    # we use a heap data structure, it allows us to efficiently
    # find the lowest of all value under consideration
    heap = []

    def add_value(left_index, right_index):
        """
        Add the value result from combining the indexed attributes
        from the two iterators. Assumes that the values have already
        been copied into the lists
        """
        value = fn( left_items[left_index], right_items[right_index] )
        # the value on the heap has the index and value.
        # since the value is first, low values will be "first" on the heap
        heapq.heappush( heap, (value, left_index, right_index) )

    # we know that every other value must be larger then 
    # this one. 
    add_value(0,0)

    # I assume the incoming iterators are infinite
    while True:
        # fetch the lowest of all values under consideration
        value, left_index, right_index = heapq.heappop(heap)

        # produce it
        yield value

        # add moving down the column
        if left_index + 1 == len(left_items):
            left_items.append(next(left))

        add_value(left_index+1, right_index)

        # if this was the first row in this column, add another column
        if left_index == 0:
            right_items.append( next(right) )
            add_value(0, right_index+1)






def fib():
    a = 1
    b = 1
    while True:
        yield a
        a,b = b,a+b



r = increasing(operator.add, fib(), itertools.count() )
for x in range(100):
    print next(r)