Как сложить много дробей как можно быстрее? ⇐ Python

[Anonymous]

Это связано с этим вопросом.
По сути, мне нужно сложить множество дробей. Кажется достаточно простым? Вот только это не просто.
Я не могу использовать класс Fractions.Fraction, эта штука тупо уменьшает дроби на каждом шагу и имеет все накладные расходы на объекты Python, поэтому крайне неэффективно.
Как правильно складывать дроби? Используйте формулу a/b + c/d = (a * d + b * c)/(b * d), мы можем просто разделить числитель и знаменатель и сохранить их как пару целых чисел и никогда не выполнять деление, а затем просто объединить их с помощью формулы. Сделанный. Сделанный? Нет, это никогда не бывает так просто.

Код: Выделить всё

In [3]: from fractions import Fraction

In [4]: Fraction(500, 1000)
Out[4]: Fraction(1, 2)

In [5]: %timeit Fraction(1, 2) + Fraction(3, 5)
2.24 μs ± 128 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [6]: a, b, c, d = 1, 2, 3, 5

In [7]: %timeit a * d + b * c, b * d
98.3 ns ± 0.401 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Как видите, Fractions.Fraction примерно в 22 раза медленнее, чем простое перекрестное умножение.
Но, как видите, у метода перекрестного умножения тоже есть проблемы: ему приходится выполнять три умножения и одно сложение при каждом отдельном вызове. Это означает, что числитель и знаменатель всегда будут увеличиваться. А int в Python имеет произвольную точность (не бесконечную точность, поскольку максимальное количество цифр ограничено ssize_t), поэтому я использую дроби вместо числа с плавающей запятой, потому что IEEE-754 double имеет жалкие 53 бита мантиссы, таким образом, 53 * log10(2) = 15.954589770191003 точных десятичных цифр.
И как числа становятся больше, стоимость сложения и умножения также увеличивается, они оба масштабируются в зависимости от количества цифр. Это означает, что чем больше дробей я складываю, тем больше будут числа и тем дороже станут вычисления.
Поэтому нам нужно уменьшать дроби, чтобы они не становились слишком большими. Как сократить дроби? Все просто, вычисляем наибольший общий знаменатель числителя и знаменателя и делаем целочисленное деление на НОД как в числителе, так и в знаменателе.
Проблема решена? Нет, НОД работает медленно и масштабируется в зависимости от количества цифр. И вместо трех умножений и одного сложения на каждой итерации нам придется выполнить три умножения и одно сложение, один НОД и два деления по этажам. Таким образом, этот метод только сделает код еще медленнее.
Как показывает мой тест:

Код: Выделить всё

import dill
from concurrent.futures import ThreadPoolExecutor
from itertools import batched
from math import gcd
from pathos.multiprocessing import ProcessPool

def arctan_derivative(x: int, y: int) -> tuple[int, int]:
return y * y, x * x + y * y

def primitive_rationals_simple(denominator: int) -> list[tuple[int, int]]:
assert isinstance(denominator, int) and denominator > 0
mid = (den_plus := denominator + 1) >> 1
result = [(1, 2)] * den_plus
result[0] = (0, 1)
result[-1] = (1, 1)

