python (dict.values())给出了不正确的结果？

Question

亲爱的斯塔克交换机，

在试图计算python字典中的值之和时，我遇到了一个奇怪的结果。如果我的字典超过了一定大小，下面的函数：sum(dict.values())似乎给出了不正确的结果。结果似乎突然变成负值，没有明显的原因。我在Windows 7上使用python2.7(我为我的编码风格事先道歉)。

请注意，我在https://projecteuler.net/problem=72上工作时遇到了这种行为，但我并不是为了得到答案而请求帮助，我只是对内置函数的行为感到困惑。(我也为在一个公共论坛上发布部分解决方案而道歉，如果你不想要任何提示，请现在注意)。

该程序的目标在项目Euler链接(上面)中得到了解释，但我将尝试简要解释我的代码：

第一个函数使用一个Erasthenes筛子来生成素数列表，并使用一个修改的筛子在指定的范围内生成一个{composite_number:[prime_factor_list]}字典。

第二个函数尝试计算形式n/d中可以生成的分数数，其中n

最初，我使用了一个简单的计数器(将计数初始化为0，然后根据需要进行增量)，但决定使用字典代替。令我惊讶的是，这两种方法给出了不同的结果，但只有当上限(d)超过一定的大小时。我更深入地探索，并设法分离出计数分歧的确切时刻。底部附近的if 88000 < i < 88055:行标识dict值和开始与简单计数不同的点。对于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())

我想我做了一些非常愚蠢的事情，但我觉得必须把它放在那里，以防真的有什么不对劲。

致以敬意，

Answer 1

您遇到了整数溢出问题，在Python中不应该发生这种情况。你有一台32位的机器，所以最大的正常整数是(2^31 - 1).一旦计算结果超过该值，Python应该自动切换到使用long来进行计算，而long在其所支持的数字大小上是不受限制的。我只有64位机器，但除了最大整数为(2^63 - 1)外，同样的情况也适用。当你有一个长的时候，你可以从外壳中分辨出来，因为L是在数字后面打印的。下面是我的shell中的一个示例：

>>> 2**62 - 1 + 2**62  # This is max int
9223372036854775807
>>> 2**63  # This is a long
9223372036854775808L
>>> num = 2**62 - 1 + 2**62
>>> num
9223372036854775807
>>> num+1
9223372036854775808L
>>> d = {1:2**62,2:-1,3:2**62}
>>> sum(d.values())
9223372036854775807
>>> d = {1:2**62,2:-1,3:2**62,4:1}
>>> sum(d.values())
9223372036854775808L

在我的例子中，在64位计算机上的Linux上使用Python2.7，这一切都如预期的那样工作。

现在，我使用Spyder运行了相同的操作，得到了错误的答案：

>>> d = {1:2**62,2:-1,3:2**62,4:1}
>>> sum(d.values())
-9223372036854775808

当我只做正常的加法时，它是正确的，但是字典中的这个和给出了错误的答案。这并不是字典所特有的，只是求和函数。清单也是一样的：

>>> list = [2**62, -1, 2**62, 1]
>>> sum(list)
-9223372036854775808

因此，这个问题被隔离到Spyder中的sum()函数中，并且发生在32位和64位机器上。

真正的答案是Spyder自动导入numpy。Numpy有它自己的求和函数。描述如下：“当使用整数类型时，算法是模块化的，溢出不会引起错误。”您正在使用sum的那个版本，它导致了问题。如果您不想使用该总和，可以将以下内容放在文件的顶部：

from __builtin__ import sum

这将导致内置版本的sum被使用，您将得到正确的答案。

要想弄清楚这笔钱不是从哪里来的，我可以用以下方法：

>>> import inspect
>>> inspect.getmodule(sum)
<module 'numpy.core.fromnumeric' from '/usr/lib/python2.7/dist-packages/nump/core/fromnumeric.pyc'>