Python 3.4 中提高大字典的速度

Question

所以我正在编写具有 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)

Answer 1

这里是Collatz conjecture。你可以查看一些关于互联网的信息，一些关于它的C或C++代码，也许Python。我想你会发现一些以前人们制作的有用的功能。

Also you can use numpy module and you can make some formulas with it, I think it will be faster with this.Numpy is a module that you can make mathematical operations easily.

Answer 2

在我的系统上，您的代码确实需要 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 数组中，避免了对密钥进行散列和查找（可能包括散列冲突）。

我从/（浮点除法）切换到//（整数除法）；当您只对整数结果感兴趣时，无需处理小数点。

我也return如果n/2在字典里找到。在测试成功后测试 n not in d 没有意义，因为我们刚刚添加了 d[n]。

词典理解完全是多余的，function1() 已经就地更改了 d，因此没有必要构建新词典来替换现有结果。

下一步是利用您刚刚计算的 temp 值序列。当您从 3 开始时，您会在此过程中计算其他几个值；一旦完成，所有这些都可以存储在 d 中，因此您不必重新计算 10、5、16、[=27= 的序列] 和 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 循环已经解决了这种情况。由于 if n not in d 块中不再需要 n，因此我完全放弃了 temp 并继续使用 n。

现在整个测试只需要1.75秒。

Answer 3

我相信这是一个有用的优化（我的 MB Air w/a Core i5 在 1.3 GHz 上运行 2.4 秒，3 次运行中最好的 w/Python 2.7.3；3.4.1，2.7 秒）是为了避免 "wasting" temp 的各种计算——保留它们可以让您非常直接地计算它们的 d 值。这是我的版本...:[=13=]

import time
start = time.clock()

first = 2
last = 1000000

def function1(n, d):
    if n%2 == 0 and n//2 in d:
        d[n] = d[n//2] + 1
    if n not in d:
        temp = n
        intermediates = []
        while temp > 1:
            if temp%2 == 0:
                temp //= 2
            else:
                temp = 3 * temp + 1
            if temp in d:
                d[n] = res = d[temp] + len(intermediates) + 1
                for i, temp in enumerate(intermediates, 1):
                    d[temp] = res - i
                return res
            else:
                intermediates.append(temp)
    return d[n]

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

print(time.clock() - start)

Python 3.4 中提高大字典的速度

Improving speed of large dictionary in Python 3.4

python

performance

dictionary