Как уменьшить время выполнения моей программы?

Question

Программа занимает несколько минут, когда я пытаюсь запустить ее. cycle_length относится к длине цикла Collatz (Collatz conjecture утверждает, что независимо от того, с какого номера вы начинаете, вы всегда достигнете 1, если выполняете данный расчет). max_length вычисляет длину цикла для целых чисел между i и j, чтобы определить, какое число производит самый длинный цикл.

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

The Collatz sequence - это действительно хорошая возможность использовать "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 наполняются предварительно вычисленные результатами, ускоряя будущие вызовы (за счет дискового пространства - классический программирование компромисс):

>>> for x in range(1, 11): 
    print x, collatz_length(x) 


1 1 
2 2 
3 8 
4 3 
5 6 
6 9 
7 17 
8 4 
9 20 
10 7 
>>> collatz_length.cache 
{(34,): 14, (9,): 20, (11,): 15, (13,): 10, (26,): 11, (1,): 1, (28,): 19 
(3,): 8, (5,): 6, (16,): 5, (7,): 17, (20,): 8, (22,): 16, (8,): 4, (10,): 7, 
(14,): 18, (52,): 12, (2,): 2, (40,): 9, (4,): 3, (6,): 9, (17,): 13} 

Это может дать вам результат о 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 секунды.

---

EDIT: Я написал сценарий, чтобы сравнить эффективность трех ответов.

from functools import lru_cache 
import time 

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

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 cycle_length2(n): 
    if n == 1: 
     return 1 
    elif n % 2: 
     return 1 + cycle_length2((3 * n) + 1) 
    return 1 + cycle_length2(n // 2) 

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

def max_length(f, i=1, j=10**6): 
    mxl = f(i) 
    mxn = i 
    while i <= j: 
     y = f(i) 
     if y > mxl: 
      mxl = y 
      mxn = i 
     i += 1 
    return (mxn,mxl) 

for f in [cycle_length1, cycle_length2, cycle_length3]: 
    tic = time.time() 
    print(max_length(f)) 
    print("%s\n" % (time.time() - tic)) 

Результат:

(837799, 525) 
1.5899293422698975 

(837799, 525) 
4.623902320861816 

(837799, 525) 
4.403488874435425 

Кажется, что этот ответ является наиболее эффективным (я думаю, что есть меньше накладные расходы, мы манипулируем простой словарь).

Answer 3

Самый простой способ - запомнить значения cycle_length. Если вы действительно используете Python 3 (3.3+), вы можете просто украсить свою функцию cycle_length с помощью lru_cache(maxsize=None); эта программа имеет время выполнения 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))