Или почему немного C++ может помочь вам пройти долгий путь

Я рассмотрю алгоритм сложения с использованием Python. Использование побитовых операторов и модулей расширения C++ приводит к почти такой же производительности, как и базовое добавление Python.

Фон

Недавно я много имел дело с байтами и битами. Я подумал, что вернусь к некоторым из старых проблем с алгоритмами, которые я помню, когда-то видел. Одна классическая проблема такова:

Создайте оператор целочисленного сложения «+». Предположим, вы не можете использовать умножение, деление или вычитание. Для простоты предположим, что входными данными могут быть только неотрицательные целые числа.

Давайте сначала подумаем о простом наивном решении этой проблемы. Один из способов сделать это — воспроизвести длинное сложение, но оптимизировать его с помощью простого запоминания.

Медленный метод: добавление поиска

Для длинного сложения вы выравниваете два числа, которые хотите добавить. Начиная с крайнего правого (первая цифра), вы продолжаете добавлять и переносить термины, если два добавленных вами термина больше 9.

Мы описываем алгоритм в псевдокоде, затем рассмотрим простой пример.

Псевдокод

Мы объясним более подробно, что означает этот псевдокод, на примере.

Обход псевдокода

Давайте возьмем пример для сложения двух чисел 23 и 48. Думайте об этих двух числах как о двух массивах строк:

[‘2’, ‘3’] and [‘4’, ‘8’]

Выравниваем цифры, затем идем справа налево. В каждой позиции мы будем добавлять только два однозначных числа (например, 3+8 в позиции 1 и 2+4 в позиции 0).

Нам нужно определить две вещи:

  1. Остаток срока
  2. Срок переноса

Обсудим, что они означают в этом примере.

Позиция 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 алгоритма:

  1. Базовый оператор добавления Python
  2. Добавление поиска (LookupAdd)
  3. Добавление битового сдвига — Python (PyBitshiftAdd)
  4. Добавление битового сдвига — C++ (CPyBitshiftAdd)

Результаты ниже и довольно ясны:

  • Добавление поиска очень медленное: это ожидаемо
  • Bitshift Addition, скомпилированный на C++, работает очень близко к операции Python Base Add, что приятно видеть, учитывая, что это была первая версия:

Заключение

Этот пост был простым пошаговым обзором использования побитовых операций и C++ для создания функции additio, производительность которой не уступает операторам сложения Python.

Want to Connect?
I discuss on similar topics on my personal website.