logo标签列表

快速字符串比较与列表

c#liststring
5

我需要一种快速的方法来确定给定的字符串是否在一个字符串列表中。

字符串列表在运行时未知，但此后它将不会改变。

我可以简单地创建一个名为strings的List<String>，然后执行以下操作：

if (strings.Contains(item))

然而，如果列表中有许多字符串，这种方法的表现会很差。
我也可以使用一个 HashSet<String>，但这将需要在每个传入的字符串上调用 GetHashCode，以及 Equals，如果列表中只有三个字符串，这将是一种浪费。我提到了这需要快速吗？
我可以在设置时决定使用 List 还是 HashSet，具体取决于字符串的数量（例如，对于少于10个的字符串使用 List，否则使用 HashSet），就像 HybridDictionary 中的逻辑一样。
由于字符串是 Unicode，标准 Trie 结构将不起作用，尽管 Radix 树 / Patricia trie 可能有效。是否有任何带基准测试的好的 C# 实现？
有人提到绕过 String 的 GetHashCode 并使用更快的哈希函数。是否有任何基准测试？
使用 LINQ 表达式来创建一个优化的 switch 语句的方法是一种新颖的方法，看起来非常有趣。
还有什么方法可以使用？安装成本并不重要，只要搜索速度快即可。
如果有关系的话，传入的字符串值很少出现在列表中。
我已更新我的回答，包含有关 Unicode 折叠树信息的链接。 - Vinay Sajip
8个回答
5
如果字符串只包含 A-Z，甚至只是ASCII字符，则字典树会非常棒。但现在这些都是Unicode字符。 - Matt Howells
从我链接的维基百科文章中可以看出：“虽然它最常见，但尝试不一定要由字符串键入。相同的算法可以轻松地适应于任何构造的有序列表的类似功能，例如数字列表上的排列，形状列表上的排列等。”因此，您可以使用Unicode字符串中的代码点来实现这一点。 - Vinay Sajip
有 Unicode 实现的链接吗？是的，我可以使用 GetBytes 并在单个字节上切换，但我怀疑这样做性能不佳。 - Matt Howells
这里还有一个 - http://paste.lisp.org/display/12161 - C# 的 char 类型是一个16位的Unicode字符，你需要更多吗？ - Vinay Sajip
@Vinay，如果你读一下你刚刚链接的代码，你会发现它只支持a-z、A-Z和0-9字符，而不是整个Unicode字符范围。 - Matt Howells
显示剩余2条评论
2
关于您的“当列表很小时”的担忧；如果您不介意使用非泛型集合，System.Collections.Specialized.HybridDictionary可以做到这一点；它在小型情况下封装了System.Collections.Specialized.ListDictionary，在变大（>10）时则封装了System.Collections.Hashtable。值得一看吗？
否则，您可以使用自定义比较器的HashSet<T>？然后您可以选择GetHashCode()的开销有多大...
using System;
using System.Collections.Generic;

class CustomStringComparer : IEqualityComparer<string> {
    public bool Equals(string x, string y) {
        return string.Equals(x, y);
    }
    public int GetHashCode(string s) {
        return string.IsNullOrEmpty(s) ? 0 :
            s.Length + 273133 * (int)s[0];
    }
    private CustomStringComparer() { }
    public static readonly CustomStringComparer Default
        = new CustomStringComparer();
}
static class Program {
    static void Main() {
        HashSet<string> set = new HashSet<string>(
            new string[] { "abc", "def", "ghi" }, CustomStringComparer.Default);
        Console.WriteLine(set.Contains("abc"));
        Console.WriteLine(set.Contains("abcde"));
    }
}
1
这是一个好主意，但进一步思考后，在不知道列表中有多少个字符串时选择正确的哈希函数非常棘手。如果像你上面写的那个函数一样简单，那么在更大的列表中会有很多冲突。 - Matt Howells
2
我最终做了这个：
private static bool Contains(List<string> list, string value)
{
    bool contains = null != list.Find(str => str.ToLower().Equals(value.ToLower()));

    return contains;
}

我猜你可以为 List<string> 创建一个扩展方法，但是对于我的需求来说这已经足够了。
我认为这不够快，不能满足我的需求 ;) - Matt Howells
2
你考虑过使用.NET 3中的HashSet类吗？它可以替代这个HashSet类。
这将再次对每个传入的字符串调用.GetHashCode和.Equals。 - Lasse V. Karlsen
1
您可以使用重载构造函数来使用所选的比较器构造一个HashSet：HashSet(T) Constructor (IEqualityComparer(T))http://msdn.microsoft.com/zh-cn/library/bb359100.aspx - Dan Diplo
2
也许在这里使用HybridDictionary是一个更好的选择。它的内部使用取决于集合中有多少项。
0
你可以使用字符串驻留（string interning）来快速完成这个操作。在构建列表时，你需要将所需字符串存储为其驻留格式（即 string.Intern() 的结果）。然后，你需要使用 object.ReferenceEquals 来与一个驻留字符串进行比较，因为驻留的字符串具有相同的引用。
List<string> BuildList() {
    List<string> result;
    foreach (string str from StringSource())
         result.Add(str.Intern());
    return result;
}

bool CheckList(List<string> list, string stringToFind) { // list must be interned for this to work!
    return list.Find(str => object.ReferenceEquals(str, stringToFind)) != null;
}

这将导致每个列表进行四字节比较，并对原始字符串进行一次遍历。字符串池专门用于快速字符串比较和查找是否已存在，因此内部操作应该非常快。

不幸的是，String.Intern并不是那么快，并且会有不良副作用，即将字符串永久存储，直到我的进程耗尽内存（此应用程序处理大量字符串）。此外，随后使用ReferenceEquals搜索列表将是O（N）操作。 - Matt Howells
它比普通的字符串比较更快，但是对于处理大量字符串来说并不好。 - configurator
0
顺便提一下，如果我没记错的话，当一个字符串被构造时，它的哈希值会被预先计算并与字符串一起存储，以优化这种用例。如果你正在使用字符数组或 StringBuilder，这显然不适用，但对于不可变的字符串应该是适用的。
编辑：我错了... Java 缓存了字符串的哈希码，而 C# 没有。
在这种情况下，我认为记忆不起作用。当使用 Reflector 查看 System.String 时，我看不到哈希码缓存的任何证据。 - Matt Howells
你说得确实对。Java确实能够这样做，我认为C#也应该进行移植。 - CoderTao
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接