基于“2-d iterator”（迭代器的笛卡尔积）的“已排序一维迭代器”。

Question

基于“2-d iterator”（迭代器的笛卡尔积）的“已排序一维迭代器”。

13

我正在寻找一种在Python中实现这个的简洁方法：

假设我有两个迭代器"iter1"和"iter2"：可能是一个素数生成器和itertools.count()。我预先知道它们都是无限的，并且单调递增的。现在我想要对两个参数"op"（例如operator.add或operator.mul）进行一些简单的操作，并使用该操作计算第一个迭代器的每个元素与下一个迭代器的每个元素，然后按顺序一个一个地产生它们。显然，这本身就是一个无限序列。（如@RyanThompson所述：这将被称为这些序列的笛卡尔积...或者更确切地说，是该积的一维排序。）

最好的方法是什么：

1. 将"iter1"、"iter2"和"op"封装在一个可迭代对象中，该对象本身按单调递增的输出产生值。

允许的简化假设：

1. 如果有帮助，我们可以假设op(a,b) >= a并且op(a,b) >= b。 2. 如果有帮助，我们可以假设op(a,b)>op(a,c)对所有b>c。

另外一种可接受的迭代器是以“一般递增”的顺序产生值的迭代器……我的意思是，可迭代对象偶尔会给我一个比上一个小的数字，但它会以某种方式提供“侧面信息”（例如通过对象上的方法），告诉我：“我不能保证我给你的下一个值将大于我刚才给你的值，但我确信所有未来的值至少都将大于N。”……而“N”本身是单调递增的。

我能想到的唯一方法是一种“对角线化”过程，在这个过程中，我会保留越来越多的部分处理的可迭代对象，并“向前看”找到所有可能的next()值中最小的那个，并产生它。但是这种奇怪的堆和一堆双端队列的聚合似乎太过离奇，甚至在我开始编码之前就已经如此。

请注意：请不要基于我的示例提到质数或count()来回答问题……我有几个非与质数和count()相关的用途，需要这个概念。

更新：哇！讨论太棒了！有些回答解释得非常透彻。非常感谢。StackOverflow很棒，你们也很棒。

我很快就会更深入地研究每个答案，并测试代码示例。从我目前阅读的内容来看，我的最初怀疑已经得到证实，即没有“简单的Python习惯用语”可以做到这一点。不管怎样，我无法避免持续保留iter1和iter2的所有产生值。

顺便说一句：如果你想尝试解决方案，这里有一个官方的“测试用例”。

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, ...]

- Dan H

假设对于所有的b > c，op(b,a) > op(c,a)，这种假设也被允许吗？（像加和乘一样，op(a,b) = op(b,a) 吗？） - Baffe Boyois

1

@Dan H：你过于笼统地回答了这个问题。如果 op 是 (+) ，那么你提出的对角线算法可以奏效。另一方面，如果你与 lambda *args:random.choice(args) 合并，那么你根本无法合并... 请问你的实际问题是什么？ - Jochen Ritzel

@Jochen: 同意。@Dan：你可以给更多的例子说明你会如何使用它吗？ - Claudiu

@BaffeBoyois：是的，你也可以假设b > c的关系。 - Dan H

@RyanThompson: 那就是我在寻找的术语：_“笛卡尔积”_。 - Dan H

显示剩余6条评论

6个回答

4

将序列定义为:

a1 <= a2 <= a3 ...
b1 <= b2 <= b3 ...

让 a1b1 简写为 op(a1,b1)。

根据您允许的假设（非常重要），您可以知道以下内容：

max(a1, b1) <= a1b1 <= a1b2 <= a1b3 ...
   <=
max(a2, b1) <= a2b1 <= a2b2 <= a2b3 ...
   <=
max(a3, b1) <= a3b1 <= a3b2 <= a3b3 ...
    .     .
    .      .
    .       .

您需要做的是：生成 a1b1。您知道，如果继续增加 b 变量，将只会获得更高的值。现在问题是：通过增加 a 变量，是否存在一个较小的值？您的下限是 min(a1, b1)，因此您必须增加 a 值，直到 min(ax,b1) >= a1b1。一旦达到该点，您可以找到 anb1 中最小的值，其中 1 <= n <= x，并安全地产生它。

