「34%高速な整数から文字列への変換アルゴリズム」
『整数から文字列への変換アルゴリズムの高速化に成功！』
整数を十分に高速に印刷していますか？
1. 導入
コンピュータプログラミングにおいて、指定された整数を文字列に変換することは一般的な操作です。これは、例えば整数を画面に印刷したり、*.xml、*.json、*.csv、*.txtのようなテキストファイルに印刷する前に行われるべきです。
整数（および他のすべてのもの）は、コンピュータのメモリにバイナリ形式で格納されることはよく知られています。つまり、0と1の連続したシーケンスとして表現されます。例えば:
- 数字12は「1100」としてメモリに表現されます。
- そして数字29は「11101」として表現されます。
これが、人間が読みやすい10進数形式に変換する必要がある理由です。
この記事では、以下のことについて説明します:
- この変換に使用される標準的なアルゴリズムの概要を作成すること。
- 既存の最適化を見てみること。
- 私のアルゴリズムを提案すること。
- 実験的な比較を行うこと。
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桁の数字に固定されているため、直接印刷に送ることができます。そして、10での割り算の余りは常に1桁の整数です。
また、このアルゴリズムでは、Nの桁を逆の順序で報告していることにも注意してください（ここでは数字のシーケンスが「7」「6」「1」「2」となっていますが、代わりに「2」「1」「6」「7」となる必要があります）。そのため、最後に生成されたシーケンスを逆にする必要があります。
まとめると、このアルゴリズムの疑似コードは以下のようになります：
var result[0 .. 25] : Charactersの配列 // 最大25文字を想定しています
// 手続きは印刷する整数'N'を取り、その10進数の文字を'result'配列に埋めます。
procedure 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行のコードで簡単に実装できます。ただし、そのボトルネックは、Nの10進表記のそれぞれの桁に対して整数の割り算と剰余の計算という比較的高価な操作を使用していることです。整数の割り算と剰余の計算は、加算、減算、さらには乗算と比較して平均で4〜5倍の時間がかかることがよく知られています。以下に、これらの算術演算の時間ベンチマークを観察できます：
これらの実験は、以下のシステムでGoogle Benchmarkを使用して行われました：
CPU: Intel Core i7–11800H @ 2.30GHz
RAM: 16.0 GB
OS: Windows 11 Home, 64-bit
コンパイラ: MSVC 2022 ( /O2 /Ob2 /MD /GR /Gd )
整数の印刷のためのより速い方法が存在するかどうか、見てみましょう…
3. 既存の最適化
最適化 1
このアルゴリズムの一般的な最適化として、生成された数字のシーケンスを逆にする最後の手順を省くことが挙げられます。このトリックは、例えば [1] でうまく説明されています。この最適化により、適切な順序でバッファに数字を直接書き込むことができます。また、アルゴリズム自体が与えられた整数Nの桁を右から左に報告しているため、バッファにも右から左に書き込むことになります。
この最適化を組み込んだ疑似コードは以下のようになります：
var result[0 .. 25] : 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 ⌋ // 最後の桁を取り出す
iを返す // 変換された整数が始まる位置
注意：このストーリー内のすべての疑似コードでは、数字 “0” の印刷の場合を処理していません。すべての書かれたアルゴリズムによれば、”0″は一切の数字がないシーケンスとなるため、ほとんどの印刷アルゴリズムでは「0」の印刷は別のブランチで行われます。ここでは、コンパクトさのためにそのブランチをスキップします。
この最適化のもう一つの小さな利点は、変換ごとに終端のヌル文字を書く必要がないことです。代わりに、バッファの最後の位置にのみ一度だけ書くことができます。Nの最後の桁の物理的な位置が事前に固定されているため、常にバッファの最後から2番目の位置になります。
この最適化の欠点は、最初の文字の位置が可変になることです。それは整数Nの桁数に依存するようになります。
ただし、実際には、これは問題になりません。変換された整数はしばしばすぐにテキストファイルや画面に送信されるため、長時間メモリに残ることはありません。そのような目的のために、変換された桁がメモリの特定の位置から書き込まれる必要はありません。
最適化2
次の最適化は、整数の除算と剰余計算操作を使用して2桁のNを一度に取得することです。このトリックは[1]と[2]でもよく文書化されています。そのため、繰り返し計算する代わりに
「digit := N mod 10」の後に「N := N / 10」という計算を行う代わりに、
以下の計算を行います：
「digits := N mod 100」と次に「N := N / 100」という計算を行います。
これにより、Nの最後の2桁を得て、それらを両方切り捨てます。
なお、取得した2桁を最終的に効率的に印刷するためには、ここで0から99までのインデックスを持つ長さ100の配列を準備しておく必要があります。値は「00」、「01」、「02」、…、「98」、「99」という文字ペアになります。
この最適化では、整数の除算と剰余計算の回数が約2倍に減少します。
最後に、この部分を完了するにあたって、説明した両方の最適化が有効になっても、与えられた整数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の累乗を計算する方が整数の除算や剰余の計算よりも時間がかかると主張するかもしれません。それはまったく正しいのですが、1つの詳細を除いて: 必要なすべての10の累乗は事前に計算しておくことができ、プログラム全体の実行中にそれらを使用することができます。 32ビット整数の場合、10の異なる累乗はわずか10個であり、64ビット整数では20個の累乗があります。 したがって、それらをすべてメモリに事前に計算して保持しておくことは問題ありません。
全体的には何を持っていますか？私のアルゴリズムでは、Nの1桁を印刷するために以下のように行います:
1つの整数の割り算、1つの乗算、1つの減算。
対照的に、通常のアルゴリズムでは以下のように行います:
1つの剰余の計算、1つの整数の割り算。
次のセクションでは、乗算と減算の組み合わせの方が剰余の計算よりもCPU時間が少ないことを示すので、私の手法の方が実際には優れていることを見ていきます。これらの算術演算の時間消費の実験的比較は第2章で紹介されています。
私のアルゴリズムの主要部分の疑似コードは次のようになります:
var powers_of_10[0 .. 10] : Integersの配列 = { 1, 10, 100, 1'000, ..., 100'000'000, 1'000'000'000 } // 印刷時に使用される事前計算済みの10のべき乗var result[0 .. 25] : 文字の配列 // 最大25文字だと仮定// プロシージャは印刷する整数'N'を受け取り、その// 10進数の数字を'result'配列に埋め込む.procedure print( N: 整数 ) 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' // 終端の「null」文字を追加私のアルゴリズムはNの数字を左から右に印刷するため、「左から右に印刷するプリンター」または単純に「LRプリンター」と呼ぶことにします。
残っているのは、Nの10進数の桁数Lを効率的に見つけることです。幸運なことに、10のべき乗の事前計算済み配列もここで役立ちます。小さいべき乗から大きいべき乗まで、その配列を反復処理し、Nよりも大きい10^Lを見つけるまで続けます。この場合、指数LはNの桁数を表します。
たとえば、「N = 23’504」の桁数を求める場合は、以下のようになります:
この関数の疑似コードは次のようになります:
// 関数は整数'N'を取り、その桁数を返します.function calculate_digits_count( N: 整数 ) : 整数 // 最大桁数の数値の場合をチェック 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のみではありません）。その場合、事前計算済みの10の冪乗を新しい基数の事前計算済みの冪乗で置き換えるだけです。
C++言語での「LRプリンター」の実装はGitHub [3] で入手できます。
「LRプリンター」の最適化2
私のアルゴリズムは、「既存の最適化」セクションで説明されている第2の最適化を使用して改善することができます。この最適化は[1]および[2]で文書化されています。これを行うと、与えられた数をステップごとではなく、1つのステップで2桁ずつ表示することができます。
例えば、数値「N = 4’610’937」での動作を見てみましょう。ここでL=7であり、今回はNを10^(L-2)=10’000で割ります：
この最適化を有効にすると、入力数値の2桁ごとに以下の操作を行います：
1つの整数除算、1つの乗算、および1つの減算。
ここでも、桁はその自然な順序で取得されます（左から右へ）。そのため、最後にそれらを逆にする必要はありません。
第2の最適化が有効な「LRプリンター」の実装はGitHub [3]で見つけることができます。
5. 既存のアルゴリズムとの実験的比較
この種の作業では、実験的な比較が重要です。この章では、次の整数印刷アルゴリズムの比較結果を示します：
- 最初の最適化を施した標準アルゴリズム（「Std」とラベル付け）、
- 私のアルゴリズム「LRプリンター」（「LR」とラベル付け）、
- 第2の最適化も施した標準アルゴリズム（「Std [2-dig]」とラベル付け）、および
- 第2の最適化を施した「LRプリンター」（「LR [2-dig]」とラベル付け）。
これらのアルゴリズムのそれぞれは、入力数値の桁数が異なる32ビットおよび64ビットの整数に対してテストされます。
10進数での数値の印刷
数値の印刷時の基数が10の場合の結果は以下のとおりです：
32ビット整数の場合、「LRプリンター」と標準のプリンターを比較すると、約30-38%の利益が得られます。2番目の最適化（1ステップで2桁を印刷）を使用した場合の利益は低くなります – 13-28%。これは完全に予想された結果であり、その場合全体としては2または4ステップしか実行されないためです。
64ビット整数の印刷に関しては、私のアルゴリズムのパフォーマンスはさらに優れています。「LRプリンター」は標準アルゴリズムよりも約40-50%高速です。そして、両方に対して2番目の最適化が有効になっている場合、「LRプリンター」は47-58%高速です。
このストーリーのタイトルのパーセンテージは、最も一般的な場合に対応するように選ばれました：ベースが10であり、32ビット整数で多くの桁数があるものとして、パフォーマンスの利益を「LRプリンター」が標準アルゴリズムに対して30-38%得た場合、平均値は約34%です。
ベース3での数値の印刷
また、別のベースで整数を印刷した場合に、結果が大きく変わるかどうかも見てみましょう。ベース=3での印刷を観察します：
ここで見るように、32ビット整数の場合、「LRプリンター」のパフォーマンスの利益は標準アルゴリズムに対して約25-33%であり、これは使用される算術演算のパフォーマンスの違いに一般的に対応しています。
64ビット整数の場合、「LRプリンター」のパフォーマンスの利益は、短い数字（8桁）では約50-55%、長い数字（36桁）では約27-30%です。
全体的な考察
一般的に、整数が印刷される基数は相対的なパフォーマンスの利益にほとんど影響しません。なぜなら、印刷中に実行する操作の回数は、入力数値の桁数に比例し、それらの桁が持つ可能性のある値の数とは関係ないからです。
通常、桁数が多いほど、「LRプリンター」（または「LRプリンター[2桁]」のバリエーション）が標準の印刷アルゴリズム（または「2桁」のバリエーション）よりも優れたパフォーマンスを発揮することがほとんどです。これは、より多くの桁があるほど、ループ外の命令（他の関数を呼び出したり、ヌル終端文字を配置したりすること）の影響が少なくなるためです。
そして、全体的に、64ビット整数を印刷する場合、「LRプリンター」と「LRプリンター[2桁]」のバリエーションの両方にとっての結果はより印象的です。
個人的には、これらの結果は非常に注目に値すると思います。
6. 結論
私たちは整数を文字列に変換する新しいアルゴリズムを発表し、「LRプリンター」と呼びました。最適化された標準の変換アルゴリズムと比較して、32ビット整数の場合は25-38%高速で実行され、64ビット整数の場合は40-58%高速です。私たちのアルゴリズムは任意の基数で動作することができます（普通の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++のための3つの最適化のヒント” — https://www.facebook.com/notes/10158791579037200/
[3] : “C++言語でのLRプリンターの実装” — https://github.com/tigranh/lr_printer
We will continue to update VoAGI; if you have any questions or suggestions, please contact us!
Was this article helpful?
93 out of 132 found this helpful
Related articles
