[Library Checker] Many A + B

スポンサーリンク

問題概要

問題文 →

$A, B$ が与えられるので $A+B$ を出力するというだけの問題です.

この問題はサイトの使い方を確認するための問題である一方で,入出力ライブラリの実行速度を比べるような目的でも利用されています.

競技プログラミングで,本問題の上位提出ほどの高速な入出力は,役に立つ(そのおかげで AC / TLE が変わる)場面はそこまで多くはないので,使用頻度に反して整備する優先度はそれほど高くないと思います.

ただし Library Checker を使っていろんなライブラリをチューニングしたいと考えているならば,あらゆる問題において上位提出との(入出力以外の)速度差が見えやすくなるため,ある程度入出力を高速にしておくメリットは大きいと思います.

私は,実行速度が上位の提出を見ながら入出力ライブラリを整備しました.こちらの Nyaan さんの提出 が理解しやすくパフォーマンスが良いと思ったので,この解法について解説します.

なお,ここで述べた入出力の実装に関する事柄は,C++ 以外の言語や,インタラクティブな入出力を求められる問題には当てはまらない場合があるので注意してください.

解法

Nyaan さんの提出 の解説です.

入力

適当なバッファを用意して,標準入力から,ある程度の文字数をまとめて受け取ってそこに入れます.そのあと,バッファを自分で走査しながら数値の切れ目などを探して,自分で値を計算します.

標準入力からの受け取りには例えば std::fread が使えるようです.1 問で受け取るべき入力がすべてバッファに収まるとは限らないため,走査している場所が受け取ったものの末尾に近づいたら続きを受け取ってバッファに配置しなおしています(if (pil + 32 > pir) load()).

値の計算は $10$ 進法文字列を整数型になおすような通常の実装で,理解しやすいと思います.

出力

適当なバッファを用意して,出力したい文字列をためておきます.バッファが埋まった時点およびプログラムの終了時(あるいは明示的に flush を呼んだとき)に flush() でこれらを標準出力に渡します.

int や long long などの整数型は内部では $2$ 進法によりビット列になおしたものを保持しているというのは有名だと思います.したがって,出力の際に $10$ 進法文字列に変換するという計算が行われます.

$10$ で割って商と余りに分解することを繰り返すと,桁数に等しい回数の除算などが必要になって,ここに高速化ポイントがあります.例えば $10$ 進法 $16$ 桁の整数は,$10^4$ 進法 $4$ 桁の整数のように扱うと,数回の除算で $4$ 桁ごとの整数に分解できます.$10^4$ 以下の整数すべてに対して $10$ 進法表記文字列を前計算しておき(struct pre),その結果を memcpy して繋ぎ合わせることで,もとの整数に対応する文字列をバッファに書き込むことができます.

「プログラムの終了時に flush する」についてはこの提出では,struct Dummy 内の at_exit でその指定をしています.他に,関数を destructor 属性で定義する gcc 拡張 を用いてこれを実現する提出もあり,私も採用しました(454 行目,どの提出を見て学んだのかを忘れてしまった).

その他のコメント

std::cin, std::cout を用いる場合

単に cin で受け取って cout で出力する,という感じのコードを実装してみます.

かなり普通の書き方にも思えますが,気をつけないと非常に遅いです.ここまで遅いと入出力が原因で TLE してしまう場面も結構出てきてしまうかもしれません.

次のような方法で実用上ほぼ問題にならない程度に高速になることが知られていて,上級者でも標準的な実装のひとつだと思います.

  • 解答例(371ms)
    • 改行に endl を使わず改行コード \n を用いる.
    • ios_base::sync_with_stdio(false); と書く.
    • cin.tie(nullptr); と書く.

私もこれらの違いについて詳しいわけではないですが,基本的には,出力が必要以上に flush されてしまうことなどを防いでいるはずです.例えばえびちゃんによる記事を参考にしてください.

Library Checker 最速実装について

やはり,入出力はバッファに溜めておくというのは共通しています.

標準入力をバッファに持ってくる部分は,mmap (sys/mman.h )を利用しているようです.なお,mmap を用いた入力を写経して私も使ってみたことがあるのですが,codeforces でコンパイルエラーになったため私は採用を見送りました.

文字列と整数型のやり取りについて,かなり簡単な rd, wt が実装されていますが,この提出ではこれは高々一度しか呼ばれません(テストケース数の偶奇合わせ).

高速化のためにテストケースを 2 つずつまとめて扱っていて,simd 命令を使って高速化しています.整数を表す文字列(1文字あたり 8bit)をそのままビット列として見て足し算を実装しているようです.全ての桁から 48=char(‘0’) を引いて,足し算したあと繰り上がりを検出し…という実装をしているように見えます.

私の力量やモチベーションの関係でそれ以上詳しくは読んでいません.A + B 問題は高速に解いていますが,入出力ライブラリ整備という目的で参考にしにくい実装かもしれません(他の問題でも似たことをやっているのを見かけたので,汎用的に使える部分を抽出することはできるのだと思います).

      タイトルとURLをコピーしました