c# - 什么是最快的 sql 实现，如 'x%' 在 c# 集合中的键

Question

我需要对数十万个键进行非常快速的前缀 “sql like” 搜索。我曾尝试使用 SortedList、Dictionary 和 SortedDictionary 进行性能测试，我喜欢这样做:

var dictionary = new Dictionary<string, object>();
// add a million random strings
var results = dictionary.Where(x=>x.Key.StartsWith(prefix));

我发现它们都需要很长时间，Dictionary 最快，SortedDictionary 最慢。

然后我尝试了 http://www.codeproject.com/Articles/640998/NET-Data-Structures-for-Prefix-String-Search-and-S 的 Trie 实现，它快了一个数量级，即。毫秒而不是秒。

所以我的问题是，是否没有可用于上述要求的 .NET 集合？我原以为这是一个常见的要求。

我的基本测试:

    class Program
    {
        static readonly Dictionary<string, object> dictionary = new Dictionary<string, object>(); 
        static Trie<object> trie = new Trie<object>(); 

        static void Main(string[] args)
        {
            var random = new Random();
            for (var i = 0; i < 100000; i++)
            {
                var randomstring = RandomString(random, 7);
                dictionary.Add(randomstring, null);
                trie.Add(randomstring, null);
            }

            var lookups = new string[10000];
            for (var i = 0; i < lookups.Length; i++)
            {
                lookups[i] = RandomString(random, 3);
            }

            // compare searching
            var sw = new Stopwatch();
            sw.Start();
            foreach (var lookup in lookups)
            {
                var exists = dictionary.Any(k => k.Key.StartsWith(lookup));
            }
            sw.Stop();
            Console.WriteLine("dictionary.Any(k => k.Key.StartsWith(randomstring)) took : {0} ms", sw.ElapsedMilliseconds);

// test other collections

            sw.Restart();
            foreach (var lookup in lookups)
            {
                var exists = trie.Retrieve(lookup).Any();
            }
            sw.Stop();
            Console.WriteLine("trie.Retrieve(lookup) took : {0} ms", sw.ElapsedMilliseconds);

            Console.ReadKey();
        }

        public static string RandomString(Random random,int length)
        {
            const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

            return new string(Enumerable.Repeat(chars, length)
              .Select(s => s[random.Next(s.Length)]).ToArray());
        }
    }

结果:

dictionary.Any(k => k.Key.StartsWith(randomstring)) took : 80990 ms
trie.Retrieve(lookup) took : 115 ms

Answer 1

如果排序很重要，请尝试使用 SortedList而不是 SortedDictionary .它们都具有相同的功能，但实现方式不同。 SortedList当你想枚举元素时更快(并且你可以通过索引访问元素)，SortedDictionary如果有很多元素并且您想在集合中间插入一个新元素，速度会更快。

那么试试这个:

var sortedList = new SortedList<string, object>();
// populate list...

sortedList.Keys.Any(k => k.StartsWith(lookup));

如果您有一百万个元素，但不想在填充字典后对它们重新排序，您可以结合它们的优点:填充一个 SortedDictionary使用随机元素，然后创建一个新的 List<KeyValuePair<,>>或 SortedList<,>从那开始。