在巨大的字符串中替换多个字符串的最快方法
我正在寻找替换大（~1mb）字符串的多个（~500）子串的最快方法。 无论我尝试过什么，似乎String.Replace是最快的方式。
我只关心最快的方式。 不是代码可读性，可维护性等。我不在乎我是否需要使用不安全的代码或预处理原始字符串。
编辑：评论后我添加了一些更多细节：
每个替换迭代将使用其他字符串替换字符串上的ABC（每个替换迭代不同）。 要替换的字符串总是相同的 – ABC将永远是ABC。 从不ABD。 因此，如果有400.000个替换迭代。 每次使用相同的字符串 – ABC – 将替换为其他（不同的）字符串。
我可以控制ABC是什么。 只要它不影响结果，我可以使它超短或超长。 显然，ABC不能打招呼，因为hello将在大多数输入字符串中作为单词存在。
输入示例： ABCDABCABCDABCABCDABCABCDABCD
示例替换为字符串： BC
示例替换为字符串： AA, BB, CC, DD, EE (5 iterations)
示例输出：
AAADAAAAAADAAAAAADAAAAAADAAAD ABBDABBABBDABBABBDABBABBDABBD ACCDACCACCDACCACCDACCACCDACCD ADDDADDADDDADDADDDADDADDDADDD AEEDAEEAEEDAEEAEEDAEEAEEDAEED
平均情况：输入字符串为100-200kb，替换迭代次数为40.000次。 最坏的情况：输入字符串是1-2mb，400,000次替换迭代。
我可以做任何事。 并行做，做不安全等等。无论我怎么做。 重要的是它需要尽可能快。
谢谢
由于我对这个问题有点兴趣，我制定了一些解决方案。 通过硬核优化，可以进一步降低成本。
要获取最新信息源： https ： //github.com/ChrisEelmaa/StackOverflow/blob/master/FastReplacer.cs
和输出
-------------------------------------------------- ----- | 实施| 平均值| 单独运行| | ---------------------- + --------- + ---------------- ---- | | 简单| 3485 | 9002,4497,443,0 | | SimpleParallel | 1298 | 3440,1606,146,0 | | ParallelSubstring | 470 | 1259,558,64,0 | | 弗雷杜不安全 356 | 953,431,41,0 | | 不安全+ unmanaged_mem | 92 | 229,114,18,8 | -------------------------------------------------- -----
你不可能在制作你自己的替换方法时击败.NET的人，它很可能已经使用不安全了。 如果你用C语言写完，我相信你可以把它降低两倍。
我的实现可能是错误的，但你可以得到一般的想法。
使用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(); //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); }
听起来你是字符串的标记？ 我会考虑生成一个缓冲区并为你的标记编制索引。 或者使用模板引擎
作为一个简单的例子，您可以使用代码生成来制作以下方法
public string Produce(string tokenValue){ var builder = new StringBuilder(); builder.Append("A"); builder.Append(tokenValue); builder.Append("D"); return builder.ToString(); }
如果您运行迭代足够多次，构建模板的时间将为自己付出代价。 然后，您也可以并行调用该方法，没有副作用。 还要看看你的琴弦实习
我对Fredou的代码做了一个变体，需要较少的比较，因为它适用于int*而不是char* 。 对于n长度的字符串，它仍然需要n次迭代，它只需要进行较少的比较。 如果字符串整齐地对齐2（因此要替换的字符串只能出现在索引0,2,4,6,8等），或者如果它与4对齐，则可以进行n/2次迭代（您可以’使用long* ）。 我不是很擅长这样的小摆弄，所以有人可能会在我的代码中找到一些可能更有效的明显缺陷。 我validation了我的变化结果与简单string.Replace的结果相同。
另外，我预计可以在500x string.Copy中获得一些收益。 string.Copy它，但尚未调查。
我的结果（Fredou II）：
IMPLEMENTATION | EXEC MS | GC MS #1 Simple | 6816 | 0 #2 Simple parallel | 4202 | 0 #3 ParallelSubstring | 27839 | 4 #4 Fredou I | 2103 | 106 #5 Fredou II | 1334 | 91
所以大约2/3的时间（x86，但x64大致相同）。
对于此代码：
private unsafe struct TwoCharStringChunk { public fixed char chars[2]; } private unsafe static void FredouImplementation_Variation1(string input, int inputLength, string replace, TwoCharStringChunk[] replaceBy) { var output = new string[replaceBy.Length]; for (var i = 0; i < replaceBy.Length; ++i) output[i] = string.Copy(input); var r = new TwoCharStringChunk(); r.chars[0] = replace[0]; r.chars[1] = replace[1]; _staticToReplace = r; Parallel.For(0, replaceBy.Length, l => Process_Variation1(output[l], input, inputLength, replaceBy[l])); } private static TwoCharStringChunk _staticToReplace ; private static unsafe void Process_Variation1(string output, string input, int len, TwoCharStringChunk replaceBy) { int n = 0; int m = len - 1; fixed (char* i = input, o = output, chars = _staticToReplace .chars) { var replaceValAsInt = *((int*)chars); var replaceByValAsInt = *((int*)replaceBy.chars); while (n < m) { var compareInput = *((int*)&i[n]); if (compareInput == replaceValAsInt) { ((int*)&o[n])[0] = replaceByValAsInt; n += 2; } else { ++n; } } } }
带有固定缓冲区的结构在这里并不是必需的，可以用一个简单的int字段替换，但是将char[2]扩展为char[3] ，这个代码也可以用于三个字母的字符串，如果它是一个int字段是不可能的。
它还需要对Program.cs进行一些更改，所以这里有完整的要点：
https://gist.github.com/JulianR/7763857
编辑：我不知道为什么我的ParallelSubstring这么慢。 我在发布模式下运行.NET 4，没有调试器，在x86或x64中运行。
由于您的输入字符串可能长达2Mb，我不预见任何内存分配问题。 您可以将所有内容加载到内存中并替换数据。
如果来自BC你总是需要替换AA ，一个String.Replace就可以了。 但是，如果您需要更多控制，可以使用Regex.Replace ：
var input = "ABCDABCABCDABCABCDABCABCDABCD"; var output = Regex.Replace(input, "BC", (match) => { // here you can add some juice, like counters, etc return "AA"; });
你可能不会比String.Replace更快地得到任何东西（除非你是原生的）因为iirc String.Replace是在CLR本身实现的，以获得最大的性能。 如果您希望获得100％的性能，可以通过C ++ / CLI方便地与本机ASM代码连接，然后从那里开始。
我的方法有点像模板 – 它接受输入字符串并拉出（移除）要替换的子串。 然后它将获取字符串的剩余部分（模板）并将它们与新的替换子字符串组合在一起。 这是在并行操作（模板+每个替换字符串）中完成的，它构建输出字符串。
我认为我上面解释的内容可能会更清晰。 这使用了上面的示例输入：
const char splitter = '\t'; // use a char that will not appear in your string string input = "ABCDABCABCDABCABCDABCABCDABCD"; string oldString = "BC"; string[] newStrings = { "AA", "BB", "CC", "DD", "EE" }; // In input, replace oldString with tabs, so that we can do String.Split later var inputTabbed = input.Replace(oldString, splitter.ToString()); // ABCDABCABCDABCABCDABCABCDABCD --> A\tDA\tA\tDA\tA\tDA\tA\tDA\tD var inputs = inputTabbed.Split(splitter); /* inputs (the template) now contains: [0] "A" [1] "DA" [2] "A" [3] "DA" [4] "A" [5] "DA" [6] "A" [7] "DA" [8] "D" */ // In parallel, build the output using the template (inputs) // and the replacement strings (newStrings) var outputs = new List(); Parallel.ForEach(newStrings, iteration => { var output = string.Join(iteration, inputs); // only lock the list operation lock (outputs) { outputs.Add(output); } }); foreach (var output in outputs) Console.WriteLine(output);
输出：
AAADAAAAAADAAAAAADAAAAAADAAAD ABBDABBABBDABBABBDABBABBDABBD ACCDACCACCDACCACCDACCACCDACCD ADDDADDADDDADDADDDADDADDDADDD AEEDAEEAEEDAEEAEEDAEEAEEDAEED
所以你可以做一个比较，这是一个完整的方法，可以在Erti-Chris Eelmaa的测试代码中使用：
private static void TemplatingImp(string input, string replaceWhat, IEnumerable replaceIterations) { const char splitter = '\t'; // use a char that will not appear in your string var inputTabbed = input.Replace(replaceWhat, splitter.ToString()); var inputs = inputTabbed.Split(splitter); // In parallel, build the output using the split parts (inputs) // and the replacement strings (newStrings) //var outputs = new List (); Parallel.ForEach(replaceIterations, iteration => { var output = string.Join(iteration, inputs); }); }
我在一个项目上遇到了类似的问题，我已经实现了一个Regex解决方案来对文件执行多个不区分大小写的替换。
出于效率目的，我设置标准只能通过原始字符串一次 。
我发布了一个简单的控制台应用程序来测试https://github.com/nmcc/Spikes/tree/master/StringMultipleReplacements上的一些策略
Regex解决方案的代码与此类似：
Dictionary replacements = new Dictionary(StringComparer.OrdinalIgnoreCase); // Fill the dictionary with the proper replacements: StringBuilder patternBuilder = new StringBuilder(); patternBuilder.Append('('); bool firstReplacement = true; foreach (var replacement in replacements.Keys) { if (!firstReplacement) patternBuilder.Append('|'); else firstReplacement = false; patternBuilder.Append('('); patternBuilder.Append(Regex.Escape(replacement)); patternBuilder.Append(')'); } patternBuilder.Append(')'); var regex = new Regex(patternBuilder.ToString(), RegexOptions.IgnoreCase); return regex.Replace(sourceContent, new MatchEvaluator(match => replacements[match.Groups[1].Value]));
编辑：在我的计算机上运行测试应用程序的执行时间是：
- 循环通过替换调用string.Substring（）（CASE SENSITIVE）：2ms
- 单次使用Regex并同时进行多次替换（不区分大小写）：8ms
- 使用ReplaceIgnoreCase扩展（不区分大小写）循环替换：55ms