5

在从元组向量（残差，模数）计算中国剩余定理时，以下代码失败：

c = ((1,5),(3,7),(11,13),(19,23))

def crt(c):
        residues, moduli = zip(*c)
        N = product(moduli)
        complements = (N/ni for ni in moduli)
        scaled_residues = (product(pair) for pair in zip(residues,complements))
        inverses = (modular_inverse(*pair) for pair in zip(complements,moduli))
        si = (product(u) for u in zip(scaled_residues,inverses))
        result = sum(si) % N
        return result

将结果设为0（我猜生成的迭代是空的）。然而，以下代码完美运行：

def crt(c):
        residues, moduli = zip(*c)
        N = product(moduli)
        complements = list((N/ni for ni in moduli)) # <-- listed
        scaled_residues = (product(pair) for pair in zip(residues,complements))
        inverses = (modular_inverse(*pair) for pair in zip(complements,moduli))
        si = (product(u) for u in zip(scaled_residues,inverses))
        result = sum(si) % N
        return result

这会产生（a）8851的正确结果。

为什么我必须list(使用第一批发电机之一？添加list到任何后续生成器不会更改失败 (0) 结果。仅列出第一个生成器会产生正确的结果。这里发生了什么 ？

4

2 回答 2

6

你迭代两次complements。您只能在生成器表达式上迭代一次。

如果你在 Python 2.x 上，zip(residues,complements)将会消耗complements并且没有任何东西可以用于zip(complements,moduli). 在 Python 3.xzip上是一个生成器本身，问题出现在代码的后面，当sum()实际运行生成器时。complements它会从每次迭代中提取两个项目。

于 2013-02-01T06:43:57.170 回答
0

根据答案中的建议作为参考，我重新实现了问题中的代码，如下所示：

def complements(moduli,N):
        return (N/ni for ni in moduli)

def scaled_residues(residues,complements):
        return (product(pair) for pair in zip(residues,complements))

def inverses(complements,moduli):
        return (modular_inverse(*pair) for pair in zip(complements,moduli))

def crt_residue_terms(scaled_residues,inverses):
        return (product(u) for u in zip(scaled_residues,inverses))

 def crt(c):   
    residues, moduli = zip(*c)
    N = product(moduli)
    return sum(
            crt_residue_terms(
                    scaled_residues(residues,complements(moduli,N)),
                    inverses(complements(moduli,N),moduli)
            )) % N

现在它在不使用任何列表的情况下生成正确的8851结果。凉爽的。

于 2013-02-01T07:03:40.540 回答