34% Более быстрый алгоритм преобразования целых чисел в строки

34% Более эффективный алгоритм преобразования целых чисел в строки

Печатаем ли мы целые числа достаточно быстро?

1. Введение

В компьютерном программировании преобразование данного целого числа в строку – это обычная операция, которая должна выполняться, например, перед выводом числа на экран или перед выводом его в текстовый файл, как *.xml, *.json, *.csv, *.txt и т.д.

Известно, что целые числа (а также все остальное) хранятся в компьютерной памяти в бинарном формате – в виде последовательностей 0 и 1. Например:

  • число 12 представлено в памяти как “1100”,
  • и число 29 представлено как “11101”.

Вот почему каждый раз требуется такое преобразование, когда мы хотим привести его в человеко-читаемый, десятичный формат.

В этой статье я собираюсь:

  • проанализировать стандартный алгоритм, используемый для такого преобразования,
  • рассмотреть его существующие оптимизации,
  • предложить свой алгоритм и
  • представить их экспериментальное сравнение.

Мы увидим, что в среднем мой алгоритм работает 25-38% быстрее для 32-битных целых чисел и 40-58% быстрее для 64-битных целых чисел, чем оптимизированный стандартный алгоритм. Его реализацию на языке C++ можно найти на GitHub, как указано в конце.

Конечно, если приложение выводит всего несколько целых чисел за свою жизнь, алгоритм, отвечающий за их преобразование в строки, никогда не станет узким местом. Но в случаях, когда приложение выводит огромное количество данных в текстовые файлы, эффективность алгоритма преобразования начинает играть роль. При работе в таких областях, как Data Science или Machine Learning, возникает необходимость преобразовать множество целых чисел в строки, например, при экспорте набора данных в текстовый файл, такой как *.csv или *.json.

2. Стандартный алгоритм преобразования

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

Чтобы получить последнюю цифру данного целого числа N, просто вычисляется остаток при делении на 10:

“цифра := N mod 10”,

и чтобы ее выбрать, выполняется само целочисленное деление:

“N := N / 10”.

При заданном числе N, как вычисляется его последняя цифра и оставшаяся часть.

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

Как пример полного алгоритма, при печати числа “N = 2’167” будут выполнены следующие операции:

Операции при печати числа “2167”:Шаг 1: 2167 % 10 = 7 (сохранение цифры “7”) , 2167 / 10 = 216 (продолжение с 216),Шаг 2: 216 % 10 = 6 (сохранение цифры “6”) , 216 / 10 = 21 (продолжение с 21),Шаг 3: 21 % 10 = 1 (сохранение цифры “1”) , 21 / 10 = 2 (продолжение с 2),Шаг 4: так как “2 < 10”, просто сохранение последней цифры “2”.Шаг 5: (не показано) обратный порядок сохраненных цифр и их вывод.

Обратите внимание, что когда мы имеем дело с однозначным целым числом (т.е. из диапазона [0..9]), мы можем сразу отправить его на печать, так как у каждой из этих 10 цифр уже фиксированы соответствующие символы. И остаток от деления на 10 всегда является однозначным целым числом.

Также мы можем отметить, что этот алгоритм выводит цифры числа N в обратном порядке (здесь у нас последовательность цифр “7”, “6”, “1”, “2”, вместо того чтобы иметь “2”, “1”, “6”, “7”), поэтому в конце нужно будет развернуть полученную последовательность.

Подводя итог, псевдокод будет выглядеть следующим образом:

var result[0 .. 25] : Array of Characters  // Предположим, не более 25 символов// Процедура принимает целое число 'N' для печати и заполняет его// десятичными цифрами в массиве 'result'.процедура print( N: Integer )    i := 0  // Индекс для массива 'result'    while N > 0        result[ i ] := '0' + (N mod 10)  // Взять последнюю цифру        N := ⌊ N / 10 ⌋   // Извлечь последнюю цифру        i := i+1    result[ i ] := '\0'  // Добавить завершающий символ 'null'    развернуть массив result[0 .. i-1]

