C＃： ReadOnlySpan と Range を駆使して高速文字列分割 †

2020/01/18追記

より有益なベンチマークを C＃：続！ ReadOnlySpan と Range を駆使して高速文字列分割 にて行いました。

最近ようやく .NET Core 3.x やら C# 8 やらに触れているのですが、 Span<T>, ReadOnlySpan<T> いいですね！

• 参考: Span<T>構造体 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

ただ標準の拡張メソッドがやや物足りない気がしていて、必要に応じて自前で色々書いてみています。

その中で string.Split 的なものが欲しくなったわけですが、こいつらは配列にできないので string[] と同じノリで ReadOnlySpan<T>[] を返すわけにはいきません。

じゃあどうするかと考えた結果…

というわけでベンチマークテストしてみたコードをGitHubに置いてあります。

GitHub: ruche7/Test_SplitReadOnlySpan at boyaki_200110

• Visual Studio 2019
• .NET Core 3.1
• Nullable オプション有効
  • 参考: null 許容参照型 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

文字列の各行について行頭と行末の空白文字を取り除く処理を、 Program クラスの下記 4 メソッドでそれぞれ実装しています。

TrimLines_StringSplitJoin

1. string.Split で行単位に分割する。
2. string.Trim で空白文字を取り除く。
3. string.Join で連結する。

TrimLines_StringSplitBuild

1. string.Split で行単位に分割する。
2. string.AsSpan().Trim() で空白文字を取り除く。
3. StringBuilder クラスで連結する。

TrimLines_SpanRangesJoin

1. string.AsSpan() に対して自作拡張メソッドで各行範囲を表す List<Range> を取得する。
2. ReadOnlySpan<char>.Trim().ToString() で空白文字を取り除いて string[] に格納する。
3. string.Join で連結する。

TrimLines_SpanRangesBuild

1. string.AsSpan() に対して自作拡張メソッドで各行範囲を表す List<Range> を取得する。
2. ReadOnlySpan<char>.Trim で空白文字を取り除く。
3. StringBuilder クラスで連結する。

上記の自作拡張メソッドというのが冒頭のツイートでも書いた「ReadOnlySpan<T> をセパレータで分割した時の各分割範囲を表す List<Range> を返すメソッド」です。

public static class ReadOnlySpanExtensions
{
    /// <summary>
    /// スパンをセパレータ値で分割した時の各分割範囲を表す範囲リストを返す。
    /// </summary>
    /// <typeparam name="T">スパン要素型。</typeparam>
    /// <param name="source">対象スパン。</param>
    /// <param name="separator">セパレータ値。</param>
    /// <param name="removeEmptyEntries">
    /// 長さが 0 の分割範囲を除外するならば true 。
    /// </param>
    /// <returns>範囲リスト。</returns>
    public static List<Range> SplitToRanges<T>(
        this ReadOnlySpan<T> source,
        T separator,
        bool removeEmptyEntries = false)
        where T : IEquatable<T>;
}

GitHubには上記以外にも、セパレータとして ReadOnlySpan<T> を受け取るオーバーロードや、引数 count で最大分割数を指定できるオーバーロードもあります。

下記のように、拡張メソッド呼び出し対象の ReadOnlySpan<T> に対して span[range] の形で使うことで各分割範囲を取得できます。

public static void PrintLinesWithPrefix(string text, string prefix)
{
    var span = text.AsSpan();
    foreach (var range in span.SplitToRanges('\n'))
    {
        var line = span[range];
        Console.WriteLine(prefix + line.ToString());
    }
}

• 参考: インデックス/範囲処理 - C# によるプログラミング入門 | ++C++; // 未確認飛行 C

前述の 4 メソッドに対するベンチマークテスト結果は、私のPCだと下記のようになりました。 line は渡した文字列の行数、 loop はメソッド呼び出し回数です。

TrimLines_StringSplitJoin   : line = 1, loop = 2000000
  -> 502.222 ms
TrimLines_StringSplitBuild  : line = 1, loop = 2000000
  -> 369.481 ms
TrimLines_SpanRangesJoin    : line = 1, loop = 2000000
  -> 325.846 ms
TrimLines_SpanRangesBuild   : line = 1, loop = 2000000
  -> 300.272 ms

TrimLines_StringSplitJoin   : line = 10, loop = 200000
  -> 524.903 ms
TrimLines_StringSplitBuild  : line = 10, loop = 200000
  -> 385.824 ms
TrimLines_SpanRangesJoin    : line = 10, loop = 200000
  -> 262.607 ms
TrimLines_SpanRangesBuild   : line = 10, loop = 200000
  -> 225.597 ms

TrimLines_StringSplitJoin   : line = 100, loop = 20000
  -> 630.623 ms
TrimLines_StringSplitBuild  : line = 100, loop = 20000
  -> 510.686 ms
TrimLines_SpanRangesJoin    : line = 100, loop = 20000
  -> 400.512 ms
TrimLines_SpanRangesBuild   : line = 100, loop = 20000
  -> 288.856 ms

TrimLines_StringSplitJoin   : line = 1000, loop = 1000
  -> 1282.716 ms
TrimLines_StringSplitBuild  : line = 1000, loop = 1000
  -> 1008.059 ms
TrimLines_SpanRangesJoin    : line = 1000, loop = 1000
  -> 578.604 ms
TrimLines_SpanRangesBuild   : line = 1000, loop = 1000
  -> 560.633 ms

行数が 1 行でも 1000 行でも、自作拡張メソッドで List<Range> を取得して処理し、最後に StringBuilder クラスで連結するメソッドが最速という結果になりました。

StringBuilder クラスが最適かどうかは用途次第だと思いますが、少なくともこの自作拡張メソッドで string.Split より高速に分割文字列を得られそうです。

ただし、 Span<T> や ReadOnlySpan<T> は使える場所が限定されたりLINQとの相性が最悪だったりするので、あらゆる用途で string.Split を完全に置き換えられるわけではありません。

 

Now place: ぼやきごと/2020-01-10/C＃： ReadOnlySpan と Range を駆使して高速文字列分割

PukiWiki 1.5.0 Copyright © 2001-2006 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji.
Skin "GS2" is designed by yiza.
Powered by PHP 5.6.40. HTML convert time: 0.015 sec.