我们打印整数的速度足够快吗？
1. 简介
在计算机编程中，将给定的整数转化为字符串是一种常见的操作，在将整数打印到屏幕上或将其打印到任何一种文本文件（例如*.xml、*.json、*.csv、*.txt等）之前，都应该这样做。
众所周知，整数（以及其他所有东西）以二进制格式存储在计算机内存中，即由一串0和1组成。例如：
- 数字12在内存中的表示为“1100”，
- 数字29在内存中的表示为“11101”。
这就是为什么每次要进行这种转换的原因，因为我们要将其转换为人类可读的十进制格式。
在本文中，我将：
- 概述用于此类转换的标准算法，
- 观察其现有的优化方法，
- 提出我的算法，并
- 展示它们的实验比较结果。
我们将看到，对于32位整数，我的算法在平均情况下运行速度比优化后的标准算法快了25–38%，对于64位整数，快了40–58%。C++语言的实现可以在GitHub上找到，末尾有参考。
当然，如果应用程序在其生命周期内只打印少量整数，负责将其转换为字符串的算法永远不会成为瓶颈。但是，对于那些将大量数据输出到文本文件中的情况，转换算法的效率开始起作用。在进行数据科学或机器学习等领域的工作时，当将数据集导出到文本文件（例如*.csv或*.json）中时，需要将大量整数转换为字符串。
2. 标准转换算法
由于将整数转换为字符串是一种常见的操作，所以任何现代编程语言都会实现该算法，无论是作为语言本身的一部分还是作为其标准库的一部分。该算法几乎无处不在，它基于反复获得和挑选整数的最后一位，并继续处理其剩余部分。
为了获得给定整数N的最后一位，它只需计算其除以10的余数：
“digit := N mod 10”，
为了挑选它，它执行整数除法本身：
“N := N / 10”。
请注意，在本文中，当进行2个整数的除法时，我们假设只取结果的整数部分。
以“N = 2’167”为例，打印数字的完整算法将执行以下操作：
请注意，当我们处理1位数时（即范围[0..9]），我们可以直接发送它进行打印，因为每个数字的对应字符已经确定。而且，除以10的余数总是一个1位数。
另外，我们还可以注意到，该算法以N的逆序报告数字（这里我们得到了数字序列’7’、’6’、’1’、’2’，而不是’2’、’1’、’6’、’7’），因此需要在最后反转所生成的序列。
总结一下，伪代码如下：
var result[0 .. 25] : 字符数组 // 假设最多25个字符// 该过程接受待打印的整数N，并将其小数位字符填充到'result'数组中。过程主体：procedure print( N: 整数 ) 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行代码实现。但是，它的瓶颈在于对N的每个数字的十进制数进行了2次相对昂贵的操作 —— 整数除法和整数求余运算。众所周知，平均而言，整数除法和求余运算的时间要比两个整数的加法、减法甚至乘法花费4-5倍的时间更长。这里我们可以观察到所提到的算术运算的时间基准：
这些实验是在以下系统中进行的：
CPU: Intel Core i7–11800H @ 2.30GHzRAM: 16.0 GBOS: Windows 11 Home, 64-bitCompiler: MSVC 2022 ( /O2 /Ob2 /MD /GR /Gd )
让我们看看是否存在更快的整数打印方法…
3. 已有的优化
优化 1
所描述的算法的一种常见优化是消除反转生成的数字序列的最后一步操作。这个技巧在 [1] 中有很好的介绍。在这种优化中，我们将以正确的顺序直接将数字写入缓冲区。由于算法本身从右到左报告给定整数 N 的数字，所以我们也将从右到左将它们写入缓冲区。
具有此优化的伪代码如下：
var result[0 .. 25] : 字符数组 // 假设最多25个字符// 该函数接受待打印的整数N，并返回其转换后第一个字符在'result'数组中的位置。函数主体：function print( N: 整数 ) : 整数 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的位数。
然而，实际上，这并不成为一个问题，因为转换后的整数通常会迅速发送到文本文件或屏幕上，因此不会在内存中停留很长时间。对于这样的用途，我们不需要转换后的数字从内存的某个精确指定的位置开始写入。
优化2
下一个优化是使用整数除法和求余计算操作一次获得N的2位数字。这个技巧在[1]和[2]中也有很好的文档记录。为此，我们将计算：
“digits := N mod 100”，然后是“N := N / 100”，
这将给我们N的最后2位数字，然后将它们都去掉。
请注意，为了最终高效地打印这两个数字，我们应该准备一个长度为100的数组（索引从0到99，因此对应于所有可能的余数“N mod 100”），其中的值将是字符对，从“00”，“01”，“02”，…一直到“98”，“99”。
在这个优化中，整数除法和求余操作的次数几乎减少了一半。
最后，我想提醒您即使启用了上述两个优化，我们仍然需要进行与给定整数N的位数成比例的整数除法和求余计算操作次数。
4. 我的算法
我将提出另一个算法，它将加速32位整数的打印速度约为25-38%，而对于64位整数，加速速度约为40-58%。这个想法是什么呢？如果我们不是从右到左地从给定的整数N中选取数字，而是从左到右地选取呢？所以首先，我们将得到它最高位的数字，然后是下一个最高位的数字，以此类推，直到只剩下最低位的数字。如果我们事先不知道N中的数字个数，这样做会变得有些困难，但现在我们先抛开这个问题，假设我们已经知道N有L个数字。
那我们如何获取最高位的数字呢？同样使用整数除法，但这次是：
“digit := N / 10^(L-1)”
那么我们如何从N中选出它，以便能够继续处理剩下的部分呢？在知道最高位数值为’d’后，我们可以进行以下减法：
“N := N — d*10^(L-1)”
随后，我们将重复进行除法和减法操作，直到N成为1位数的整数（即在范围[0..9]内），最后也会打印出该数字。让我们看看算法对“N = 6’129”这一示例的工作原理。请注意，它有4个数字，所以我们从“L=4”开始：
你可能会认为计算不同的10的幂比进行整数除法或求余计算更耗时。在这一点上你是完全正确的，但有一个细节例外：我们可以预先计算所有必要的10的幂，并在程序的整个执行过程中使用它们。对于32位整数，只有10个不同的10的幂，而对于64位整数，有20个10的幂。因此，把它们全部预先计算在内存中不会成为问题。
那么我们总体来说有什么呢？为了用我的算法打印N的一个数字，我们需要进行以下操作：
1次整数除法，1次乘法和1次减法，
与标准算法相比：
1次求余计算和1次整数除法。
在下一部分中，我们将看到我的方法实际上更好，因为乘法和减法一起所需的CPU时间比求余计算更少。在第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'数组中.过程打印（N：整数） L := 计算数字数量(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' // 添加终止的'null'字符由于我的算法从左到右打印N的数字，我想称之为“从左到右打印机”或简称“LR打印机”。
仅剩下一个问题，那就是高效地找到L——N的十进制数字的数量。幸运的是，预先计算的10的幂数组在这里也有帮助。我们可以从较小的幂到更大的幂迭代该数组，直到找到一个幂10^L，使其大于N为止。然后指数L本身将表示N的数字数量。
例如，对于“N = 23’504”的数字数量获取过程如下：
该函数的伪代码可能如下：
// 该函数接受整数'N'并返回其数字数量.function calculate_digits_count( N: Integer ) : Integer // 检查具有最大数字数量的数字 if N >= powers_of_10[ 9 ] // 与10的最大幂比较 return 10 // 对于这样的数字，返回数字数量为10 // 常规情况 L := 0 while N >= powers_of_10[ L ] L := L+1 return L通过这2部分，我们提供了完整的整数转换为字符串的算法。
注意，由于“从左到右打印机”从左到右报告N的数字，因此在最后不需要进行任何反转。另外，与现有优化1相反，在这里我们保留了指定转换后的N的第一个数字应放置在内存中的位置的能力。
“从左到右打印机”可用于以任何进制（不仅仅是10进制）打印数字。为此，我们只需要用新进制的预先计算的幂来替换预先计算的10的幂。
可以在GitHub上找到用C++语言实现的“从左到右打印机”代码[3]。
“从左到右打印机”的优化2
我的算法可以通过“现有优化”部分中描述的第二种优化来增强，并且在[1]和[2]中有详细的记录。如果完成了，在每一步中，我们将以两位数字的形式打印给定的数字，而不是一位数字。
让我们看看它是如何在数字“N = 4’610’937”上运行的。这里L=7，我们从将N除以10^(L-2)=10’000开始：
通过启用此功能，我们将花费：
1次整数除法，1次乘法和1次减法，
每2个输入数字的数字。
在这里，数字将按照自然顺序从左到右获得，因此在最后无需颠倒它们。
启用第二种优化的“LR打印机”的实现也可以在GitHub上找到[3]。
5. 与现有算法的实验比较
进行实验比较对于这类工作是必不可少的，因此在本章中，我将介绍以下整数打印算法的比较结果：
- 带有第一种优化的标准算法（标记为“Std”），
- 我的算法“LR打印机”（标记为“LR”），
- 带有第二种优化的标准算法（标记为“Std [2-dig]”），以及
- 带有第二种优化的“LR打印机”（标记为“LR [2-dig]”）。
对于32位和64位整数，每个算法都进行了测试，输入数字的位数不同。
以base=10打印数字：
在以base=10（普通情况）打印时的结果如下：
对于32位整数，我们可以看到“LR打印机”相比标准打印机的增益约为30-38%。当使用第二个优化（一步打印两个数字）进行打印时，增益较低 — 约为13-28%。这是完全预料的，因为在这种情况下我们只需要执行2或4个步骤。
当涉及到打印64位整数时，我的算法性能更好。“LR打印机”比标准算法运行速度快40-50%。并且对于两者都启用第二个优化，“LR打印机”的性能提升达到47-58%。
本文标题中的百分比是通过考虑最常见的情况得出的：当我们处于基数为10、使用32位整数，并假设它们有多位数字时。对于该情况，“LR打印机”相对标准算法的性能提升为30-38%，所以取平均约为34%。
以基数=3打印数字：
让我们看看在以另一个基数打印整数时结果是否会有显著差异。我们观察在基数为3的情况下的打印：
我们可以看到，对于32位整数，“LR打印机”相对于标准算法的性能提升约为25-33%，这通常对应于所使用的算术操作的性能差异。
而对于64位整数，对于短数字（8位数），“LR打印机”的性能提升约为50-55%，对于长数字（36位数），性能提升约为27-30%。
总结
通常，整数的打印基数对于相对性能提升影响不大，因为打印过程中要执行的操作次数与输入数字的位数成比例，而不是与这些位可能具有的可能值数量成比例。
几乎总是情况下，位数越多，“LR打印机”（或“LR打印机[2位]”变种）相对于标准打印算法（或其“2位”变种）的性能提升越大。这也很明显，因为我们拥有的数字越多，出循环的指令的影响就越小（例如从一个函数调用另一个函数，或者放置空终止字符）。
总的来说，当打印64位整数时，“LR打印机”和“LR打印机[2位]”变种的结果更令人印象深刻。
对我个人来说，这些结果非常显著。
6. 结论
我们提出了一个新的整数转字符串的算法，并称其为“LR打印机”。相比于优化的标准转换算法，它对于32位整数的运行速度快25-38%，对于64位整数的运行速度快40-58%。我们的算法可以在任何基数下工作（不仅仅是普通的十进制）。
将整数转换为字符串的算法对于只在其生命周期内打印少量数字的应用程序来说通常不会成为瓶颈。但对于其他类型的自动生成文本文件（如*.csv，*xml或*.json）的应用程序来说，转换算法的效率很重要。特别是当这些文本文件将包含大量数字时，例如导出大型数据集时。
非常感谢您阅读到最后！欢迎在下面留下任何评论！
向David Ayrapetyan（https://www.linkedin.com/in/davidayrapetyan/）表示感谢，他仔细审查了本文的草稿，并提出了多个上下文增强和语法修正。
感谢Hayk Aslanyan（https://www.linkedin.com/in/haykaslanyan/），对本文的草稿进行了技术审查，并提出了其他改进意见。
插图设计由Asya Papyan完成：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] : “C++语言中的LR打印机实现” — https://github.com/tigranh/lr_printer