【C#】競プロ等で簡単・高速に入力を受け取れるライブラリを作成した話

この記事はC#アドベントカレンダー24日目の記事です

概要

• atcoderの問題では入力がスペースで区切られることが多いよ
• C#だとこういう入力をサクっと受け取るのが案外できなかった
• 簡単に使えて従来より高速なライブラリを作ったよ

コード全文とドキュメントは以下のレポジトリで取得できます。
記事では経緯や実装面の話をするつもりですので、とにかく使いたい方はリポジトリの方を参照ください。

利用例

以下のように柔軟かつ直感的に入力が受け取れます。
1個、複数個、可変個のすべてに対応し、事実上ほぼすべての基本型に対応。好きな変数名を付けて読みやすいコードにできますし、foreach や Linq なども直接サポートされます。

// 使用例
double x = ReadLine<double>();
var (m, n) = ReadLine<int>();
var (a, b, c, d, e) = ReadLine<int>();
var (s, t, u) = ReadLine(); // string型
foreach (var item in ReadLine<int>())
{
    // do something
}
var array = ReadLine<decimal>().ToArray();
var max = ReadLine<long>().Select(x => x * 2).Where(x => x != 0).Max();

問題提起

atcoderなどの競技プログラミングシーンではスペース区切りの入力が与えられる問題が多く存在します。
例えば、現時点での最新のA問題、ABC334-A は

100 300

のように、2つの整数が与えられ、その大小に応じた文字列を出力する問題です。

例えばC++では

int a , b;
cin >> a >> b;

といったふうにシンプルに入力を受け取ることができます。

が、C#では標準でこの用途に特化した関数はなく、多くのC#erが

string[] line = Console.ReadLine().Trim().Split(' ');
var a = int.Parse(line[0]);
var b = int.Parse(line[1]);

と、変数の数だけ冗長なコードを書くか、さもなくば

int[] input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

と省略するかわりに、 input[0] や input[1] が頻出する読みにくさを受け入れることを選択しています。

従来の解決策

以前、具体的にはコンパイラの選択肢がMonoしかなかった時代には自分もこれを受け入れていました。
しかし、コンパイラとして .net core が選択できるようになったときから、ValueTuple を返すメソッドを用意しておくという方法を使い始めました。

具体的には、入力の個数のパターン数だけ以下のようなメソッドを定義します。

public static ValueTuple<T, T> ReadInput2<T>(Func<string, T> converter = null)
{
    if (converter is null) { converter = GetConverter<T>(); }
    var input = Console.ReadLine().Split(separator);
    return (converter.Invoke(input[0]), converter.Invoke(input[1]));
}

欲しい型への変換部分は以下のように地獄の条件分岐で適切な Func を返すことで実装します。
こうすることで記述の冗長さを多少マシにすることができます。

