Быстрый метод для тестирования небольшого большого int - PullRequest
Новая
       32

Быстрый метод для тестирования небольшого большого int

4 голосов
/ 01 ноября 2019

В теоретико-числовом алгоритме, манипулирующем очень большим целым числом n (от сотен тысяч бит до нескольких миллионов), мне нужно проверить j th бит. Любая из этих работ: 

if 1<<j & n != 0 :
    # bit j of n is set

if n>>j & 1 != 0 :
    # bit j of n is set

, но продолжительность теста возрастает линейно с n.bit_length() (для j вдвое меньше). Иначе, в соответствии с big-O нотацией , время равно O (log (n)), когда это может быть O (1).

Существует ли идиома O (1) дляпроверить немного int в Python 3 (.8), как у нас mpz_tstbit() в GMP?

Если нет, то где находится окно для предложений Python?

Добавление за комментарий : n.bit_length() не более 1<<24, с j < n.bit_length() и j>=0.

Ответы [ 2 ]

4 голосов
/ 05 ноября 2019

Отказ от ответственности: я поддерживаю gmpy2.

gmpy2 поддерживает битовый доступ несколькими различными способами. gmpy2.bit_test(n,j) будет проверять j-й бит n. n может быть целым числом Python или целым типом gmpy2. 

>>> gmpy2.bit_test(78,2)
True

Целочисленный тип gmpy2.mpz поддерживает метод bit_test. Также поддерживаются другие методы. 

>>> a=gmpy2.mpz(123456)
>>> a.bit_test(27)
False

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

>>> a=gmpy2.xmpz(123456)
>>> a[27]
0
>>> a[27]=1
>>> a[27]
1
>>> a[27:30]
mpz(1)
>>> a[27:30] = -1
>>> a[27:30]
mpz(7)

Вы можете использовать xmpz целые числа в обычных математических операциях. Если вы используете только немедленные операции (+ =, * = и т. Д.), То объект xmpz будет обновлен на месте. 

>>> a
xmpz(939647552)
>>> b=a
>>> a+=9999
>>> a
xmpz(939657551)
>>> b
xmpz(939657551)

xmpz целые числа иногда немного странны,но они обычно очень быстры для прямого доступа к битам.

2 голосов
/ 02 ноября 2019

Если ваш «j» зафиксирован, вы можете записать число в буквальной форме вместо использования «j» - компилятор Python записал бы «1 << j» как литерал, и у вас была бы одна операция вместо двух(То есть, если «j» не является переменной и всегда, скажем, «10204», вы должны написать <code>1 << 10204)

Тем не менее, я думаю, что вы представляете себе, что этот алгоритм запускается как «спокойно толкающий1 000 бит слева, один за другим »- это не то, что происходит.

Алгоритм для больших целых чисел, вероятно, значительно оптимизирует создание целого числа« 1 << j »- и в то же времярезультат того, что <code>& n будет «линейным», все равно будет очень быстрой операцией.

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

В прошлом я использовал библиотеку GMP2 - доступную для Python как gmpy2 и получил хорошие результаты. \

Что касается специфики вашего вопроса о попыткахчтобы ускорить процесс, написав другие выражения для битового тестирования: это определенно неправильный подход -

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

Ускорение, которое вы получите по сравнению с обычным битовым тестированием &, заключается в том, что ваша функция заранее знает, что она должна соответствовать одному биту в одном из операндов, и не должна искать другой "1 "бит в другом операнде - поэтому операция будет O (1).

Но я бы поспорил, что ускорение, которое вы получите от этого, будет слишком маленьким - имейте в виду, чтопри «преждевременной оптимизации - корень зла».

обновление : gmp не быстрее для построения номера 1 << j: </p> 


In [22]: a = bmpy2.numer(1); b = gmpy2.numer(10_000_000)                                                                                                   

In [23]: %timeit a << b                                                                                                                
25.8 µs ± 508 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [24]: %timeit 1 << 10_000_000                                                                                                       
27.2 µs ± 239 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
...