Более быстрый способ генерации последовательности чисел

Question

Скажите, что я хочу сгенерировать следующую рекурсивную последовательность:

, которая является такой же последовательностью, что и следующая в закрытой форме:

Но цель состоит в том, чтобы написать функцию для генерации последовательности с ее рекурсивным определением. Итак, моя функция заключается в следующем:

def gen_seq(n):
    '''
    n is the number of terms to generate in the sequence
    '''
    lis = [1] # starting number of the sequence
    for i in range(1,n):
        lis.append(lis[-1] + 2*(i+1) - 1)
    return lis

Мы можем взглянуть на первые 10 членов последовательности:

gen_seq(10)
>>> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Если мы посмотрим на время, необходимое для генерации первых 10 миллион чисел в последовательности:

import time
t = time.time()
foo = gen_seq(10000000)
print('Time taken: {}s'.format(time.time()-t))

>>> Time taken: 6.146637201309204s

Это займет 6,1 секунды. Для 100 миллионов номеров потребуется 1 минута. С более сложными последовательностями время будет больше.

Как мне оптимизировать эту функцию, чтобы сделать ее намного быстрее?

Answer 1

Если доступна закрытая форма, вы можете использовать понимание списка. Преимущество этого заключается в том, что вся необходимая память может быть выделена в самом начале:

seq = [(i + 1)**2 for i in range(1, n+1)]

Повторное добавление в список приводит к внутреннему изменению размера основной памяти и, таким образом, включает в себя ненужные выделения памяти и копии.

Без закрытой формы вы все еще можете использовать генератор:

def gen_seq(n):
    a = 0
    for i in range(1, n+1):
        a += 2*i - 1
        yield a

Сравнение производительности

In [1]: def f1(n): 
   ...:     return [(i + 1)**2 for i in range(1, n+1)] 
   ...:                                                                                       

In [2]: def gen_seq(n): 
   ...:     a = 0 
   ...:     for i in range(1, n+1): 
   ...:         a += 2*i - 1 
   ...:         yield a 
   ...:                                                                                       

In [3]: def f2(n): 
   ...:     return list(gen_seq(n)) 
   ...:                                                                                       

In [4]: %timeit f1(100_000)                                                                   
29.7 ms ± 271 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [5]: %timeit f2(100_000)                                                                   
16.1 ms ± 176 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Версия генератора почти в 2 раза быстрее, чем понимание списка. Это потому, что рекурсивная версия выигрывает от относительно простых операций, которые в ней участвуют. Умножение целого числа на 2 - это просто сдвиг на 1, а сложение или вычитание числа - это операция O (N), где N - это число цифр. Однако умножение двух целых чисел равно O (N * log (N)) и, следовательно, требует больше времени для вычисления. Для рекурсивной версии используется уже вычисленная часть a_{n-1}, которую можно использовать на каждом шаге.

Answer 2

В частности, в этом случае вы можете просто использовать list(range(1, n)), что намного быстрее

import time
t = time.time()
print(list(range(1, 1_000_000)))
print(time.time() - t)

Занимает менее 0,5 секунды.

Answer 3

Функция добавления в список заставляет меня поверить, что мы можем сделать это быстрее, давайте попробуем с генераторами:

def seq(n,i=1):
    while i < n+1:
        yield i
        i+=1

import time
t = time.time()
foo = list(seq(10000000))
print('Time taken: {}s'.format(time.time()-t))

Это для меня более чем на одну секунду быстрее. Я думаю, что это может быть улучшено больше.