最佳C#实现IndexOfAny(string，params string[])
最佳C#实现IndexOfAny(string，params string[])
提问于 2019-07-26 19:05:31
.Net提供String.IndexOfAny(string, char[])，但不提供String.IndexOfAny(string, string[])。
现有的内置String.IndexOfAny接受一个char数组，如果找不到任何一个char，则从数组中返回string或-1中传递的任何一个D5的最低位置。从本质上说，它相当于我天真的定义的char。
我的分机使用string搜索s，使用strings数组查找targets，如果没有找到，则返回s或-1中任何targets成员中最低的位置。
天真的实现(使用LINQ)并不特别有效：
public static int IndexOfAny1(this string s, params string[] targets) =>
targets.Select(t => s.IndexOf(t)).Where(p => p >= 0).DefaultIfEmpty(-1).Min();我改进的实现跟踪当前候选人职位，并将未来搜索限制在该候选人职位之前：
public static int IndexOfAny2(this string s, params string[] targets) {
int? curAns = null;
foreach (var target in targets) {
var posAns = s.IndexOf(target, 0, curAns.HasValue ? curAns.Value + target.Length : s.Length);
if (posAns >= 0 && (!curAns.HasValue || posAns < curAns)) {
curAns = posAns;
if (curAns == 0) // once you're at the beginning, can't be any less
break;
}
}
return curAns ?? -1;
}这个速度快了两倍。
测试这两种方法的示例代码：
Console.WriteLine($"IndexOfAny1 should be 8: {"foo bar baz".IndexOfAny1("barz", "baz")}");
Console.WriteLine($"IndexOfAny1 should be 0: {"aabbccddeeffgghh".IndexOfAny1("bbb", "hh", "aa")}");
Console.WriteLine($"IndexOfAny2 should be 8: {"foo bar baz".IndexOfAny2("barz", "baz")}");
Console.WriteLine($"IndexOfAny2 should be 0: {"aabbccddeeffgghh".IndexOfAny2("bbb", "hh", "aa")}");是否有更好的算法或其他方法使这更快？
用于测试随机可能性的PS测试工具：
var r = new Random();
var sb = new StringBuilder();
for (int j1 = 0; j1 < r.Next(80,160); ++j1)
sb.Append((char)('0'+r.Next(0, 26+52)));
var s = sb.ToString();
var listTargets = new List();
for (int j1 = 0; j1 < r.Next(5, 10); ++j1)
if (r.NextDouble() < 0.8) {
var tLen = r.Next(4, Math.Min(s.Length - 4, 10));
var beginPos = r.Next(0, s.Length - tLen);
listTargets.Add(s.Substring(beginPos, tLen));
}
else {
sb.Clear();
for (int j2 = 0; j2 < r.Next(5, 10); ++j2)
sb.Append((char)('0'+r.Next(0, 26+52)));
listTargets.Add(sb.ToString());
}
var targets = listTargets.ToArray();
if (s.IndexOfAny1(targets) != s.IndexOfAny2(targets))
Console.WriteLine($"Fail on {s} containing {String.Join(",", targets)}");回答 2
Code Review用户
发布于 2019-07-29 20:11:07
评论
- 不要使用缩写变量名
s、curAns和posAns；使用自描述名称：value、index和targetIndex。 - 可以用
-1替换可空的int。这样读起来更干净，并允许您绕过curAns ?? -1中的最后一个D14操作符。 - 您可以通过添加
curAns.Value + target.Length来优化计数-1，因为我们不关心在当前最好的索引上找到另一个匹配项。 - 如果没有指定目标，则应提前退出。
重构
public static int IndexOfAny2(this string value, params string[] targets)
{
var index = -1;
if (targets == null || targets.Length == 0) return index;
foreach (var target in targets)
{
var targetIndex = value.IndexOf(target, 0,
index > -1 ? index + target.Length - 1 : value.Length);
if (targetIndex >= 0 && (index == -1 || targetIndex < index))
{
index = targetIndex;
if (index == 0)
{
break;
}
}
}
return index;
}Code Review用户
发布于 2019-07-30 15:08:03
"abc".IndexOfAny2("c", "abc")在ArgumentOutOfRangeException中失败，因为IndexOf要求startIndex + count不超过字符串的长度。- 对于一个微小的改进，让
curAns成为一个普通整数，并使用s.Length初始化它。在进行了必要的更改之后，您将在foreach循环中得到更少的检查。
然而，大多数时间都花在string.IndexOf上，因此，为了获得更多实质性的改进，您需要研究更优化(和更复杂)的算法，如Rabin、Knuth Pratt、Boyer、Aho等。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/224980
复制相关文章
相似问题
腾讯云开发者