for i in range(1, mid):
result[i] = (
(n := i // (common := gcd(i, denominator))),
(d := denominator // common),
)
result[denominator - i] = (d - n, d)

return result

def make_test_case(n: int) -> list[tuple[int, int]]:
return [arctan_derivative(*frac) for frac in primitive_rationals_simple(n)]

def test1(fracs: list[tuple[int, int]]) -> tuple[int, int]:
num, den = 0, 1
for tnum, tden in fracs:
num, den = num * tden + tnum * den, den * tden

return num, den

def test2(fracs: list[tuple[int, int]]) -> tuple[int, int]:
num, den = 0, 1
for tnum, tden in fracs:
num, den = num * tden + tnum * den, den * tden
num //= (common := gcd(num, den))
den //= common

return num, den

Код: Выделить всё

In [38]: data = make_test_case(360)

In [39]: %timeit test1(data)
268 μs ± 7.24 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [40]: %timeit test2(data)
9.72 ms ± 131 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Как видите, уменьшение дробей на каждом шагу делает код в 36 раз медленнее.
Но что, если мы сможем одновременно уменьшить дроби и не слишком сильно замедлять выполнение? А что если сократить дроби и сложить их одновременно параллельно? Мы можем получить лучшее из обоих миров. Как вы, наверное, догадались из моего импорта, мы должны складывать дроби параллельно.
Теперь рассмотрим функцию сложения дробей, она принимает две дроби и дает одну дробь. Кажется достаточно простым, не так ли? Теперь для двух пар дробей нам нужны два вызова, очевидно, что вывод каждого вызова независим друг от друга. Рассмотрим четыре пары дробей, выход каждого вызова независим. Таким образом, их можно делать параллельно.
Хорошо, даны четыре пары дробей, обозначьте их (a, b), (c, d), (e, f), (g, h), как нам сложить их все вместе?
Все просто, мы складываем пары, тогда у нас есть четыре дроби: (a+b, c+d, e+f, g+h). После этого у нас есть две пары, поэтому мы складываем пары вместе: (a+b+c+d, e+f+g+h). И посмотрите, теперь у нас есть одна пара, поэтому мы складываем их вместе, готово.
Таким образом, для n дробей у нас есть n//2 пар, причем одна непарная дробь, если n нечетное, все эти пары можно складывать параллельно. Это означает, что мы также можем выполнять НОД параллельно. И тогда у нас есть n//2 дроби с условной дробью переноса, мы можем итеративно и рекурсивно использовать результат текущей итерации в качестве входных данных следующей итерации, пока в стеке не останется только одна дробь.
Вот алгоритм:

Код: Выделить всё

def add_fractions(fracs: tuple[tuple[int, int], tuple[int, int]]) -> tuple[int, int]:
(num_1, den_1), (num_2, den_2) = fracs
num, den = num_1 * den_2 + num_2 * den_1, den_1 * den_2
num //= (common := gcd(num, den))
den //= common
return num, den

def test3(fracs: list[tuple[int, int]]) -> tuple[int, int]:
with ProcessPool() as pool:
while (length := len(fracs)) > 1:
carry = fracs.pop(-1) if length & 1 else None
fracs = pool.map(add_fractions, batched(fracs, 2))
if carry:
fracs.append(carry)

return fracs[0]

Я не знаю, насколько это быстро, потому что это не работает.

Код: Выделить всё

In [41]: %timeit test3(data)
---------------------------------------------------------------------------
RemoteTraceback                           Traceback (most recent call last)
RemoteTraceback:
"""
Traceback (most recent call last):
File "C:\Program Files\Python312\Lib\site-packages\multiprocess\pool.py", line 125, in worker
result = (True, func(*args, **kwds))
^^^^^^^^^^^^^^^^^^^
File "C:\Program Files\Python312\Lib\site-packages\multiprocess\pool.py", line 48, in mapstar
return list(map(*args))
^^^^^^^^^^^^^^^^
File "C:\Program Files\Python312\Lib\site-packages\pathos\helpers\mp_helper.py", line 15, in 
func = lambda args: f(*args)
^^^^^^^^
File "", line 53, in add_fractions
NameError: name 'gcd' is not defined
"""

И я знаю, что существует множество способов параллельного выполнения кода: concurrent.futures.ThreadPoolExecutor, concurrent.futures.ProcessPoolExecutor, threading.Threads, asyncio, subprocess... Я понятия не имею, какой использовать.
Как правильно распараллелить сложение дробей и сделать его максимально быстрым возможно?

Подробнее здесь: https://stackoverflow.com/questions/798 ... s-possible