然后，您将拥有多个水平链，您需要跟踪这些链。每次有一个值超过 min(ax,b1)，您必须增加 x（添加更多链），直到安全发出比之前更大的值为止。

只是一个起点……我现在没有时间编码。

编辑：哦，这恰好就是您已经拥有的内容。嗯，没有更多的信息，这就是您所能做的，因为我非常确定，在数学上，这是必要的。

编辑2：至于您的“可接受”解决方案：您可以按照递增顺序产生 a1bn，返回 N = P 作为 min(a1,b1)。您需要更具体地说明。您说话的口气好像对于您通常想看到的内容、您想通过两个可迭代对象进行进展的一般方式，您有一个启发式方法，但是没有告诉我们它是什么，我不知道如何做得更好。

更新：温斯顿的解决方案很好，但做出了一个假设：如果 b>a，则 op(a,c) > op(b,c)。但是，我们确实知道 op(a,b)>=a 和 op(a,b)>=b。这是我的解决方案，它接受第二个假设，而不是温斯顿采用的假设。他的代码结构很好。

def increasing(fn, left, right):
    left_items = [next(left)]
    right_items = [next(right)]

    #columns are (column value, right index)
    columns = [(fn(left_items[0],right_items[0]),0)]

    while True:
        #find the current smallest value
        min_col_index = min(xrange(len(columns)), key=lambda i:columns[i][0])

        #generate columns until it's impossible to get a smaller value
        while right_items[0] <= columns[min_col_index][0] and \
              left_items[-1] <= columns[min_col_index][0]:
            next_left = next(left)

            left_items.append(next_left)
            columns.append((fn(next_left, right_items[0]),0))

            if columns[-1][0] < columns[min_col_index][0]:
                min_col_index = len(columns)-1

        #yield the smallest value
        yield columns[min_col_index][0]

        #move down that column
        val, right_index = columns[min_col_index]

        #make sure that right value is generated:
        while right_index+1 >= len(right_items):
            right_items.append(next(right))

        columns[min_col_index] = (fn(left_items[min_col_index],right_items[right_index+1]),
                                  right_index+1)
        #repeat

对于一个展示差异的（病态的）输入，请考虑以下内容：

def pathological_one():
    cur = 0
    while True:
        yield cur
        cur += 100

def pathological_two():
    cur = 0
    while True:
        yield cur
        cur += 100

lookup = [
    [1,   666, 500],
    [666, 666, 666],
    [666, 666, 666],
    [666, 666, 666]]

def pathological_op(a, b):
    if a >= 300 or b >= 400: return 1005
    return lookup[b/100][a/100]

r = increasing(pathological_op, pathological_one(), pathological_two())
for x in range(15):
    print next(r)

温斯顿的回答如下：

虽然我的版本是：

- Claudiu

2

你想要处理两个单调递增的序列，并且（懒惰地）计算它们之间的乘法（或加法或其他操作）表格，这是一个二维数组。然后，你想将该二维数组的元素按排序顺序排列，并迭代遍历它们。

通常情况下，这是不可能的。但是，如果你的序列和操作使得你能够对表的行和列做出一定的保证，那么你就可以取得一些进展。例如，假设你的序列仅包含单调递增的正整数，并且操作为乘法（与你的示例相同）。在这种情况下，我们知道数组的每一行和每一列都是单调递增的序列。在这种情况下，你不需要计算整个数组，而只需要计算其中的部分。具体来说，你必须跟踪以下内容：

- 你曾经使用过的行数 - 每个已使用的行中你已获取的元素数量 - 你曾经使用过的第一个输入序列和第二个输入序列的每个元素，以及每个序列多一个元素

为了计算迭代器中的下一个元素，你必须执行以下操作：

