C#で行・列インデックスから文字列内のインデックスへの高速変換

Question

こんにちは。
文字列内で行・列を表すインデックスを文字列の先頭を0として始まるインデックスへ高速に変換したいのですが、自分ではうまく実装できないので、　より良い方法を教えていただきたいです。
インデックスが大きくなっても処理速度が極端に遅くなったりすることがないような実装はありますか？

IndexOfを使って実装したコード(インデックスが大きくなると遅くなる):

int GetCharIndex( string text, int line, int col )
{
    string code = "\r\n";
    int inLine = line;

    int begin = 0;
    for (int i = 0; true; i++ )
    {
        if (line == 0)
        {
            if (inLine != 0)
                begin += code.Length - 1;
            break;
        }
        begin = text.IndexOf(code, begin);
        if (begin == -1)
        {
            return -1;
        }
        line--;
        begin++;
    }

    return begin + col;
}

Comments

[Zuishin]

実装できなかったコードだけ乗せられても。
それで説明は終わりですか？

[Nauclhlt]

自分の実装が低速なので改善点を質問しています。
説明が足りないのなら何が足りないのか明示していただかないとわからないのですが。

[nonoshu]

質問文の内容が理解できませんでした。
・具体的な引数データを示してみる
　text="aaaa\r\nbbbb\r\ncccc\r\n....."
line=1
col=1
・「高速に変換」とありますが、
　提示した引数の場合に何ミリ秒以内で結果が返ってくることを期待しているのか

など質問者さんの期待する答えをもう少し具体的に提示すると回答が集まりやすくなるかと思いました。

[Zuishin]

改良すべき点はありますが、線形探索なので、少々いじってもそこまで劇的に速くはならないでしょう。
バグがあるかどうかまでは見ていません。
テキストが固定ならあらかじめ各行の先頭をインデックス付けするなど検索しやすい前準備をしておくのが良いかもしれません。

[fana]

そもそもこれ，どう使う想定なんだろう？

私は頭悪いので，text の中身が完全に不明な状態下においてこれを真っ当に使用できる状況が想像つかない．
例えば， line 行目の文字列の長さよりも col の値が大きいかもしれないわけで，（しかもそうだったということは結果からは全くわからないのだけど）得られた値をまともに使えるのだろうか？
（実際には return の直前あたりで col の妥当性をチェックする処理が入る？）

Answer 1

更新 １万字超えたため元回答と置き換えました

わかりました。StringComparisonの問題でした（基本のはずなのですが失念しておりました^^;
StringComparison 列挙型 (System) | Microsoft Learn
.NET での文字列の比較に関するベスト プラクティス | Microsoft Learn

StringComparison.Ordinalならば、今より100～1000倍は速くなりました。
それでもReadOnlySpanのほうが速いことは確かなので、ROSを使えるなら使ったほうがいいでしょう^^

Method	N	Mean	Error	StdDev	Ratio
Original	100	693.671 us	13.8602 us	12.2867 us	1.000
OriginalOrdinal	100	6.695 us	0.0434 us	0.0385 us	0.010
ROS	100	5.053 us	0.0245 us	0.0217 us	0.007
Original	500	20,997.678 us	440.4404 us	1,298.6484 us	1.000
OriginalOrdinal	500	47.985 us	0.9310 us	0.8253 us	0.002
ROS	500	39.873 us	0.2115 us	0.1979 us	0.002
Original	1000	139,483.870 us	1,282.5145 us	1,136.9157 us	1.000
OriginalOrdinal	1000	131.865 us	1.2881 us	1.0757 us	0.001
ROS	1000	117.974 us	2.3328 us	2.3957 us	0.001

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;


BenchmarkRunner.Run(typeof(Program).Assembly);


[ReturnValueValidator(true)]
public class CharIndex
{
    [Params(100, 500, 1000)]
    public int N;
    private string data;

    [GlobalSetup]
    public void GlobalSetup()
        => data = string.Join("\r\n", Enumerable.Range(0, N).Select(x => new string('a', x)));

    [Benchmark(Baseline = true)]
    public int Original() => GetCharIndex(data, N - 1, N - 1);

    [Benchmark]
    public int OriginalOrdinal() => GetCharIndex2(data, N - 1, N - 1);

    [Benchmark]
    public int ROS() => GetCharIndex3(data, N - 1, N - 1);

    int GetCharIndex(string text, int line, int col)
    {
        string code = "\r\n";
        int inLine = line;

        int begin = 0;
        for (int i = 0; true; i++)
        {
            if (line == 0)
            {
                if (inLine != 0)
                    begin += code.Length - 1;
                break;
            }
            begin = text.IndexOf(code, begin);
            if (begin == -1)
            {
                return -1;
            }
            line--;
            begin++;
        }

        return begin + col;
    }

