提高Python 3.4中大型字典的速度 - python

因此，我正在研究具有1 000 000键的字典，我的任务是使它在3秒内(在Intel 2.4 GHz上)工作。我尝试对我的代码进行性能分析，而while循环有很多成功之处，但是我想不出一种方法来使我的代码在没有它的情况下运行得更快。有没有一种方法可以改善我的代码以使其更快地工作？

该代码应该(并且这样做，但是太慢)创建一个字典，其中的键都是从2到999999的整数，并且值是由序列模式制成的列表的长度。模式是:如果整数是偶数，则将其除以2，如果整数是奇数且大于1，则将其乘以3并加1。这一直持续到达到数字1。

例如:3-> 10-> 5-> 16-> 8-> 4-> 2->1。此列表的长度是8。

码:

import time
start = time.clock()

first = 2
last = 1000000

def function1(n,d):
    if n/2 in d:
        d[n] = d[n/2] + 1
    if n not in d:
        d[n] = 0
        temp = n
        while temp > 1:
            if temp%2 == 0:
                temp /= 2
                d[n] += 1
            else:
                temp = 3*temp + 1
                d[n] += 1
            if temp in d:
                d[n] += d[temp]
                break
    return d[n]

d={}
d[1]=1
d={key: function1(key,d) for key in range(first,last)}

print(time.clock() - start)

python大神给出的解决方案

在我的系统上，您的代码确实耗时超过3秒(在最近的2.3 GHz Intel Core i7 Macbook Pro上使用Python 3.4)。

我可以通过使用局部变量并避免两次构建字典，在3秒内(减少2.65秒，减少12％)获得它:

def function1(n,d):
    if n/2 in d:
        d[n] = d[n/2] + 1
        return
    if n not in d:
        length = 0
        temp = n
        while temp > 1:
            if temp%2 == 0:
                temp //= 2
            else:
                temp = 3*temp + 1
            length += 1
            if temp in d:
                length += d[temp]
                break
        d[n] = length

d={1: 1}
for key in range(first,last):
    function1(key, d)

请注意，我使用的是本地length变量，而不是一直读取d[n]的长度。 Python中的局部变量存储在C数组中，从而避免了对键进行哈希处理和查找(可能包括哈希冲突)的麻烦。

我从/(浮点除法)切换为//(整数除法)；当您感兴趣的只是整数结果时，无需处理小数点。

如果在字典中找到n/2，我也会返回。测试成功后，没有必要进行n not in d的测试，因为我们刚刚添加了d[n]。

字典的理解是完全多余的，function1()已经就地更改了d，因此构建新字典来替换现有结果毫无意义。

下一步是利用刚刚计算的temp值序列。当您从3开始时，您会沿途计算其他几个值。一旦完成，所有这些都可以存储在d中，因此您不必重新计算10，5，16，8和4的顺序:

def function1(n,d):
    if n not in d:
        length = 0
        seen = []
        while n > 1:
            seen.append(n)
            if n % 2 == 0:
                n //= 2
            else:
                n = 3 * n + 1
            length += 1
            if n in d:
                length += d[n]
                break
        for num in seen:
            d[num] = length
            length -= 1

在这里3需要8个步骤，但是我们可以为10存储7个，为5存储6个，依此类推。

我完全放弃了if n/2 in d测试，while循环已经处理了这种情况。由于在n块中不再需要if n not in d，因此我完全放弃了temp并继续使用n。

现在整个测试仅需1.75秒。