private static Func<string, T> GetConverterOrDefault<T>()
{
    Type type = typeof(T);
    Func<string, T> conveter;

    // 出現頻度が高そうなものを上
    if (type == typeof(int))
    {
        conveter = str => (T)(object)int.Parse(str);
    }
    else if (type == typeof(long))
    {
        conveter = str => (T)(object)long.Parse(str);
    }
    else if (type == typeof(double))
    (以下略)

using static でこれらを定義したライブラリクラスへ参照を通しておけば

var (a,b) = ReadInput2<int>();

と書け、利用側はかなりすっきりとしました。
実際には、ReadInput2 ~ ReadInput7 と、可変個を配列にする ReadArray を用意し、型引数としてすべてのプリミティブのパターンを記述していました。

新しいライブラリを書こう

さて、今ではatcoderでのコンパイラとして .net7 を使用できますし、自身もC#の仕様に詳しくなりました。改めてこの秘伝のたれライブラリを見返してみると結構気になることがあるので、現代的に再考して再構築してみます。

まず最初に解決するのが、地獄のような条件分岐をやめることです。Generic Math が実装された今、 IParsable などのインターフェイスによる、オブジェクト指向的で行儀がいい方法が使用できます。

次に、入力個数に応じて異なる名前のメソッドを使う必要をなくします。言語仕様の重箱の隅をつついていくことで、すべて単一のメソッド ReadLine で対応させます。

最後に、Split 関数が string の配列を返すことに伴う、パフォーマンスとアロケーションのオーバーヘッドも解消を試みます。

IParsable インターフェイス

従来、インターフェイスで抽象化できるのは、仮想関数にできるインスタンスメソッドのみでした。しかし、.NET7 から静的関数もインターフェイスで抽象化できる機能が実装されており、これは特に数値・数学関数の抽象化に貢献するため、Generic Math などと呼ばれています。

IParsable<T> インターフェイスは、ジェネリック型引数の T 型を返す静的メソッド、Parse(string) を実装することを約束します。実際、int や double などの、多くの数値型がこのインターフェイスを実装しています。

public interface IParsable<TSelf> where TSelf : IParsable<TSelf>?
{
    static abstract TSelf Parse(string s, IFormatProvider? provider);
    
    static abstract bool TryParse([NotNullWhen(true)] string? s, IFormatProvider? provider, [MaybeNullWhen(false)] out TSelf result);
}

また、類似するインターフェイスとして、ISpanParsable<T> があり、これは string のかわりに、ReadOnlySpan<char> を要求するものです。本題から外れるため解説は譲りますが、Span は先頭に型情報・長さのヘッダーが付いている必要性がないため。部分列に対してより柔軟に対応することができます。

今回はこちらの、ISpanParsable<T> インターフェイスにより文字列からの変換を共通化します。その恩恵は後ほど明らかにします。

分解パターン

タプル(ValueTuple)を受け取る場合、複数個の入力に名前を付けて

var (a,b) = {タプル}

と構文上記述することができ、従来はこの仕様を活用していました。しかし、実際にはこの仕様はタプルのみに与えられた特権ではありません。

C# の言語仕様や構文のうちある程度はパターンベースとなっています。パターンとは、特定の型やインターフェースの実装を要求するのではなく、指定の名前・シグネチャのメソッドを実装することだけを要求するものです。

今回活用する分解構文もパターンベースで、Deconstruct という名前で、分解結果を out パラメータとして受け取る(戻り値は void であることに注意！)メソッドを定義すればなんでも分解できます。

public void Deconstruct(out TResult val1, out TResult val2)
{
    val1 = ReadNextValue();
    val2 = ReadNextValue();
}

メソッド名が同じで戻り値の型が異なる、というメソッドのオーバーロードを作成ことはできないため、要素数の異なるタプルを返す共通メソッドを定義するのは難しいわけですが、要素数の異なる分解パターンをすべて実装する型を作成することはできます。

今回作成したライブラリの ReadLine 関数は、InputToken という構造体を返すようになっています。この構造体が分解パターンを満たすため、ValueTuple のように分解ができるというわけです。分解構文では、分解した結果に好きな名前をつけることができるため、空白区切りで定数個の入力が与えられる問題で可読性を落とさずに楽に入力を受け取れます。

// 使用例
var (m, n) = ReadLine<int>();

ValueTuple に囚われる代わりに、より根本的なパターンを実装することで簡潔な構文にできました。

Split のアロケーション回避

string の Split メソッドを呼ぶと、文字列の配列が返ります。つまり、特に要素数が多い場合には結構な量の無駄なヒープアロケーションが発生します。

分割した文字列自体はどうせすぐに不要になるわけですから、実際このアロケーション程度で困ることはないだろうとはいえ、やはり無駄はない方がいいといえます。

という発想で、Span を利用して部分文字列を取り扱うことでアロケーションを回避します。
Span 自体をフィールドに持ち、まだ読んでいない部分だけを保持するように Slice し続けていくとコード的には綺麗なのですが、ref struct の制約としてヒープに乗る可能性がある操作ができない、つまりインターフェースの実装ができず、Linq が素直に使えなくなるという課題があります。これが意外と不便だったので、逐次 Slice することにしました。ベンチマークを取りましたが、この変更によるパフォーマンス影響はほぼ無視できるレベルです。

例として、2 x 10^5 個の入力を受け取る場合だと(傾向をみるためにでかくしています)

と、速度は2倍に高速化され、アロケーションは1/3に削減されました。
(注: イテレータを実装するため、配列を作成するよりループを回すほうが速度やアロケーションが最適化されています)

その他ちょっとしたハック

暗黙的キャスト

入力が1件の場合もきれいに結果を受け取りたいため、暗黙的キャストでこのケースに対応しました。
var 型推論が使えないといった若干の不便はありますが

// 使用例
double x = ReadLine<double>();

と1件の場合も自然です。

文字列と非ジェネリック

string は IParsable を実装しないため、型引数として string を使用できません。
これへの解決策として、非ジェネリックなオーバーロードを作成し、この場合文字列が返るようになっています。

var (s, t, u) = ReadLine();

実装として、ReadLine の戻り値の実体である InputToken 構造体は InputToken<TResult, TImpl> とジェネリックになっており、TImpl 型引数で変換の実装を渡すようにしており、IParsable インターフェースに直接依存しないようにして回避しています。

検索

分割対象、今回であれば半角スペースを検索するような処理は、自分でループを回すより標準ライブラリの高度に最適化されたロジックを使用したほうが高速であることが知られています。

今回のライブラリでは一貫して標準ライブラリの機能やコピペコードで検索を行っています。

品質保証と単体テスト

というわけで、個人的には結構便利なものができたわけですが、実際これを使ってWAを出すと辛いですし、他の人に出させてしまうのはもっとつらいです。

対策として、結構しっかりと単体テストを作成してあります。実際、単体テスト記述中にコーナーケースでの非直感的動作を発見するなど、品質向上しています。

リポジトリの方ではCIで単体テストが回り、リグレッション対策もしています。

最後に

内容としてはかなり言語仕様ハックを重ねた一方、パフォーマンスと品質にもしっかり配慮し、割と実用性重視で設計しています。ぜひ使っていただけると喜びます。