A+Bから始める異常高速化！競プロ入出力周りの高速化研究

発表のハイライト

• VRChatの「CS集会」でMizar_みざーさんが発表した、「A+Bから始める異常高速化」の内容をまとめます。
• Rustを使った、競プロにおける入出力周りの高速化について、実践的なコード例と共に解説していきます。
• 標準ライブラリや外部ライブラリを使った高速化、そしてさらに高速化を実現するためのテクニックを紹介します。

標準入出力の高速化

Mizar_みざーさんは、競技プログラミングにおいて入出力処理の高速化が重要であることを強調しました。 入出力処理がボトルネックとなり、実行時間が伸びてしまうケースは多く、特に、大量の入出力を行う問題では顕著に現れます。

では、どのような方法で入出力処理を高速化できるのでしょうか？

例題：Many A + B (128bit)

今回、Mizar_みざーさんは、Library Checkerの「Many A + B (128bit)」という問題を例に挙げ、解説を進めていきます。 この問題は、128bitの整数を表す文字列AとBが複数与えられ、それぞれのA+Bを計算し、結果を出力するというものです。

実行時間の改善

Mizar_みざーさんは、この問題を題材に、以下の5つのケースで実行時間を計測し、それぞれでどのような高速化が行われたのかを解説しています。

• CASE 1: println! の使用
• 標準ライブラリのprintln!を毎回呼び出す方法。
• 実行時間は537msと、非常に遅いです。
• これは、println!がOSに対して毎回出力を行うため、オーバーヘッドが大きいことが原因です。
• CASE 2: BufWriter の使用
• 標準ライブラリのBufWriterを用いる方法。
• 実行時間は222msに短縮され、大幅な改善が見られます。
• BufWriterは、出力バッファを用意することで、OSへの出力回数を減らし、実行時間の短縮を実現します。
• 多くのライブラリでは、BufWriterが内部で用いられています。
• CASE 3: 一括読み込み
• 標準入力を一度に全て読み込み、処理する方法。
• 実行時間は213msと、さらに高速化されます。
• 標準ライブラリでは、1行ずつ読み込む処理が行われますが、一度に全て読み込むことで、入出力回数を減らすことができます。
• しかし、入力データ量が大きすぎる場合は、メモリ不足が発生する可能性があるため、注意が必要です。
• CASE 4: mmap の使用
• mmapシステムコールを用いて、ファイルをメモリにマップする方法。
• 実行時間は191msとなり、CASE 3よりもさらに高速化されます。
• mmapは、ファイルの内容をメモリに直接読み込むことで、ファイルアクセスにかかる時間を削減します。
• 標準入出力とは異なる仕組みを用いるため、使用には注意が必要です。
• CASE 5: 入出力の改善
• 128bit整数の入出力処理を高速化。
• 実行時間は54msと、大幅な高速化を実現しています。
• 文字列→128bit整数への変換処理を工夫することで、高速化を実現しています。

文字列から128bit整数への変換

Mizar_みざーさんは、文字列から128bit整数への変換処理を高速化するためのテクニックとして、「分割統治法」を紹介しました。

分割統治法

分割統治法は、大きな問題を小さな問題に分割し、それぞれを解決することで、元の問題を解決するという手法です。 この手法を用いることで、文字列から128bit整数への変換処理を、より効率的に行うことができます。

エンディアンについて

Mizar_みざーさんは、エンディアンについて解説しました。 エンディアンとは、コンピュータが複数バイトのデータをメモリに格納する際のバイト順序のことです。 エンディアンには、リトルエンディアンとビッグエンディアンの2種類があります。 - リトルエンディアン: 最低位のバイトから格納する方式 - ビッグエンディアン: 最高位のバイトから格納する方式

Rustでは、リトルエンディアンが採用されています。

分割統治法の実装

Mizar_みざーさんは、分割統治法を用いた、文字列から128bit整数への変換処理の実装例を紹介しました。 この実装では、128bit整数を8bitずつ区切り、それぞれの8bitデータを10進数に変換し、10進数の値を組み合わせて128bit整数を作成しています。

速度の比較

Mizar_みざーさんは、分割統治法を用いた文字列から128bit整数への変換処理と、標準ライブラリのparse関数を使った場合の速度を比較しました。 その結果、分割統治法を用いた場合の方が、parse関数を使った場合よりも、2倍ほど高速であることが示されました。

SIMDレジスタを用いた高速化

分割統治法は、SIMDレジスタを用いることで、さらに高速化が期待できます。 SIMDレジスタは、複数のデータを同時に処理できるレジスタで、特定の演算を並列化することで、処理速度を大幅に向上させることができます。

除算の高速化

Mizar_みざーさんは、除算の高速化について、具体的な例を挙げて解説しました。 除算は、乗算や加算に比べて、処理時間がかかるため、高速化が難しいとされています。 しかし、特定の除数に対しては、特殊なアルゴリズムを用いることで、高速化を実現することができます。

特殊なアルゴリズム

Mizar_みざーさんは、除数3、7、1016、1032の除算について、高速化を実現するための特殊なアルゴリズムを紹介しました。 これらのアルゴリズムでは、シフト演算、加算、減算などの演算を組み合わせることで、除算を効率的に行っています。 SIMDレジスタを用いることで、さらに高速化が期待できます。

まとめ

Mizar_みざーさんの発表では、競技プログラミングにおいて、入出力処理や除算処理を高速化するための、様々なテクニックが紹介されました。 Rustは、標準ライブラリでも高速化が期待できますが、場合によっては、unsafeなコードを用いることで、さらなる高速化を実現することができます。 今回の発表で紹介された手法を実装することで、競技プログラミングでより良い成績を残せる可能性があるでしょう。

• Rustは標準で高速なわけではありません。
• Rustは安全に書くこともできますが、unsafeなコードを使うことで高速化できます。

• 不要不急の高速化は、時間と労力の無駄になる可能性があります。

• このブログ記事は、Mizar_みざーさんの発表を参考に作成されました。

• スライドのリンク: https://data.vrc-ta-hub.com/slide/manyaplusb.pdf

CS集会の他の発表もチェック！