Описанный алгоритм прост, и мы легко можем реализовать его в 3-4 строки кода. Но его узкое место заключается в том, что он использует 2 относительно дорогостоящие операции – целочисленное деление и вычисление остатка от деления, для каждой цифры десятичного представления числа N. Известно, что целочисленное деление и вычисление остатка от деления в среднем занимают в 4-5 раз больше времени, чем сложение, вычитание или даже умножение 2 целых чисел. Здесь мы можем наблюдать бенчмаркинг арифметических операций:

Экспериментальное сравнение времени (в наносекундах), затраченного на выполнение 5 видов арифметических операций (каждая операция выполняется 200 раз на случайных данных).Мы видим, что последние 2 операции (целочисленное деление и вычисление остатка от деления) занимают значительно больше времени. Также мы видим, что умножение целых чисел выполняется почти так же быстро, как сложение или вычитание.

Эксперименты проводились с помощью Google Benchmark на следующей системе:

ЦП: Intel Core i7–11800H @ 2.30GHzПЗУ: 16.0 ГБОС: Windows 11 Home, 64-разрядныйКомпилятор: MSVC 2022 ( /O2 /Ob2 /MD /GR /Gd )

Давайте посмотрим, существуют ли более быстрые способы вывода целых чисел…

3. Существующие оптимизации

Оптимизация 1

Одна распространенная оптимизация для описанного алгоритма заключается в устранении последнего шага – развороте полученной последовательности цифр. Фокус хорошо представлен, например, в [1]. В рамках этой оптимизации мы будем сразу записывать цифры в буфер в правильном порядке. И поскольку сам алгоритм сообщает цифры данного целого числа N справа налево, мы также их будем записывать в буфер справа налево.

Заполнение полученных цифр в массив result справа налево,напрямую в том порядке, в котором они должны быть в конце.

Псевдокод с этой оптимизацией будет выглядеть следующим образом:

var result[0 .. 25] : Array of Characters  // Предположим, не более 25 символов// Функция принимает целое число 'N' для печати и возвращает позицию// его первого преобразованного символа в массиве 'result'.function print( N: Integer ) : Integer    result[ 25 ] := '\0'  // Разместить завершающий символ 'null' в конце    i := 25  // Индекс для массива 'result'    while N > 0        i := i-1  // Здесь мы переходим влево, чтобы разместить следующую цифру        result[ i ] := '0' + (N mod 10)  // Взять последнюю цифру        N := ⌊ N / 10 ⌋  // Извлечь последнюю цифру    return i  // Позиция, с которой начинается преобразованное целое число

Обратите внимание, что в этом и во всех других псевдокодах в этой истории мы не рассматриваем случай печати числа “0”. Согласно всем написанным алгоритмам, “0” будет результатом последовательности, в которой нет цифр вообще, и поэтому в большинстве алгоритмов печати “0” выполняется в отдельной ветке. Здесь мы пропустим эту ветвь для компактности.

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

Недостатком этой оптимизации является то, что позиция первого символа становится переменной, так как она зависит от количества цифр, которые имеет целое число N.

Drawback of optimization 1: numbers with different digits count will start in the output array from different positions.

Однако на практике это не становится проблемой, потому что преобразованные целые числа часто немедленно отправляются в текстовый файл или на экран, так что они не остаются в памяти надолго. И для таких целей нам не требуется, чтобы преобразованные цифры были записаны, начиная с некоторой заранее заданной позиции памяти.

Оптимизация 2

Следующая оптимизация заключается в использовании операций целочисленного деления и получения остатка, чтобы получить 2 цифры N за один шаг. Этот трюк также хорошо задокументирован в [1] и [2]. В этом случае, вместо повторного вычисления

«цифра := N mod 10», за которым следует «N := N / 10»,

мы будем вычислять:

“digits := N mod 100”, а затем “N := N / 100”,

что даст нам последние 2 цифры N, а затем обрежет их обе.

Operations for printing number “5174092” with second optimization enabled:Step 1: 5174092 % 100 = 92 (storing digits “92”) , 5174092 / 100 = 51740 (continuing with 51740),Step 2: 51740 % 100 = 40 (storing digits “40”) , 51740 / 100 = 517 (continuing with 517),Step 3: 517 % 100 = 17 (storing digits “17”) , 517 / 100 = 5 (continuing with 5),Step 4: As “5 < 100”, just storing the last digit “5”.

