Как я могу преобразовать абсолютно массивное число в строку за разумное время?

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

prime = 2**74207281 - 1 

Это занимает около полутора секунд, и все работает отлично. Операции довольно быстрые. Деление его на 10 (без десятичных знаков) для смещения цифр происходит быстро. Однако str(prime) занимает очень много времени. Я повторил эту страницу так, и нашел, что она обрабатывает около ста цифр в секунду.

 while prime > 0: strprime += str(prime%10) prime //= 10 

Есть ли способ сделать это более эффективно? Я делаю это на Python. Должен ли я даже попробовать это с Python, или есть лучший инструмент для этого?

4 Solutions collect form web for “Как я могу преобразовать абсолютно массивное число в строку за разумное время?”

Повторная конкатенация строк, как известно, неэффективна, поскольку строки Python неизменяемы. Я бы пошел

 strprime = str(prime) 

В моих тестах это всегда самое быстрое решение. Вот моя маленькая тестовая программа:

 import decimal def f1(x): ''' Definition by OP ''' strprime = "" while x > 0: strprime += str(x%10) x //= 10 return strprime def digits(x): while x > 0: yield x % 10 x //= 10 def f2(x): ''' Using string.join() to avoid repeated string concatenation ''' return "".join((chr(48 + d) for d in digits(x))) def f3(x): ''' Plain str() ''' return str(x) def f4(x): ''' Using Decimal class''' return decimal.Decimal(x).to_eng_string() x = 2**100 if __name__ == '__main__': import timeit for i in range(1,5): funcName = "f" + str(i) print(funcName+ ": " + str(timeit.timeit(funcName + "(x)", setup="from __main__ import " + funcName + ", x"))) 

Для меня это печатает (используя Python 2.7.10):

 f1: 15.3430171013 f2: 20.8928260803 f3: 0.310356140137 f4: 2.80087995529 

Целочисленный алгоритм Python для строкового преобразования использует упрощенный алгоритм с управлением O (n ** 2). Поскольку длина числа удваивается, время преобразования увеличивается в четыре раза.

Некоторые простые тесты на моем компьютере показывают увеличение времени работы:

 $ time py35 -c "n=str(2**1000000)" user 0m1.808s $ time py35 -c "n=str(2**2000000)" user 0m7.128s $ time py35 -c "n=str(2**4000000)" user 0m28.444s $ time py35 -c "n=str(2**8000000)" user 1m54.164s 

Так как фактический показатель примерно в 10 раз больше моего последнего тестового значения, он должен занимать около 100 раз дольше. Или чуть более 3 часов.

Можно ли это сделать быстрее? Да. Существует несколько способов, которые быстрее.

Способ 1

Быстрее разделить очень большое число на 10 единиц на два примерно равных, но меньших числах. Процесс повторяется до тех пор, пока номера не будут относительно небольшими. Затем на каждом номере используется str() а начальные нули используются для заполнения результата до той же длины, что и последняя мощность -10. Затем строки объединяются для формирования конечного результата. Этот метод используется библиотекой mpmath и документация подразумевает, что она должна быть примерно в 3 раза быстрее.

Способ 2

Целочисленные числа Python хранятся в двоичном формате. Двоичный файл отлично подходит для вычислений, но двоично-десятичное преобразование является узким местом. Можно определить свой собственный целочисленный тип, который хранит значение в блоках из десятичных цифр (или некоторых аналогичных значений) из 100 знаков. Операции (возведение в степень, умножение, деление) будут медленнее, но преобразование в строку будет очень быстрым.

Много лет назад я реализовал такой класс и использовал эффективные алгоритмы для умножения и деления. Код больше не доступен в Интернете, но я нашел резервную копию, которую я тестировал. Время работы сократилось до ~ 14 секунд.

Обновить

Я обновил код DecInt, упомянутый выше, и теперь он доступен по адресу https://github.com/casevh/DecInt .

Если используется собственный целочисленный тип Python, общее время работы на моем компьютере составляет менее 14 секунд. Если вместо этого используется целочисленный тип gmpy2 , время работы ~ 3,5 секунды.

 $ py35 DecInt.py Calculating 2^74207281 Exponentiation time: 3.236 Conversion to decimal format: 0.304 Total elapsed time: 3.540 Length of result: 22338618 digits 

Способ 3

Я поддерживаю библиотеку gmpy2, которая обеспечивает легкий доступ к библиотеке GMP для быстрой целочисленной арифметики. GMP реализует метод 1 в высоко оптимизированном C и сборочном коде и вычисляет простое число и строковое представление в ~ 5 секунд.

Способ 4

decimal модуль в Python сохраняет значения в виде десятичных цифр. В последних версиях Python 3 реализована реализация десятичной библиотеки в формате C, которая намного быстрее, чем реализация pure-Python с Python 2. Выполнение C выполняется всего за 3 секунды на моем компьютере.

 from decimal import * getcontext().prec = 23000000 getcontext().Emin = -999999999 getcontext().Emax = 999999999 x=Decimal(2)**74207281 - 1 s=str(x) 

Взял около 32 секунд для вывода файла с помощью WinGhci (язык Haskell):

 import System.IO main = writeFile "prime.txt" (show (2^74207281 - 1)) 

Файл был 21 мегабайт; последние четыре цифры, 6351.

Существует gmp, многоадресная арифметическая библиотека GNU. Он особенно разработан при быстром обращении с огромными числами.

Python - лучший язык программирования в мире.