如何减少程序的运行时间？

Question

每次我试着运行这个程序都要花几分钟时间。cycle_length是指Collatz循环长度（Collatz conjecture声称，无论你从哪个数字开始，如果你进行给定的计算，你最终总会达到1）。max_length计算i和{}之间的整数的循环长度，以确定哪个数产生最长的循环。在

def cycle_length(n):
    if n == 1:
        return n    
    elif n % 2 == 0:
        return cycle_length(n//2) + 1
    else:
        return cycle_length(3*n + 1) + 1

def max_length(i,j):
    mxl = cycle_length(i)
    mxn = i
    while i <= j:
        start = time.time()
        y = cycle_length(i)
        if y > mxl:
            mxl = y
            mxn = i
        i += 1
    return (mxn,mxl)

print(max_length(1, 10**6)) 

我想将程序从1迭代到10**6。有没有什么有效的方法可以让程序更快（10秒以下）？在

Answer 1

Collatz序列是使用"dynamic programming" techniques的好机会。来自给定数字n的序列的长度将始终相同，因此您可以存储该结果，并在将来的某个序列中再次到达n时使用它。例如，使用修饰符来"memoize"结果：

def memo(func):
    def wrapper(*args):
        if args not in wrapper.cache:
            wrapper.cache[args] = func(*args)
        return wrapper.cache[args]
    wrapper.cache = {}
    return wrapper

@memo
def collatz_length(n):
    if n == 1:
        return 1
    elif n % 2:
        return 1 + collatz_length((3 * n) + 1)
    return 1 + collatz_length(n // 2)

现在，如果我们运行程序的初始值为n，您可以看到cache被预先计算的结果填充，从而加快了将来的调用（以牺牲存储空间为代价—这是一种典型的编程权衡）：

^{pr2}$

这可以在大约1.5s内得出结果：

>>> from timeit import timeit
>>> timeit('max(collatz_length(x+1) for x in range(10**6))',
           setup='from __main__ import collatz_length',
           number=1)
1.5072860717773438

Answer 2

你做了很多相同的计算。为了避免这种情况，我们可以存储以下值：

cache = {1 : 1}

def cycle_length(n):
    if n in cache.keys():
        return cache[n]
    elif n % 2 == 0:
        x = cycle_length(n//2) + 1
    else:
        x = cycle_length(3*n + 1) + 1
    cache[n] = x
    return x

def max_length(i,j):
    mxl = cycle_length(i)
    mxn = i
    while i <= j:
        y = cycle_length(i)
        if y > mxl:
            mxl = y
            mxn = i
        i += 1
    return (mxn,mxl)

print(max_length(1, 10**6))

在我的机器上，你的代码运行了29.9秒。我的代码给出了相同的结果，并在1.8秒内运行。在

---

编辑：我写了一个脚本来比较3个答案的效率。在

^{pr2}$

结果：

(837799, 525)
1.5899293422698975

(837799, 525)
4.623902320861816

(837799, 525)
4.403488874435425

我认为这是一个比较简单的答案（我认为这是一个比较简单的答案）。在

Answer 3

最简单的方法是记住cycle_length的值。如果您确实在使用Python3（3.3+），您可以用lru_cache(maxsize=None)来装饰函数cycle_length；这个程序在我的笔记本电脑上运行时间为5秒：

from functools import lru_cache

@lru_cache(maxsize=None)
def cycle_length(n):
    if n == 1:
        return n    
    elif n % 2 == 0:
        return cycle_length(n//2) + 1
    else:
        return cycle_length(3*n + 1) + 1

def max_length(i,j):
    mxl = cycle_length(i)
    mxn = i
    while i <= j:
        start = time.time()
        y = cycle_length(i)
        if y > mxl:
            mxl = y
            mxn = i
        i += 1
    return (mxn,mxl)

print(max_length(1, 10**6))