Как можно оптимизировать вложенные циклы Python?

Question

Как можно оптимизировать вложенные циклы Python?

Квантовая сингулярность Мастер (1914), закрыт 11 месяцев назад

Есть код такого типа:

 def doubles(maxk, maxn): 
    sum = 0 
    for k in range(1, maxk + 1): 
        for n in range(1, maxn + 1): 
            sum += 1 / (k * (n + 1) ** (2 * k)) 
         
    return sum

print(doubles(1, 10))   # 0.5580321939764581 
print(doubles(10, 1000))    # ~ 0.6921486500921933 
print(doubles(10, 10000))   # ~ 0.6930471674194457 
print(doubles(20, 10000))   # ~ 0.6930471955575918

созданный для воспроизведения следующей формулы:

Выходит timed out при высоких значениях maxn, есть идеи как можно это оптимизировать? из модулей доступен только numpy

Answer 1

Самая "тяжёлая" операция здесь - это возведение в степень. Возведение в натуральную степень p питоновский рантайм выполняет за O(log p) умножений, и общая асимптотика выходит O(N × K × log(K)).

Можно изменить порядок итерации: внешний цикл - по n, внутренний - по k. Тогда для каждого n вычисляем q = 1 / (n + 1)², и v(n, k + 1) = v(n, k) × q × k / (k + 1), или можно заодно сэкономить умножение, отделив множитель k:

 def doubles(maxk, maxn):
    sum = 0
    for n in range(1, maxn + 1):
        q = 1 / ((n + 1) * (n + 1))
        t = 1
        for k in range(1, maxk + 1):
            t *= q
            sum += t / k
    return sum

Здесь асимптотика понижается до O(N × K).

Вторая по сложности операция - это деление. Выполняется за экспоненту от количества цифр. Если памяти хватит (т.е. не миллиард итераций), то можно попробовать предварительно рассчитать q(n) и 1/k для всех n, k. Расчёт выполняется один раз, при этом видно замедление до печати первого результата, зато все остальные выдаются мгновенно.

 qs = [1 / ((n + 1) * (n + 1)) for n in range(1, 10001)]
ks = [1 / k for k in range(1, 21)]

def doubles(maxk, maxn):
    sum = 0
    for n in range(1, maxn + 1):
        q = qs[n-1]
        t = 1
        for k in range(1, maxk + 1):
            t *= q
            sum += t * ks[k-1]
    return sum

Здесь асимптотика та же, но значительно (в разы) уменьшается её константный множитель.

Правда, тут стоит отметить, что вторая программа выдаёт расхождение с 14-го знака после точки, а первая считает в точности. Если это критично, то можно посмотреть в сторону типа decimal, правда, это замедлит вычисления и может аннулировать выигрыш от замены деления умножением. Хотя, можно обойтись без decimal, обычным int-ом, просто сдвинув десятичную точку на нужное число порядков.

Ещё можно взять эйлеровское обобщение ряда обратных квадратов для чётных степеней. Но там даётся сразу предел при n → ∞ (он вычисляется за константное время, и общая асимптотика будет O(K), т.к. останется только цикл по k), а для конечных n формулы нет.
https://ru.wikipedia.org/wiki/Ряд_обратных_квадратов

Answer 2

Оптимизация вложенных циклов в Python может выполняться несколькими способами:

1. Использование генераторов списков (list comprehensions) вместо вложенных циклов:

# Пример с вложенными циклами
nested_result = []
for i in range(5):
for j in range(5):
nested_result.append((i, j))

# То же самое с использованием генераторов списков
list_comprehension_result = [(i, j) for i in range(5) for j in range(5)]

2. Использование более эффективных структур данных, таких как словари или множества, для избежания повторяющихся операций во вложенных циклах.

3. Если возможно, можно попробовать переписать алгоритм так, чтобы избежать вложенных циклов (например, использовать словари или множества для хранения и обработки данных).

4. Использование библиотеки NumPy для операций над массивами, которая может значительно ускорить выполнение операций в циклах.

5. Проверка условий и использование операторов continue или break в циклах для пропуска лишних итераций и ускорения выполнения программы.

Однако следует помнить, что оптимизация должна основываться на профилировании кода и измерении его производительности, чтобы убедиться, что внесенные изменения действительно улучшают его быстродействие.

Answer 3

Иногда можно, иногда не очень.
В данном случае я каких-то математических приемчиков для красивой оптимизации не вижу.
Если в той машине, на которой ты это запускаешь, имеется несколько ядер, можно один из циклов распараллелить и запустить в несколько потоков - пусть считают суммы в каком-нибудь массиве. Потом синхронизирующий поток просуммирует массив.

Answer 4

можно и через numpy сделать, получается "быстро", но непосредственно импорт numpy занимает прилично времени и точность чуть теряется (почему-то)

 import numpy as np

def doubles(maxk, maxn):
    sum = 0
    for k in range(1, maxk + 1):
        sum += np.sum(np.divide(1., np.multiply(k, np.power(np.add(np.array(range(1, maxn + 1), dtype=np.float64), 1), k * 2))))
 
    return sum