python dict.values() 的 sum() 结果不正确？

Question

亲爱的Stack交流者们，

我在用Python计算字典中数值的总和时遇到了奇怪的结果。如果我的字典超过了某个大小，使用这个函数：sum(dict.values())似乎会给出错误的结果。结果突然变成负数，完全没有理由。我是在Windows 7上使用Python 2.7。（提前为我的编码风格道歉）。

请注意，我在处理https://projecteuler.net/problem=72时遇到了这种情况，但我并不是在寻求答案的帮助，只是对这个内置函数的表现感到困惑。（我也为在公共论坛上发布部分解决方案而道歉，如果你不想看到任何提示，请现在就移开视线）。

程序的目标在上面的项目Euler链接中有解释，但我会尝试简要说明我的代码：

第一个函数使用埃拉托斯特尼筛法生成素数列表，并使用修改过的筛法在指定范围内生成一个字典，格式为{合成数:[素因子列表]}。

第二个函数试图计算可以生成的形如n/d的分数的数量，其中n < d且d <= 1000000。问题说明我只应该计算约简的真分数，所以这个函数的大部分内容都在处理可约分数。我采用的策略是循环遍历每个分子，从1到d-1，并丢弃不合适的分母。对于素数来说，这很简单，而对于非素数，我接近一个可行的解决方案，但仍然会多次丢弃一些值。对于这篇帖子，重要的细节是我统计计数的方式：

最开始我使用了一个简单的计数器（将计数初始化为0，然后根据需要增加），但后来决定尝试使用字典。令我惊讶的是，这两种方法给出的结果不同，但只有当上限（d）超过某个大小时。我深入探究，成功找到了计数结果分歧的确切时刻。代码行if 88000 < i < 88055:在底部标识了字典值的总和开始与简单计数不同的点。对于i = 88032之前的值，结果是相同的，但当i = 88033时，结果却大相径庭：

from collections import defaultdict

def primeset(limit):
    pr = [0]*(limit+1)
    for i in range(2,limit+1):
        j = i
        i += j
        while i <= limit:
            pr[i] = 1
            i += j
    primes = [k for k in range(2,limit+1) if pr[k] == 0]
    composites = defaultdict(list)
    for p in primes:
        q = p
        p += q
        while p <= limit:
            composites[p].append(q)
            p += q
    return primes, composites


def method2(limit):
    primes, composites = primeset(limit)
    prf = {}
    count = 0
    count += limit-1
    count += (limit-2)/2
    prf[1] = limit-1
    prf[2] = (limit-2)/2    
    for i in primes:
        if i != 2:
            tally = limit-i-(limit/i)+1
            count += tally
            prf[i] = tally
    for i in composites:
        tally = limit-i
        for item in composites[i]:
            tally -= (limit/item-i/item)
        count += tally
        prf[i] = tally
        if 88000 < i < 88055:
            print i, count, tally, sum(prf.values())
    return count, prf

result, index = method2(88547)

print result,sum(index.values())

我想我可能做了什么愚蠢的事情，但我觉得有必要把这个问题提出来，以防真的有什么不对劲。

祝好，

编码风格字典数值计算错误调试计数器埃拉托斯特尼筛法项目Euler 约简真分数

python dict.values() 的 sum() 结果不正确？

1 个回答

撰写回答