在多维System.Collection.IList中快速查找

Question

我需要您的以下建议。

我有一个多维IList，其中包含具有索引，Id和Text的项目。通常，我知道Id的值，并据此获取Text。从数据库读取Id和Text值。

我们当前用于获取Text字段值的是：

foreach (Object myObj in List) 
{
    if (((MessageType)myObj).Id == id) 
    {
        return ((MessageType)myObj).Text;
    }
}

当IList中的计数变大（大于32K）时，需要一些时间来处理。

问题：有没有一种方法可以有效地获取Text值而无需遍历IList？

我尝试没有成功的事情：

• 使用List.IndexOf（Id）-无效，因为IndexOf仅适用于文本。
• 将List转换为多维数组-我的猜测对List.CopyTo（array，0）失败，因为它是多维的：string [] array = new string [List.Count，List.Count]; List.CopyTo（array，0）;

我不能使用AJAX / JQuery解决方案，因为它是一个现有的（活动）项目，并且重新编码将花费太多时间。

谢谢

Answer 1

如果要通过32k元素的集合中的某些标识符快速搜索，则应将其Dictionary<K,V>用作集合。

var dict = new Dictionary<IDType, MessageType>();

字典基本上是一棵搜索树，其中的元素以排序的方式存储，因此无需查看所有元素就可以找到具有特定键（在您的情况下为ID）的元素。有关更多信息，请参见MSDN。

如果您不能将集合重构为字典，则可以先填充字典（慢速），然后搜索字典（快速）。这只会是更快，如果你做多次搜索，你重新填写字典之前，也就是说，如果你的列表并不会经常改变。

foreach(object o in List)
{
    var msg = (MessageType)o;
    dict.Add(msg.Id, msg);
}

然后搜索很容易：

MessageType msg = dict[id];

编辑：恩，我很好奇，写了一个测试程序，比较了线性搜索和字典方法。这是我使用的：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class MessageType
    {
        public string Id;
        public string Text;
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rand = new Random ();
            // filling a list with random text messages
            List<MessageType> list = new List<MessageType>();
            for (int i = 0; i < 32000; i++)
            { 
                string txt = rand.NextDouble().ToString();
                var msg = new MessageType() {Id = i.ToString(), Text = txt };
                list.Add(msg);
            }
            IList List = (IList)list;

            // doing some random searches
            foreach (int some in new int[] { 2, 10, 100, 1000 })
            {
                var watch1 = new Stopwatch();
                var watch2 = new Stopwatch();
                Dictionary<string, MessageType> dict = null;
                for (int i = 0; i < some; i++)
                {
                    string id = rand.Next(32000).ToString();
                    watch1.Start();
                    LinearLookup(List, id);
                    watch1.Stop();

                    watch2.Start();
                    // fill once
                    if (dict == null)
                    {
                        dict = new Dictionary<string, MessageType>();
                        foreach (object o in List)
                        {
                            var msg = (MessageType)o;
                            dict.Add(msg.Id, msg);
                        }
                    }
                    // lookup 
                    DictionaryLookup(dict, id);
                    watch2.Stop();
                }

                Console.WriteLine(some + " x LinearLookup took " 
                    + watch1.Elapsed.TotalSeconds + "s");
                Console.WriteLine("Dictionary fill and " + some 
                    + " x DictionaryLookup took " 
                    + watch2.Elapsed.TotalSeconds + "s");
            }
        }

        static string LinearLookup(IList List, string id)
        {
            foreach (object myObj in List)
            {
                if (((MessageType)myObj).Id == id)
                {
                    return ((MessageType)myObj).Text;
                }
            }
            throw new Exception();
        }

        static string DictionaryLookup(Dictionary<string, MessageType> dict,
            string id)
        {
            return dict[id].Text;
        }
    }
}

我在Release / x86中得到的结果：

Number of | Time [ms] with | Time[ms] with | Speedup (approx.)
searches  | linear search  | dictionary(*) | with dictionary
----------+----------------+---------------+-----------------
      2   |      1.161     |   2.006       |   0.6
----------+----------------+---------------+-----------------
     10   |      2.834     |   2.060       |   1.4
----------+----------------+---------------+-----------------
    100   |     25.39      |   1.973       |   13
----------+----------------+---------------+-----------------
   1000   |    261.4       |   5.836       |   45
----------+----------------+---------------+-----------------

(*) including filling the dictionary once.

因此，我有点乐观地说，两次搜索就已经成功了。在我的测试应用程序中，我必须搜索10次才能使字典更快。

抱歉，我无法给出一个更现实的示例，我的ID都已排序。随意尝试修改和尝试；-)