Есть ли способ получить справедливую реализацию алгоритма Брайана Кернигана для подсчета в Python? - PullRequest
Новая
       6

Есть ли способ получить справедливую реализацию алгоритма Брайана Кернигана для подсчета в Python?

0 голосов
/ 23 сентября 2018

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

Преобразование в строку тогдаподсчет их показался мне плохой идеей.

Теперь плохая идея кажется зацикленной и не использующей встроенные функции при поиске производительности.

import random

x = random.randint(0,1<<1000000)

def count_ones(number):
    c = 0
    while(number !=0 ):
        number = number&(number-1)
        c = c + 1
    return c


%timeit bin(x).count("1")
%timeit count_ones(x)


5.09 ms ± 20 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
25 s ± 544 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

1 Ответ

0 голосов
/ 24 сентября 2018

Алгоритм Кернигана лучше всего работает с данными, которые вписываются в ALU , часто 64-битные на современном оборудовании.Для более длинных чисел алгоритм становится квадратичным по длине числа, потому что каждая итерация выполняет вычисления по всей длине числа.Арифметика может быть оптимизирована вручную, потому что ясно, что как только заимствование перестанет распространяться, в результате побитового преобразования ничего не изменится.

Даже с этой оптимизацией мы все еще находимся на территории Шлемиэля Художника;вычисления являются квадратичными, потому что сканирование эффективно всегда начинается в одном и том же месте на каждой итерации, сканируя все дальше и дальше каждый раз.

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

Битум и бигнум, очевидно, можно было бы сделать на месте, поэтому было бы заманчиво написать: 

number &= number - 1

в надежде, что будет выполнена операция на месте.Но это не будет иметь никакого значения с CPython;Бигнумы CPython неизменны , поэтому мутация на месте невозможна.

Короче говоря, Python собирается создать два новых миллиона-битных числа для каждой итерации.Не удивительно, что это занимает некоторое время.Скорее удивительно, что это занимает всего 25 секунд.

В зависимости от версии и платформы операции CPython bignum выполняются в 15- или 30-битных единицах.(Вычисления на целых числах, которые вписываются в 30 бит, слегка оотимизированы. Но 64 бита находятся далеко за пределами этого диапазона, поэтому не ожидайте, что ограничение чисел 64 битами поможет избежать накладных расходов bignum.) Предполагая, что ваша платформа использует 30-битные блоки, запуститеАлгоритм для ожидаемых полумиллионов итераций означает выполнение более 66 миллиардов однословных вычислений (вычитание и побитовое значение (1000000/30 = 33334) -значений слов), плюс миллион выделенных 130КБ памяти.Делать это за 25 секунд совсем не плохо.Это свидетельство того, насколько быстры современные современные процессоры, и предупреждение о том, как легко не заметить, что вы используете квадратичный алгоритм, пока числа не станут действительно большими.

...