- 对于你曾经使用过的每一行，请计算该行中的“下一个”值。例如，如果你从第1行使用了5个值，则通过从第一个序列中获取第1个值和从第二个序列中获取第6个值（两者都已被缓存）并将操作（乘法）应用于它们来计算第6个值（i=1，j=6）。还需计算第一行未使用的第一个值。 - 取所有计算出的值的最小值。将其作为下一个元素返回。 - 增加上一步中抽样元素所在行的计数器。如果你从一个新的未使用过的行中取出了元素，则必须增加你所使用的行数的计数，并初始化该行的新计数器为1。如有必要，还需计算一或两个输入序列的更多值。

这个过程有点复杂，特别是请注意，在最坏情况下，为了计算N个值，你必须保存与 N 成比例的状态量。这与典型的生成器形成了鲜明对比，后者只需要恒定的空间即可迭代它的元素，而不管长度如何。

总之，在某些假设下可以实现该方法，并且可以提供类似生成器的接口，但不能以“流式”方式进行处理，因为为了按正确的顺序迭代遍历元素，你需要保存大量的状态。

- Ryan C. Thompson

谢谢；非常棒的分析，也感谢您对其他帖子的评论。 - Dan H

2

让我从一个例子开始，展示如何直观地解决这个问题。

因为在代码中阅读行内内容有点乏味，所以我会引入一些符号：

符号说明：

- i1表示iter1。i10表示iter1的第一个元素。iter2同理。 - ※表示op运算符。

直观解法：

通过使用简化假设2，我们知道i10 ※ i20是最终迭代器中将产生的最小元素。下一个元素将是i10 ※ i21和i11 ※ i20中较小的那个。

假设i10 ※ i21更小，则会产生该元素。接下来，您将产生i11 ※ i20、i11 ※ i20和i11 ※ i21中较小的那个。

表达式作为DAG的遍历：

您在这里面对的是一个图遍历问题。首先，将问题视为树。树的根是i10 ※ i20。该节点及其下方的每个节点都有两个子节点。i1x ※ i2y的两个子节点分别是：一个子节点是i1x+1 ※ i2y，另一个子节点是i1x ※ i2y+1。根据您的第二个假设，我们知道i1x ※ i2y小于其两个子节点。

（事实上，正如Ryan在评论中提到的那样，这是一个有向无环图，或DAG。一些“父母”与其他“父亲”节点共享“孩子”。）

现在，我们需要保留一个“frontier”——可以作为下一个返回节点的节点集合。在返回一个节点之后，我们将其两个子节点添加到frontier中。为了选择下一个要访问（并从新迭代器中返回）的节点，我们比较frontier中所有节点的值。我们选择具有最小值的节点并返回它。然后，我们再次将其两个子节点添加到frontier中。如果该子节点已经在frontier中（作为其他父节点的子节点添加），则忽略它。

存储frontier

由于您主要关心节点的值，因此按值索引存储这些节点是有意义的。因此，您可能有兴趣使用字典。该字典中的键应为节点的值。该字典中的值应为包含单个节点的列表。因为节点中唯一的标识信息是操作数对，所以可以将单个节点存储为包含两个操作数的二元组。

实际上，在几次迭代之后，您的frontier可能如下所示：

>>> frontier
{1: [(2, 3), (2, 4)], 2: [(3, 5), (5, 4)], 3: [(1, 6)], 4: [(6, 3)]}

其他实现注意事项

由于迭代器不支持随机访问，您需要保留您的前两个迭代器生成的值，直到它们不再需要。每当一个值被您的前沿中的任何值引用时，您将知道该值仍然需要。一旦前沿中的所有节点引用的值晚于/大于您存储的值，您将知道该值不再需要。例如，只有 i1₂₁、i1₂₅、i1₃₃ ... 被引用时，i1₂₀ 就不再需要了。

正如 Ryan 所提到的，每个迭代器生成的值都将被无限次使用。因此，每个生成的值都需要保存。

不切实际

不幸的是，为了确保元素仅以递增顺序返回，前沿将无限增长。您的记忆化值也将无限增长。这可能是您可以通过使问题更少见来解决的问题，但这应该是一个很好的起点。

- Wesley

1

