Или почему немного C++ может помочь вам пройти долгий путь
Я рассмотрю алгоритм сложения с использованием Python. Использование побитовых операторов и модулей расширения C++ приводит к почти такой же производительности, как и базовое добавление Python.
Фон
Недавно я много имел дело с байтами и битами. Я подумал, что вернусь к некоторым из старых проблем с алгоритмами, которые я помню, когда-то видел. Одна классическая проблема такова:
Создайте оператор целочисленного сложения «+». Предположим, вы не можете использовать умножение, деление или вычитание. Для простоты предположим, что входными данными могут быть только неотрицательные целые числа.
Давайте сначала подумаем о простом наивном решении этой проблемы. Один из способов сделать это — воспроизвести длинное сложение, но оптимизировать его с помощью простого запоминания.
Медленный метод: добавление поиска
Для длинного сложения вы выравниваете два числа, которые хотите добавить. Начиная с крайнего правого (первая цифра), вы продолжаете добавлять и переносить термины, если два добавленных вами термина больше 9.
Мы описываем алгоритм в псевдокоде, затем рассмотрим простой пример.
Псевдокод
Мы объясним более подробно, что означает этот псевдокод, на примере.
Обход псевдокода
Давайте возьмем пример для сложения двух чисел 23 и 48. Думайте об этих двух числах как о двух массивах строк:
[‘2’, ‘3’] and [‘4’, ‘8’]
Выравниваем цифры, затем идем справа налево. В каждой позиции мы будем добавлять только два однозначных числа (например, 3+8 в позиции 1 и 2+4 в позиции 0).
Нам нужно определить две вещи:
- Остаток срока
- Срок переноса
Обсудим, что они означают в этом примере.
Позиция 1
- Начните с двух членов: (3,8)
- Остаток шага: остаток(3,8) = 1 (поскольку 3+8 = 11 по модулю 10 = 1)
- Шаг переноса: перенос (3,8) = 1 (потому что 3+8 > 9)
- Добавить оставшийся шаг в выходной массив: [1]
Позиция 0
- Начните с двух терминов: (2, 4)
- Вынести оставшийся член из предыдущего шага: (2+1, 4)
- Остаток Шаг: остаток (3, 4) = 7
- Шаг переноса: перенос (3,4) = 0
- Добавьте оставшийся шаг в выходной массив: [7, 1]
Последний шаг
- Возврат объединенного массива: 71
Мы видим, что в позиции 1 оставшийся шаг дает нам цифру на выходе, тогда как шаг переноса увеличивает цифры в следующей позиции (т.е. позиции 0). Мы повторяем этот процесс, добавляя выходной массив, используя оставшийся шаг, пока не исчерпаем оба массива.
Код Python
Теперь о коде на питоне. К сожалению, это очень сложно. Мы не будем тратить время на рефакторинг этого, потому что другое решение и читабельнее, и быстрее.
Простые ускорения
Мы можем запомнить оставшиеся шаги и шаги переноса, определив массивы поиска: Остаток и Перенос. Мы не будем углубляться в это, но это было основным улучшением скорости для этого алгоритма.
Остаток массива
Переносной массив
Быстрый метод: добавление битового сдвига
Другой путь решения проблемы — использование операторов битового сдвига. Битовый сдвиг эквивалентен умножению или делению числа на некоторое базовое число. Например, в базе 2 число 4 представлено как [1,0,0]. Помните, что биты — это просто коэффициенты, поэтому 4=1*2²+0*2¹+0*2⁰
.
Битовый сдвиг 4 влево эквивалентен умножению 4 на число 2, таким образом, BitshiftLeft(4)=8=[1,0,0,0]
.
Псевдокод
Ниже у нас есть псевдокод для побитового алгоритма. Вы сразу заметите, что добавление битового сдвига не зависит от поисковых массивов, а его псевдокод намного короче. Оказывается, его код на python/c++ тоже очень-очень короткий.
Прогулка по псевдокоду
Я пройдусь по логике того, как это работает. Давайте сделаем более простое сложение, чем раньше, предположив, что мы хотим сложить 5+3.
Преобразуем 5, 3 и 8 (ответ) в двоичное представление с основанием 2:
5=1*2² +0*2¹+1*2⁰
3=0*2² +1*2¹+1*2⁰
8=1*2³+0*2²+0*2¹ +0*2⁰
Что мы будем делать, так это в основном повторять нашу переносную логику сверху, но на этот раз в двоичном виде. Это позволяет нам выполнять перенос «векторизованным» способом.
Подход пытается найти двухбитовые наборы, в которых нет перекрывающихся битов, значения которых больше 0. Для этого мы попеременно используем битовые сдвиги и битовые маски. Базовый вариант алгоритма определяет x, y как входные значения, которые мы пытаемся сложить вместе:
x=[1, 0, 1]
(т.е. 5 по основанию 2)y=[0,1,1]
(т.е. 3 по основанию 2)
Итерация 1
Шаг 1. Шаг переноса с использованием побитового оператора AND и битового сдвига
Этот шаг просто ищет общие биты между 3 и 5, а затем переносит их на следующий шаг. Мы объединяем AND и битовый сдвиг влево, чтобы переопределить x:
x=BitshiftLeft(And(x,y)) = [0,1,0]
Разбивая эти шаги:
And(x,y) = [0, 0, 1]
(потому что 5 и 3 делят 2⁰)BitshiftLeft([0,0,1]) = [0, 1, 0]
(это эквивалентно 2¹=2⁰+2⁰)
Шаг 2. Предотвратите дублирование шага подсчета с помощью побитового оператора ИЛИ и битовой маски
На шаге 1 мы удалили биты, которые были общими для x и y. Мы хотим удалить эти биты из y.
y=BitMask(Or(x,y), ~And(x,y))=[1,1,0]
Разбивая эти шаги:
~And(x,y) = [1, 1, 0]
(это биты, которые мы не удалили на шаге 1, мы хотим сохранить)Or(x,y) = [1, 1, 1]
(это биты, которые нам нужно замаскировать)BitMask([1, 1, 1], [1, 1, 0]) = [1, 1, 0]
(замаскируйте биты в позиции 2⁰)
Условие остановки
Мы продолжаем выполнять эти итерации до тех пор, пока x и y не перестанут иметь общие биты, т. е. мы можем просто сложить битовое представление. В этом примере это окончательные значения x и y:
- Конечный x=[1, 0, 0, 0]
- Конечный у = [0, 0, 0, 0]
Мы используем оператор OR, чтобы получить наше решение:
8 = Or(x, y) = [1, 0, 0, 0]
Код Python
Код Python относительно короткий и простой.
Простые ускорения — модуль расширения C++
Одно из простых ускорений — написать код на C++ и создать модуль расширения C++. Код модуля расширения приведен ниже. Фактическая функция C++, которую мы будем вызывать в python, определена как c_bitadd_method
, остальная часть кода предназначена для определения классов/методов C++, чтобы ее можно было интегрировать с Python.
Полученные результаты
Я провожу простой эксперимент, варьируя два параметра:
- Общее количество выборок: используйте три значения: 100 тыс., 1 млн, 10 млн.
- Максимально возможное число: используйте три значения: 100k, 10mil, 1bil
Эти два параметра изменяют общее количество выполняемых сложений, а также размер целых чисел. Например, если максимально возможное число = 1 миллиард, это означает, что потенциально функция сложения должна будет складывать целые числа до 1 миллиарда.
Я тестирую 4 алгоритма:
- Базовый оператор добавления Python
- Добавление поиска (LookupAdd)
- Добавление битового сдвига — Python (PyBitshiftAdd)
- Добавление битового сдвига — C++ (CPyBitshiftAdd)
Результаты ниже и довольно ясны:
- Добавление поиска очень медленное: это ожидаемо
- Bitshift Addition, скомпилированный на C++, работает очень близко к операции Python Base Add, что приятно видеть, учитывая, что это была первая версия:
Заключение
Этот пост был простым пошаговым обзором использования побитовых операций и C++ для создания функции additio, производительность которой не уступает операторам сложения Python.
Want to Connect? I discuss on similar topics on my personal website.