c# - 在一个巨大的字符串中替换多个字符串的最快方法

Question

我正在寻找替换大 (~1mb) 字符串的多个 (~500) 子字符串的最快方法。无论我尝试过什么，String.Replace 似乎都是最快的方法。

我只关心最快的方法。不是代码可读性、可维护性等。我不关心我是否需要使用不安全代码或预处理原始字符串。

每次替换迭代都会用其他字符串替换字符串中的 ABC(每次替换迭代都不同)。要替换的字符串将始终相同 - ABC 将始终是 ABC。从来没有ABD。因此，如果有 400.000 几千次替换迭代。相同的字符串 - ABC - 每次都会被其他(不同的)字符串替换。

我可以控制 ABC 是什么。只要不影响结果，我可以让它超短或超长。显然 ABC 不能是 hello 因为 hello 将作为一个词存在于大多数输入字符串中。

示例输入:ABCDABCABCDABCABCDABCABCDABCD

示例替换字符串:BC

替换为字符串的示例:AA、BB、CC、DD、EE(5 次迭代)

示例输出:

AAADAAAAAADAAAAAADAAAAAADAAAD
ABBDABBABBDABBABBDABBABBDABBD
ACCDACCACCDACCACCDACCACCDACCD
ADDDADDADDDADDADDDADDADDDADDD
AEEDAEEAEEDAEEAEEDAEEAEEDAEED

平均情况:输入字符串为 100-200kb，替换迭代次数为 40.000。最坏情况:输入字符串为 1-2mb，替换迭代次数为 400.000。

我可以做任何事。并行做，做不安全等等，我怎么做都无所谓。重要的是它需要尽可能快。

Answer 1

使用 unsafe 并编译为 x64

结果:

Implementation       | Exec   | GC
#1 Simple            | 4706ms |  0ms
#2 Simple parallel   | 2265ms |  0ms
#3 ParallelSubstring |  800ms | 21ms
#4 Fredou unsafe     |  432ms | 15ms

获取 Erti-Chris Eelmaa 的代码并以此替换我之前的代码。

我不认为我会再做一次迭代，但我确实从不安全中学到了一些东西，这是一件好事:-)

    private unsafe static void FredouImplementation(string input, int inputLength, string replace, string[] replaceBy)
    {
        var indexes = new List<int>();

        //input = "ABCDABCABCDABCABCDABCABCDABCD";
        //inputLength = input.Length;
        //replaceBy = new string[] { "AA", "BB", "CC", "DD", "EE" };

        //my own string.indexof to save a few ms
        int len = inputLength;

        fixed (char* i = input, r = replace)
        {
            int replaceValAsInt = *((int*)r);

            while (--len > -1)
            {
                if (replaceValAsInt == *((int*)&i[len]))
                {
                    indexes.Add(len--);
                }
            }                
        }

        var idx = indexes.ToArray();
        len = indexes.Count;

        Parallel.For(0, replaceBy.Length, l =>
            Process(input, inputLength, replaceBy[l], idx, len)
        );
    }

    private unsafe static void Process(string input, int len, string replaceBy, int[] idx, int idxLen)
    {
        var output = new char[len];

        fixed (char* o = output, i = input, r = replaceBy)
        {
            int replaceByValAsInt = *((int*)r);

            //direct copy, simulate string.copy
            while (--len > -1)
            {
                o[len] = i[len];
            }

            while (--idxLen > -1)
            {
                ((int*)&o[idx[idxLen]])[0] = replaceByValAsInt;
            }
        }

        //Console.WriteLine(output);
    }