Я работаю над небольшой программой на Python для себя, и мне нужен алгоритм быстрого умножения огромного массива чисел (более 660 000 чисел, каждое из которых состоит из 9 цифр). Число результата превышает 4 миллиона цифр. В настоящее время я использую math.prod, который вычисляет его примерно за 10 минут, но это слишком медленно, особенно если я хочу увеличить количество чисел.
Я проверил некоторые алгоритмы для более быстрого умножения, например алгоритм Шенхаге-Штрассена и умножение Тума-Кука, но я не понимал, как они работают и как их делать. Я попробовал несколько версий, которые нашел в Интернете, но они работают не очень хорошо и даже медленнее. Интересно, знает ли кто-нибудь, как быстрее умножать эти числа, или может объяснить, как для этого использовать некоторые математические методы?
Вы можете потратить дни на написание чего-нибудь сносного или просто воспользоваться одной из многих эффективных математических и научных библиотек, над которыми годами работала команда инженеров, ученых и программистов.
Я не думаю, что есть, все числа в массиве являются степенями простых чисел. Эта программа вычисляет LCM для диапазона от 1 до N, числа выше указаны для N = 10 000 000. Таким образом, это 4-миллионное число является наименьшим числом, которое делится на любое число в диапазоне от 1 до 10 миллионов.
@Серджио, а как насчет контекста, в котором используется это число, можешь ли ты избежать его вычисления, возможно, работая с ним неявно? (вы знаете его факторы, это хорошее начало неявной работы с ним)
Другими словами, что вы собираетесь делать с этим числом? Наверняка вы не собираетесь это распечатывать и читать. И, возможно, вашей реальной цели можно достичь, не вычисляя это число.
Кроме того, НОК от 1 до 10 000 000 является произведением высших степеней простых чисел в этом диапазоне для каждого простого числа в этом диапазоне — вы имели в виду 664579 семизначных чисел?
@Ry- да, я виноват, числа здесь семизначные.
Не комментируйте комментарии, требующие разъяснений или дополнительной информации: отредактируйте свое сообщение.
math.prod
будет накапливать товар по одному номеру. Вы можете добиться большего, рекурсивно разделив список, взяв, например, произведение каждой половины, что уменьшит размер промежуточных продуктов.
У меня это происходит за несколько секунд:
import math
def recursive_prod(ns, r):
if len(r) <= 10: # arbitrary small base case
return math.prod(ns[i] for i in r)
split_at = len(r) // 2
return recursive_prod(ns, r[:split_at]) * recursive_prod(ns, r[split_at:])
import random
ns = [random.randrange(1_000_000_000) for _ in range(660_000)]
p = recursive_prod(ns, range(len(ns)))
Я бы избегал рекурсии, если скорость является приоритетом
Спасибо, у меня все умножается за 15 секунд!
Было бы лучше объяснить, «почему» это быстрее.
@juanpa.arrivillaga Как вы думаете, насколько быстрее будет нерекурсивное решение?
Я бы сказал, что «уменьшает размер промежуточных продуктов» - это скорее противоположность тому, почему это быстрее. Вам нужны большие операнды, чтобы можно было использовать лучший алгоритм умножения. А конкатенация строк кажется совершенно вводящей в заблуждение, поскольку конкатенация не использует разные алгоритмы и является линейной. Если вы думаете об основной теореме, ваше рекурсивное умножение подпадает под случай 3, а ваша рекурсивная конкатенация подпадает под случай 1. Случай 1 является причиной того, что оно быстрее, а не потому, что используется другой алгоритм. Это другая причина.
@nocomment: их довольно сложно отделить друг от друга, поскольку нет смысла использовать более быстрый алгоритм умножения на небольших входных данных, но я бы сказал, что меньший размер промежуточных элементов является ключевым, если что-то и есть. И да, конкатенация строк должна быть нижней границей улучшения, поскольку умножение хуже линейного.
@nocomment: Если подумать, то на самом деле это просто другой способ сказать одно и то же, подчеркивая максимальный и минимальный размер на каждом уровне в задаче, где меньший максимум подразумевает больший минимум, и наоборот.
Разве вы не имеете в виду верхнюю границу улучшения? Потому что он действительно выигрывает от самого принципа «разделяй и властвуй», улучшаясь с O(n^2) до O(n log n). Принимая во внимание, что продукт улучшается только с O(n^2) до O(n^1,58), что является гораздо меньшим улучшением и происходит не из-за принципа «разделяй и властвуй», а из-за вмешательства Карацубы.
@nocomment: я имею в виду нижнюю границу, если вы считаете, что произведение имеет одинаковую асимптотическую сложность O (n ^ 1,58) в обоих случаях. Стоимость одного продукта не увеличивается с O(n^2) до O(n^1,58) при переходе на рекурсивный подход – она ухудшается с O(n) (поскольку один операнд имеет постоянную верхнюю границу)… что может быть, это означает, что моя аналогия неверна (но по противоположной причине?). Вернусь, когда у меня будет возможность.
Стоимость одного продукта увеличивается до O(n^1,58) при переключении на рекурсивный подход. Потому что рекурсивный подход делает операнды сбалансированными и запускает Карацубу, когда они становятся достаточно большими. Хотя я говорил не об одном продукте, а о целом. Позвольте мне сказать иначе: если бы Python не переключился на Карацубу, а продолжал использовать наивный алгоритм, то ваше рекурсивное решение имело бы ту же сложность, что и math.prod
, и, вероятно, было бы таким же медленным.
Я использовал хитрый метод, всегда умножая два самых старых, еще не умноженных числа, пока не останется только одно:
from operator import mul
def prod(ns):
ns = list(ns)
it = iter(ns)
ns += map(mul, it, it)
return ns[-1]
Примерно так же быстро, как @Ry-. Скорость достигается благодаря тому, что Карацуба умножает два больших числа вместо одного большого и одного крошечного.
А использование decimal
кажется примерно в пять раз быстрее из-за еще более быстрых алгоритмов умножения (и имеет то преимущество, что печать в десятичном формате гораздо быстрее, если вы этого хотите):
from operator import mul
from decimal import *
setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX))
def prod(ns):
ns = list(map(Decimal, ns))
it = iter(ns)
ns += map(mul, it, it)
return ns[-1]
Есть два ключа к тому, чтобы сделать это быстро. Во-первых, используя самую быструю реализацию multi, какую только можно получить. Для «достаточно больших» множимых множитель Карацубы в Python равен O(n^1.585)
. Гораздо более интересный NTT-мульт модуля decimal
больше похож на O(n log n)
. Но быстрее всего установить пакет расширения gmpy2
, который включает в себя библиотеку GMP GNU, главная цель которой — максимальная скорость. По сути, это имеет ту же асимптотику, что и decimal
mult, но с меньшим постоянным коэффициентом.
Во-вторых, усовершенствованные алгоритмы multi работают лучше всего при умножении двух больших целых чисел примерно одинакового размера (количества битов). Вы можете оставить это на волю случая или, как показано ниже, заставить это сделать, используя очередь с приоритетами и на каждом шаге умножая оставшиеся «два наименьших» частичных продукта.
from gmpy2 import mpz
from heapq import heapreplace, heappop, heapify
# Assuming your input ints are in `xs`.
mpzs = list(map(mpz, xs))
heapify(mpzs)
for _ in range(len(mpzs) - 1):
heapreplace(mpzs, heappop(mpzs) * mpzs[0])
assert len(mpzs) == 1
# the result is mpzs[0]
Это код, который я бы использовал. Обратите внимание, что стоимость рекурсии (которая здесь не используется) тривиальна по сравнению со стоимостью арифметики с огромными целыми числами. Операции с кучей более дороги, чем рекурсия, но все же относительно дешевы и могут более чем окупить свои затраты, если входные данные расположены в таком порядке, что методам «по счастливой случайности» не хватает удачи.
Можете ли вы дать представление о том, насколько это быстро, особенно по сравнению с текущим принятым ответом?
Используя их способ построения тестовых данных (и это нормально — скажем так, чтобы было понятно), этот код выполняется менее чем за треть времени, и независимо от того, включено ли время на преобразование из int в mpz (это дешево ). И, кстати, они вычисляют тот же результат :-)
Означает ли это, что он медленнее моего decimal
? Так как это заняло пятую часть времени.
На моем компьютере время в секундах составляет 10,1 (исходное), 3,3 (десятичное) и 2,1 (мое). Если вместо 9 используются 18 цифр, то 32,0 (исходное), 7,1 (десятичное) и 3,4 (мое). Для небольших входных данных мой работает намного медленнее (тогда доминируют операции с кучей). Не на тихой машине.
Спасибо. А раньше у вас было другое время? Я бы не назвал 2.1 «менее трети» от 10,1.
Не позволю мне редактировать последний комментарий: время для моего должно быть 2,9 вместо 2,1 для 9-значного числа.
Поместите их в ответ, а затем сможете редактировать по своему усмотрению :-) (И в любом случае им лучше быть там.)
Нет, я закончил. Скорость всех методов здесь будет зависеть от платформы. Записывать только один мне не так интересно. В любом случае, это не имеет отношения к пунктам высокого уровня, самый важный из которых: если вас очень заботит гигантская скорость int, используйте gmpy2
.
Я бы назвал другое более важным. Использование gmpy2 мало поможет с несбалансированными операндами (как в вопросе /math.prod).
Если вас волнует худший случай, конечно. Я делаю. Но я ожидаю, что большая часть входных данных в большинстве случаев не будет располагаться в патологическом порядке. Для конкретных тестовых данных использование кучи в большинстве случаев является ненужным накладным расходом. И нет, я больше не провожу тестов: я закончил :-) Нисколько не спорю, что «по одному слева направо» — это ужасно. Совсем не об этом. Рассказываем о трёх небезумных методах, представленных на столе.
Ваша куча может быть более накладной, чем необходимо, но им нужно что-то сделать, чтобы сбалансировать операнды. Я имею в виду, что если они используют gmpy2 с math.prod, это все равно будет медленным, тогда как рекурсия, или мой путь, или ваша куча с int
s Python, будет быстрой. Поэтому я считаю использование gmpy2 (намного) менее важным моментом, а использование лучшего алгоритма высокого уровня — более важным.
«Говорим о трех небезумных методах в таблице» — Ага, это изменение появилось только после того, как я опубликовал свой комментарий выше.
Это нормально: мое «если вас очень волнует скорость гигантских целых чисел, используйте gmpy2
» в любом случае на самом деле не относилось к этому посту: независимо от того, что вы делаете с гигантскими целыми числами, «использование gmpy2
» будет частью лучший ответ, который вы когда-либо найдете.
Это работает даже лучше, чем то, что я принял сначала. @nocomment для меня примерно такая же скорость, как и твой десятичный способ.
Спустя несколько тестов decimal
вычислил результат для 5,7 млн 8-значных цифр за ~63 секунды, gmpy2
за ~59 секунд. Наверное, у них примерно одинаковая скорость.
Чем крупнее продукты, тем лучше подойдет gmpy2. Под покровом происходят чрезвычайно сложные вещи. gmpy2
на самом деле реализует множество различных алгоритмов мультирования и меняет те из них, которые он использует, в зависимости от точных размеров битов, которые могут даже варьироваться в зависимости от того, на каком оборудовании он работает, decimal
реализует только 3 алгоритма мультирования и выбирает размеры обрезки независимо от оборудования. Дон Я также не ожидаю воспроизвести одни и те же различия на разных платформах.
@Sergio Still: Что вы собираетесь делать с этим огромным числом, которое теперь даже превышает 40 миллионов цифр?
В любом случае в Python встроены эти причудливые алгоритмы, но они действительно срабатывают только при умножении двух больших чисел, а не тогда, когда одно большое, а другое нет. Кстати, какие вещи здесь на самом деле выполняются, возможно, есть какой-то ярлык или альтернатива?