在 python 中对迭代器进行排序

Question

我想遍历一个大 itertools product，但我想以不同于 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 实际上涉及遍历整个迭代器并返回一个列表。而第二个未排序的迭代器正在执行某种惰性评估魔术。

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

一般问题：是否有惰性计算方法来更改迭代器中出现的顺序项？
具体问题：有没有办法遍历所有 m 长度小于 n 的整数列表，首先命中总和较小的列表？

Answer 1

如果您的 objective 是为了减少内存消耗，您可以编写自己的生成器来 return 按总和排列的排列（见下文）。但是，如果内存不是问题，对 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

这只会产生值的组合，而不是产生这些组合的不同排列的产品。（38,760 种组合对 11,390,625 种产品）。

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

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)将按总和的顺序产生11,390,625个排列，而不将它们存储在列表中但是这样做会花费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 比对产品排序更快）。

在 python 中对迭代器进行排序

Sorting an iterator in python

python

python-3.x

iterator