    int GetCharIndex2(string text, int line, int col)
    {
        string code = "\r\n";
        int inLine = line;

        int begin = 0;
        for (int i = 0; true; i++)
        {
            if (line == 0)
            {
                if (inLine != 0)
                    begin += code.Length - 1;
                break;
            }
            begin = text.IndexOf(code, begin, StringComparison.Ordinal);
            if (begin == -1)
            {
                return -1;
            }
            line--;
            begin++;
        }

        return begin + col;
    }

    int GetCharIndex3(ReadOnlySpan<char> text, int line, int col)
    {
        var code = "\r\n".AsSpan();
        var inLine = line;

        var begin = 0;
        while (true)
        {
            if (line == 0)
            {
                if (inLine != 0) begin += code.Length - 1;
                break;
            }

            begin = text.IndexOf(code, begin);
            if (begin == -1) return -1;

            line--;
            begin++;
        }

        return begin + col;
    }
}

static class Ex
{
    // [Add Span / ReadOnlySpan IndexOf extensions taking in a start index and a count · Issue #26982 · dotnet/runtime](https://github.com/dotnet/runtime/issues/26982)
    public static int IndexOf(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, int startIndex)
    {
        var indexInSlice = span.Slice(startIndex).IndexOf(value);
        return indexInSlice == -1 ? -1 : startIndex + indexInSlice;
    }
}

// * Summary *

BenchmarkDotNet=v0.13.2, OS=Windows 10 (10.0.19043.2006/21H1/May2021Update)
Intel Core i7 CPU 920 2.67GHz (Nehalem), 1 CPU, 8 logical and 4 physical cores
.NET SDK=7.0.100-rc.1.22431.12
  [Host]     : .NET 6.0.9 (6.0.922.41905), X64 RyuJIT SSE4.2
  DefaultJob : .NET 6.0.9 (6.0.922.41905), X64 RyuJIT SSE4.2


|          Method |    N |           Mean |         Error |        StdDev | Ratio |
|---------------- |----- |---------------:|--------------:|--------------:|------:|
|        Original |  100 |     693.671 us |    13.8602 us |    12.2867 us | 1.000 |
| OriginalOrdinal |  100 |       6.695 us |     0.0434 us |     0.0385 us | 0.010 |
|             ROS |  100 |       5.053 us |     0.0245 us |     0.0217 us | 0.007 |
|                 |      |                |               |               |       |
|        Original |  500 |  20,997.678 us |   440.4404 us | 1,298.6484 us | 1.000 |
| OriginalOrdinal |  500 |      47.985 us |     0.9310 us |     0.8253 us | 0.002 |
|             ROS |  500 |      39.873 us |     0.2115 us |     0.1979 us | 0.002 |
|                 |      |                |               |               |       |
|        Original | 1000 | 139,483.870 us | 1,282.5145 us | 1,136.9157 us | 1.000 |
| OriginalOrdinal | 1000 |     131.865 us |     1.2881 us |     1.0757 us | 0.001 |
|             ROS | 1000 |     117.974 us |     2.3328 us |     2.3957 us | 0.001 |

// * Warnings *
MultimodalDistribution
  CharIndex.Original: Default -> It seems that the distribution is bimodal (mValue = 3.4)

// * Hints *
Outliers
  CharIndex.Original: Default        -> 1 outlier  was  removed (750.32 us)
  CharIndex.OriginalOrdinal: Default -> 1 outlier  was  removed (7.19 us)
  CharIndex.ROS: Default             -> 1 outlier  was  removed (5.33 us)
  CharIndex.OriginalOrdinal: Default -> 1 outlier  was  removed (51.15 us)
  CharIndex.Original: Default        -> 1 outlier  was  removed (143.96 ms)
  CharIndex.OriginalOrdinal: Default -> 2 outliers were removed (137.41 us, 139.30 us)
  CharIndex.ROS: Default             -> 1 outlier  was  removed (127.26 us)

---

インデックスが大きくなっても処理速度が極端に遅くなったりすることがないような実装はありますか？

想像よりもかなり遅いですね。。。（1万行にしたら全然返ってこなくなりました^^;

行数もわからずノーヒントだったら、頭から探していくしかないような。

Replace("\r\n", "\n")して行数を求めて後ろ側だったら、LastIndexOfするとか？
置換や後ろから探すオーバーヘッドをペイできるのかどうか...
Charになるのはメリットかも？（IndexOf(String, Int32)よりは、IndexOf(Char, Int32)のほうが速そうな気はする）

Comments

[Zuishin]

string.IndexOf は内部で Span<T> を使ってるだろうから速くなるはずがないと高をくくっていましたが、この結果はすごいですね。
なぜ数百分の一になるのか信じ難いです。