0

我遇到了在字符串中搜索 90,000 个 GUID 的问题。我需要获取每个 GUID 的所有实例。从技术上讲，我也需要更换它们，但这是另一回事。

目前，我正在使用正则表达式单独搜索每一个。但我突然想到，通过一起搜索它们可以获得更好的性能。我过去读过有关尝试的内容，但从未使用过，但我突然想到我可以构建一个包含所有 90,000 个 GUID 的 trie 并使用它来搜索。

或者，也许 .NET 中有一个现有的库可以做到这一点。我突然想到，我没有理由只用一个巨大的正则表达式就不能获得良好的性能，但这似乎行不通。

除此之外，也许我可以使用一些与 GUID 结构相关的聪明技巧来获得更好的结果。

这对我来说并不是一个真正的关键问题，但我认为我可能能够学到一些东西。

4

4 回答 4

1

看看 Rabin-Karp 字符串搜索算法。它非常适合在字符串中进行多模式搜索：

http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search

于 2012-11-19T20:25:51.417 回答
1

不久前我开发了一种替换大量字符串的方法，这可能很有用：

替换许多字符串的更好方法 - C# 中的混淆

另一种选择是使用正则表达式来查找字符串中的所有 GUID，然后遍历它们并检查每个 GUID 是否是您的 GUID 集的一部分。

基本示例，使用Dictionary快速查找 GUID：

Dictionary<string, string> guids = new Dictionary<string, string>();
guids.Add("3f74a071-54fc-10de-0476-a6b991f0be76", "(replacement)");

string text = "asdf 3f74a071-54fc-10de-0476-a6b991f0be76 lkaq2hlqwer";

text = Regex.Replace(text, @"[\da-f]{8}-[\da-f]{4}-[\da-f]{4}-[\da-f]{4}-[\da-f]{12}", m => {
  string replacement;
  if (guids.TryGetValue(m.Value, out replacement)) {
    return replacement;
  } else {
    return m.Value;
  }
});

Console.WriteLine(text);

输出：

asdf (replacement) lkaq2hlqwer
于 2012-11-19T20:21:33.490 回答
1

使用 RegEx 不会获得良好的性能，因为它的性能天生就很差。此外，如果所有 GUID 共享相同的格式，您应该只需要一个 RegEx。并且regex.Replace(input, replacement);会去做。

String.Replace如果您已经在内存中拥有 guid 列表，那么通过循环遍历该列表并像这样进行调用，性能会更好

 foreach(string guid in guids)
     inputString.replace(guid, replacement);
于 2012-11-19T20:22:00.867 回答
0

好的，这看起来不错。所以这里要清楚的是原始代码，它在示例字符串上运行了 65 秒：

   var unusedGuids = new HashSet<Guid>(oldToNewGuid.Keys);

    foreach (var guid in oldToNewGuid) {
        var regex = guid.Key.ToString();

        if (!Regex.IsMatch(xml, regex))
             unusedGuids.Add(guid.Key);
        else
            xml = Regex.Replace(xml, regex, guid.Value.ToString());
    }

新代码如下，耗时6.7s：

var unusedGuids = new HashSet<Guid>(oldToNewGuid.Keys);

var guidHashes = new MultiValueDictionary<int, Guid>();

foreach (var guid in oldToNewGuid.Keys) {
    guidHashes.Add(guid.ToString().GetHashCode(), guid);
}

var indices = new List<Tuple<int, Guid>>();

const int guidLength = 36;

for (int i = 0; i < xml.Length - guidLength; i++) {
    var substring = xml.Substring(i, guidLength);

    foreach (var value in guidHashes.GetValues(substring.GetHashCode())) {
         if (value.ToString() == substring) {
        unusedGuids.Remove(value);
        indices.Add(new Tuple<int, Guid>(i, value));
        break;
         }
    }
}

var builder = new StringBuilder();

int start = 0;
for (int i = 0; i < indices.Count; i++) {
    var tuple = indices[i];
    var substring = xml.Substring(start, tuple.Item1 - start);
    builder.Append(substring);
    builder.Append(oldToNewGuid[tuple.Item2].ToString());
    start = tuple.Item1 + guidLength;
}

builder.Append(xml.Substring(start, xml.Length - start));

xml = builder.ToString();
于 2012-11-19T21:38:08.490 回答