Заметьте, что для того, чтобы в конечном итоге и эффективно распечатать эти полученные 2 цифры, нам следует подготовить массив длиной 100 (с индексами от 0 до 99 – поэтому соответствующих всем возможным остаткам “N mod 100”), где значения будут пары символов, начиная с “00”, “01”, “02”, и так далее до “98”, “99”.

В рамках этой оптимизации количество операций целочисленного деления и получения остатка сокращается почти в 2 раза.

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

4. Мой алгоритм

Я предлагаю еще один алгоритм, который ускорит вывод целых чисел примерно на 25–38% для 32-разрядных чисел и на 40–58% для 64-разрядных чисел. Идея заключается в следующем: а что, если мы будем выбирать цифры из данного целого числа N не справа налево, а слева направо? То есть, сначала мы получим самую значимую цифру, затем следующую значимую цифру и так далее, пока не останется только наименее значимая цифра. Это становится сложнее, если мы заранее не знаем количество цифр числа N, но пока отложим этот вопрос и предположим, что мы уже знаем, что в N L цифр.

Пример вводного числа N, которое имеет L=7 цифр.

Как мы получим самую значимую цифру? Снова с помощью целочисленного деления, но на этот раз так:

«цифра := N / 10^(L-1)»

Примеры получения самой левой цифры из заданных целых чисел.

А как мы будем выбирать ее из N, чтобы продолжить работу с оставшейся частью? Зная значение самой значимой цифры «d», мы можем выполнить следующее вычитание:

«N := N — d*10^(L-1)»

Примеры выбора самых левых цифр из заданных целых чисел.

Позже мы будем повторять операции деления и вычитания, пока N не станет целым числом из одной цифры (т.е. в диапазоне [0..9]), и наконец, мы выведем эту цифру. Давайте посмотрим, как алгоритм будет работать для случая «N = 6’129». Обратите внимание, что здесь у нас 4 цифры, поэтому мы начинаем с «L=4»:

Операции для вывода числа

Вы можете возразить, что вычисление различных степеней 10 занимает больше времени, чем целочисленное деление или вычисление остатка. И вы будете абсолютно правы, кроме одной детали: мы можем предварительно вычислить все необходимые степени 10 и использовать их во время выполнения программы. Для 32-разрядных чисел есть всего 10 различных степеней 10, а для 64-разрядных чисел есть 20 степеней 10. Поэтому сохранение их всех предварительно вычисленными в памяти не будет проблемой.

Итак, что у нас в итоге? Чтобы напечатать одну цифру N с помощью моего алгоритма, мы делаем следующее:

1 деление нацело,1 умножение и1 вычитание,

в сравнении со стандартным алгоритмом:

1 вычисление остатка и1 деление нацело.

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

Псевдокод основной части моего алгоритма может выглядеть так:

var powers_of_10[0 .. 10]: Массив целых чисел = {1, 10, 100, 1'000, ..., 100'000'000, 1'000'000'000} // Предварительно вычисленные степени 10, которые будут использованы при печати var result[0 .. 25]: Массив символов // Предполагаем максимум 25 символов// Процедура принимает целое число 'N' для печати и заполняет его// десятичными цифрами в массив 'result'.процедура print(N: Integer)    L := calculate_digits_count(N)    i := 0   // Индекс в массиве 'result'    while L> 0        digit := ⌊ N / powers_of_10[L-1] ⌋  // Получаем крайнюю левую цифру        result[i] := '0' + digit   // Записываем ее в массив 'result'        N := N – digit * powers_of_10[L-1]  // Вычисляем оставшуюся часть        L := L-1  // Соответствующим образом корректируем количество цифр        i := i + 1    result[i] := '\0' // Добавляем завершающий нулевой символ 

Поскольку мой алгоритм печатает цифры N слева направо, я хочу назвать его «Принтер слева направо» или просто «LR принтер».

