代码之家 › 专栏 › 技术社区 › Matt Howells

与列表的快速字符串比较

string list c#

Matt Howells · 技术社区 · 17 年前

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

字符串列表在运行时之前是未知的,但此后它不会更改。

我可以简单地喝一杯 List<String> 打电话 strings 然后做:

if (strings.Contains(item))

我也可以用 HashSet<String> ,但这需要打电话 GetHashCode 在每个传入字符串上以及 Equals ,如果列表中只有3个字符串,这将是一种浪费。我有没有提到这件事 快速的 ?

我可以在设置时决定使用 List 或者 HashSet 根据字符串的数量(例如,对于少于10个字符串使用列表,否则使用HashSet),而与中的逻辑类似 HybridDictionary .

由于字符串是unicode,标准Trie结构将不起作用,尽管基数树/Patricia Trie可能起作用。有没有好的C#实现和基准测试?

有些人提到绕过 String 方法 以及使用执行速度更快的哈希函数。有什么基准吗?

使用LINQ表达式从本质上创建优化的switch语句是一种新颖的方法,看起来非常有趣。

还有什么办法?安装成本并不重要,只是搜索速度。

如果重要的话,传入的字符串值很少出现在列表中。

8 回复 | 直到 17 年前

Vinay Sajip 17 年前

你可以用一个 trie 持有字符串列表;尝试是为快速重新设计而设计的 特里亚 瓦尔,给你 one example 在C#中实现trie的方法。

: Powerpoint presentation on folded tries for Unicode 和 Ifo on implementation of a folded trie for Unicode (not C#)

GooseSerbus 11 年前

看看这些:

Jomo Fisher - Fast Switching with LINQ

Gustavo Guerra - StaticStringDictionary - Fast Switching with LINQ revisited

Dan Diplo 17 年前

你有没有考虑过使用 HashSet

Marc Gravell 17 年前

重新考虑你的“当清单很小”问题;如果您不介意使用非泛型集合, System.Collections.Specialized.HybridDictionary 做这样的事情;它封装了一个 System.Collections.Specialized.ListDictionary 小的时候,还是小的时候 System.Collections.Hashtable 当它变大的时候( >10 ).值得一看吗?

否则你也许可以用 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"));
    }
}

Pat 17 年前

也许是 HybridDictionary 这是一个更好的选择。其内部用途取决于集合中的项目数量。

Hector Sosa Jr 17 年前

我最终做了这样的事:

private static bool Contains(List<string> list, string value)
{
    bool contains = null != list.Find(str => str.ToLower().Equals(value.ToLower()));

    return contains;
}

我猜你可以为它创建一个扩展方法 List<string> ,但这足以满足我的需要。

CoderTao 17 年前

另一方面,如果内存可用,则在构造字符串时,它的HashValue将被预计算并与字符串一起存储,作为这种类型用例的优化。如果您使用的是字符数组或StringBuilder,这显然不适用,但对于不可变的字符串应该适用。

编辑:我错了。。。Java会缓存字符串的哈希代码,而C#不会。

configurator 17 年前

在构建列表时,必须存储所需字符串的内部格式( 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;
}

这将导致对每个列表进行四字节比较,并对原始字符串进行一次传递。字符串的intern池是专门为快速字符串比较和查找是否已经存在而构建的,因此intern操作应该非常快。