我正在寻找一种在Python中执行此操作的简洁方法:
假设我有两个迭代器"iter1"和"iter2":也许是一个素数生成器和itertools.count().我先验地知道两者都是无限的并且单调递增.现在我想利用有两个参数的一些操作简单的"OP"(也许operator.add或operator.mul),并计算出每个元素的第一个迭代器与每一个元素的下一个,采用上述操作,则产生逐一时间,排序.显然,这本身就是一个无限的序列.(正如@RyanThompson在评论中所提到的:这将被称为这些序列的笛卡尔积 ...或者更准确地说,是该产品的第1类.)
什么是最好的方式:
允许的简化假设:
也允许:
我能想到这样做的唯一方法是一种"对角化"过程,在这种过程中,我保留了越来越多的部分处理的迭代,并且"向前看"所有可能的next()值的最小值,并产生.但是,即使在我开始对它进行编码之前,这种古怪的聚集和一堆deques似乎都是异乎寻常的.
请:那不是立足于事实,我的例子中提到的质数或计数()你的答案....我对这个非常的概念,不相关的素数和计算多种用途().
更新:天啊!多么棒的讨论!并通过非常彻底的解释得到一些很好的答案.非常感谢.StackOverflow摇滚; 你们好棒.
我将尽快深入研究每个答案,并给出示例代码.从我到目前为止所读到的内容来看,我最初的怀疑是确认没有"简单的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, ...]
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)
| 归档时间： |
|
| 查看次数： |
319 次 |
| 最近记录： |