Единственное, что остается, это эффективно найти L — количество десятичных цифр N. И к счастью для нас, предварительно вычисленный массив степеней 10 также поможет здесь. Мы просто можем перебирать этот массив от меньших степеней до больших, пока не найдем такую степень 10^L, которая будет больше N. Тогда само число L будет представлять собой количество цифр в N.

Например, получение количества цифр для «N = 23’504» будет выглядеть следующим образом:

Как рассчитывается количество цифр L для числа N = 23'504.Мы последовательно сравниваем N с степенями 10, пока N не станет меньше.Это происходит при степени 100'000, которая равна 10⁵, поэтому мы заключаем, что L=5.

Псевдокод этой функции может выглядеть следующим образом:

// Функция принимает целое число 'N' и возвращает количество его цифр.function calculate_digits_count(N: Integer): Integer    // Проверяем случай чисел с максимальным количеством цифр    if N >= powers_of_10[9]  // Сравниваем с максимальной степенью 10        return 10  // Количество цифр для таких чисел    // Обычный случай    L := 0    while N >= powers_of_10[L]         L := L + 1    return L

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

Обратите внимание, что поскольку «LR принтер» выводит цифры N слева направо, нет необходимости делать обратный порядок в конце. Кроме того, в отличие от существующей оптимизации 1, здесь у нас есть возможность указать, где в памяти должна быть размещена первая цифра преобразованного N.

«LR принтер» можно использовать для печати чисел в любой системе счисления (не только десятичной). Для этого нам просто нужно заменить предварительно вычисленные степени 10 на предварительно вычисленные степени новой системы счисления.

Реализацию «LR принтера» на языке C++ можно найти на GitHub по ссылке [3].

Оптимизация 2 для «LR принтера»

Мой алгоритм может быть улучшен с помощью второй оптимизации, описанной в разделе “Существующие оптимизации” и документированной в [1] и [2]. Если это сделать, то вме­сто печати данного числа цифра за цифрой на каждом шаге, мы будем печатать его двузначными числами на каждом шаге.

Давайте посмотрим, как это будет работать, например, для числа “N = 4’610’937”. Здесь L=7, и мы начинаем делить N на 10^(L-2)=10’000 в этот раз:

Действия для печати числа “4610937” с включенной второй оптимизацией для принтера “LR”: Шаг 1: 4610937 / 10⁵ = 46 (печатаем цифры '46'), 4610937–46*10⁵ = 10937 (продолжаем с числом 10937), Шаг 2: 10937 / 10³ = 10 (печатаем цифры '10'), 10937–10*10³ = 937 (продолжаем с числом 937), Шаг 3: 937 / 10 = 93 (печатаем цифры '93'), 937–93*10 = 7 (продолжаем с числом 7), Шаг 4: Поскольку “7 < 100”, просто печатаем последнюю цифру '7'.

Включение этой оптимизации обойдется нам:

1 целочисленное деление,1 умножение и1 вычитание,

на 2 цифры входного числа.

Здесь снова цифры будут получены в естественном порядке — слева направо, поэтому нет необходимости переворачивать их в конце.

Реализацию принтера “LR” с включенной второй оптимизацией также можно найти на GitHub по адресу [3].

5. Сравнение существующих алгоритмов с помощью экспериментов

Проведение экспериментального сравнения является важным для такого типа работы, поэтому в этой главе я представлю результаты сравнения следующих алгоритмов печати целых чисел:

  • стандартный алгоритм с первой оптимизацией (обозначен как “Std”),
  • мой алгоритм “LR принтер” (обозначен как “LR”),
  • стандартный алгоритм с также второй оптимизацией (обозначен как “Std [2-знач]”), и
  • “LR принтер” с второй оптимизацией (обозначен как “LR [2-знач]”).

Каждый из этих алгоритмов был протестирован как на 32-битных, так и на 64-битных числах с разным количеством цифр во входных числах.

Печать чисел в основании = 10:

Результаты при печати в основании = 10 (обычный случай) следующие:

Время (в наносекундах), затраченное на печать 1 числа (32-битного или 64-битного) с определенным количеством цифр с помощью разных алгоритмов. Печать выполняется в основании = 10.

