在python中对迭代器进行排序

Question

我想迭代一个大的itertoolsproduct，但我想用不同于product提供的顺序。问题是使用sorted对迭代器进行排序需要时间。例如：

from itertools import product
import time
RNG = 15
RPT = 6
start = time.time()
a = sorted(product(range(RNG), repeat=RPT), key=sum)
print("Sorted: " + str(time.time() - start))
print(type(a))
start = time.time()
a = product(range(RNG), repeat=RPT)
print("Unsorted: " + str(time.time() - start))
print(type(a))

创建排序迭代器大约需要两倍的时间。我猜这是因为sorted实际上涉及到遍历整个迭代器并返回一个列表。而第二个未排序的迭代器正在做某种懒惰的求值魔术。

我想这里真的有两个问题。

1. 一般问题：是否有一种懒惰的评估方法来更改迭代器中项目的显示顺序
2. 具体问题：有没有一种方法可以循环遍历所有小于n的int的m长度列表，首先命中具有较小和的列表

Answer 1

如果您的目标是减少内存消耗，您可以编写自己的生成器，按照排列的和的顺序返回排列(见下文(。但是，如果不考虑内存，则对itertools.product()的输出进行排序将比生成相同结果的Python代码更快。

编写一个递归函数，按照值的和的顺序生成值的组合，可以通过基于最小和合并多个迭代器(每个起始值一个(来实现：

def sumCombo(A,N):
if N==1:
yield from ((n,) for n in A) # single item combos
return
pA = []                          # list of iterator/states
for i,n in enumerate(A):         # for each starting value 
ip = sumCombo(A[i:],N-1)     # iterator recursion to N-1
p  = next(ip)                # current N-1 combination
pA.append((n+sum(p),p,n,ip)) # sum, state & iterator
while pA:
# index and states of smallest sum
i,(s,p,n,ip) = min(enumerate(pA),key=lambda ip:ip[1][0])
ps = s
while s == ps:        # output equal sum combinations
yield (n,*p)       # yield starting number with recursed
p = next(ip,None)  # advance iterator
if p is None:
del pA[i]      # remove exhausted iterators
break
s = n+sum(p)       # compute new sum
pA[i] = (s,p,n,ip) # and update states

这只会产生值的组合，而不是产生这些组合的不同排列的乘积。(38760种组合vs 11390625种产品(。

为了获得所有的产品，您需要通过一个生成不同排列的函数来运行这些组合：

def permuteDistinct(A):
if len(A) == 1:
yield tuple(A) # single value
return
seen = set()               # track starting value
for i,n in enumerate(A):   # for each starting value
if n in seen: continue # not yet used
seen.add(n)
for p in permuteDistinct(A[:i]+A[i+1:]): 
yield (n,*p)       # starting value & rest
def sumProd(A,N):     
for p in sumCombo(A,N):           # combinations in order of sum
yield from permuteDistinct(p) # permuted

因此，sumProd(range(RNG),RPT)将按照它们的和的顺序产生11390625个排列，而不将它们存储在列表中，但这样做需要5倍的时间(与对乘积进行排序相比(。

a = sorted(product(range(RNG), repeat=RPT), key=sum) # 4.6 sec
b = list(sumProd(range(RNG),RPT))                    # 23  sec
list(map(sum,a)) == list(map(sum,b)) # True  (same order of sums)
a == b                               # False (order differs for equal sums)
a[5:15]            b[5:15]             sum
(0, 1, 0, 0, 0, 0) (0, 1, 0, 0, 0, 0)  1
(1, 0, 0, 0, 0, 0) (1, 0, 0, 0, 0, 0)  1
(0, 0, 0, 0, 0, 2) (0, 0, 0, 0, 0, 2)  2
(0, 0, 0, 0, 1, 1) (0, 0, 0, 0, 2, 0)  2
(0, 0, 0, 0, 2, 0) (0, 0, 0, 2, 0, 0)  2
(0, 0, 0, 1, 0, 1) (0, 0, 2, 0, 0, 0)  2
(0, 0, 0, 1, 1, 0) (0, 2, 0, 0, 0, 0)  2
(0, 0, 0, 2, 0, 0) (2, 0, 0, 0, 0, 0)  2
(0, 0, 1, 0, 0, 1) (0, 0, 0, 0, 1, 1)  2
(0, 0, 1, 0, 1, 0) (0, 0, 0, 1, 0, 1)  2

如果你的过程是搜索特定的和，那么首先过滤组合，只为符合你的标准的组合(和(展开不同的排列可能会很有趣。这可能会大大减少迭代次数(sumCombo(range(RNG),RPT) # 0.22 sec比对产品进行排序更快(。