你必须保存来自两个迭代器的每个值。你不能丢弃它们中的任何一个，至少不能永久性地丢弃，因为每个迭代器中的每个值将被无限次使用。 - Ryan C. Thompson

经过一段时间的思考，似乎你是对的。我会编辑我的回答。 - Wesley

1

此外，您不必维护树形结构的前沿，而是要维护有向无环图（DAG）的前沿。例如，i1_2※i2_2 既是 i1_1※i2_2 的子节点，也是 i1_2※i2_1 的子节点。 - Ryan C. Thompson

下一个元素不一定是a2b1或a1b2。a3b1可能比a1b2小，a4b1、a5b1等也可能如此。请看我的答案。 - Claudiu

@Wesley：感谢您的贡献！并且您赢得了“最佳使用※字符的奖项”，;-) - Dan H

0

使用生成器，它们只是作为函数编写的迭代器，可以产生结果。在这种情况下，您可以为iter1和iter2编写生成器，并编写另一个生成器来包装它们并产生它们的结果（或对它们进行计算，或者它们的结果历史记录）。

从我阅读问题的描述中，您想要像这样的东西，它将使用所述操作计算第一个迭代器的每个元素与下一个迭代器的每个元素，您还声明希望以单调递增的输出方式包装“iter1”、“iter2”和“op”的可迭代对象。我建议使用生成器来解决这个问题，它提供了一个简单的解决方案。

import itertools

def prime_gen():
    D, q = {}, 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

def infinite_gen(op, iter1, iter2):
    while True:
        yield op(iter1.next(), iter2.next())

>>> gen = infinite_gen(operator.mul, prime_gen(), itertools.count())

>>> gen.next()
<<< 0

>>> gen.next()
<<< 3

>>> gen.next()
<<< 10

生成器提供了很大的灵活性，因此编写iter1和iter2作为生成器应该相当容易，以按照您想要的顺序返回所需的值。您还可以考虑使用协程，它允许您将值发送到一个生成器中。

- Zach Kelling

抱歉，这不是我要找的。如果我可以使用序列符号，你给我的是：对于所有i，产生primes[i]+count[i]... 这是一个“一维”的输出。我要找的是对于所有i,j，产生primes[i]+count[j]，并按从低到高排序。 - Dan H

@Dan H 生成器非常灵活，如果您能提供所需输出的示例，我可以重写函数以适应。 - Zach Kelling

@zeekay：请仔细阅读问题：“请不要根据我提到的质数或count()来回答我的问题......我有很多与质数和count()无关的用途。”函数可能会有所不同，您的代码假设一些与他正在寻找的通用函数不符的事实。 - Claudiu

@Claudiu 所以它应该产生 [op(a1,b1),op(a2,b1)] 然后是 [op(a1,b2),op(a2,b2)] 接着是 [op(a1,b3),op(a2,b3)]？还是它会字面上产生一个无限序列 op(a1,b1), op(a1,b2),op(a1,b3),等等 并在某个不确定的时间增加 a 并开始产生 op(a2,b1),op(a2,b2)？ - Zach Kelling

@Claudiu 啊！我明白了，因此在Winston Hewit的答案中使用heapq是这种情况的完美解决方案。 - Zach Kelling

显示剩余7条评论

0

其他答案中的讨论指出，无论算法如何，每个 a[n] 都必须保持可用以供每个新的 b[n] 使用，因此可能需要无限的存储空间。如果您取消“输入”必须是两个迭代器的限制，而只要求它们是序列（可索引或仅可重复生成的内容），那么我认为您的所有状态突然就会崩溃成一个数字：您返回的最后一个值。知道了上一个结果值，您可以搜索输出空间以查找下一个值。（如果您想正确地发出重复项，则可能还需要跟踪结果已返回的次数）

对于一对序列，您有一个简单的递归关系：

result(n) = f(seq1, seq1, result(n-1))

f(seq1, seq1, p) 在输出空间 q 中搜索最小值，使得 q > p。在实际应用中，您可能会将序列作为记忆化函数，并选择搜索算法以避免过度使用记忆化项池。

- Ben Jackson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Winston Ewert · Accepted Answer

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)