Для 32-битных целых чисел мы видим, что прирост “LR-принтера” по сравнению со стандартным принтером составляет около 30–38%. Прирост при печати со второй оптимизацией (печать 2-х цифр на одном шаге) ниже — 13–28%. Это полностью ожидаемо, так как в целом в данном случае мы делаем только 2 или 4 шага.

Когда речь идет о печати 64-битных целых чисел, производительность моего алгоритма даже лучше. “LR-принтер” работает примерно на 40–50% быстрее стандартного алгоритма. И при включенной второй оптимизации для обоих алгоритмов “LR-принтер” работает на 47–58% быстрее.

Процент в заголовке этой истории был выбран, исходя из наиболее распространенного случая: когда мы находимся в основании = 10, работаем с 32-битными целыми числами и предполагаем, что у них много цифр. В этом случае прирост производительности “LR-принтера” по сравнению со стандартным алгоритмом составлял 30–38%, поэтому среднее значение составляет около 34%.

Печать чисел в основании = 3:

Также давайте посмотрим, будут ли значительно отличаться результаты при печати целых чисел в другом основании. Мы будем наблюдать печать в основании = 3:

Время (в наносекундах), затраченное на печать 1 числа (32-битных или 64-битных), имеющего определенное количество цифр, с использованием разных алгоритмов. Печать выполняется в основании = 3.

Как мы видим здесь, для 32-битных целых чисел прирост производительности “LR-принтера” по сравнению со стандартным алгоритмом составляет около 25–33%, что в целом соответствует разнице в производительности используемых арифметических операций.

А для 64-битных целых чисел прирост производительности “LR-принтера” составляет около 50–55% для коротких чисел (8 цифр) и 27–30% для длинных чисел (36 цифр).

Общие замечания

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

Почти всегда такое, что с увеличением количества цифр “LR-принтер” (или “LR-принтер [2-цифр.] вариант”) превосходит стандартный алгоритм печати (или его вариант “2-цифр.”). Это тоже понятно, поскольку с увеличением количества цифр уменьшается влияние инструкций, выполняемых вне цикла (например, вызов одной функции из другой или размещение нулевого символа в конце строки).

И в целом, при печати 64-битных целых чисел результаты более впечатляющие как для “LR-принтера”, так и для его варианта “LR-принтер [2-цифр.]”.

Лично для меня эти результаты довольно заметны.

6. Заключение

Мы представили новый алгоритм преобразования целых чисел в строки и назвали его “LR-принтер”. Он работает на 25–38% быстрее для 32-битных целых чисел и на 40–58% быстрее для 64-битных целых чисел по сравнению с оптимизированным стандартным алгоритмом преобразования. Наш алгоритм может работать в любом основании числа (а не только в обычном основании 10).

Алгоритм, который преобразует целые числа в строки, не является узким местом для приложений, которые печатают только несколько чисел за всю свою жизнь. Но для других типов приложений, которые автоматически генерируют текстовые файлы, такие как *.csv, *.xml или *.json, эффективность алгоритма преобразования имеет значение. Это особенно важно, если эти текстовые файлы будут содержать множество чисел, как это бывает при экспорте больших наборов данных.

Большое спасибо за то, что дочитали до конца! Буду рад прочитать любые комментарии ниже!

Выражаю благодарность Давиду Айрапетяну (https://www.linkedin.com/in/davidayrapetyan/) за тщательное рассмотрение черновика этой истории и предложение множества контекстных улучшений и грамматических исправлений.

Благодарность Хайку Асланяну (https://www.linkedin.com/in/haykaslanyan/) за технический обзор черновика и предложение других улучшений.

Дизайн иллюстраций от Аси Папян: https://www.behance.net/asyapapyan

Если вам понравилась эта история, вы можете найти меня на LinkedIn: https://www.linkedin.com/in/tigran-hayrapetyan-88989b12/

Ссылки

[1]: «Преобразование целого числа в строку» — https://tia.mat.br/posts/2014/06/23/integer_to_string_conversion.html

[2]: «Три совета по оптимизации C++» — https://www.facebook.com/notes/10158791579037200/

[3]: «Реализация принтера LR на языке C++» — https://github.com/tigranh/lr_printer