c# - 用于查找项目的字典与列表

Question

我的印象是在字典中查找项目比在列表中查找项目更快，下面的代码似乎表明并非如此:

字典:66 个刻度

列表:32 个报价点

我假设我搞砸了什么地方？

static void Main(string[] args)
    {
        // Speed test.
        Dictionary<string, int> d = new Dictionary<string, int>()
        {
            {"P1I1-1MS    P2I1-1MS    3I-1MS    4I-1MS", 2},
            {"P1I2-1MS    P2I1-1MS    3I-1MS    4I-1MS", 1},
            {"P1I3-1MS    P2I1-1MS    3I-1MS    4I-1MS", 0},
            {"P1I4-1MS    P2I1-1MS    3I-1MS    4I-1MS", -1},
            {"P1I5-1MS    P2I1-1MS    3I-1MS    4I-1MS", 0},
            {"P1I1-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
            {"P1I2-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
            {"P1I3-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
            {"P1I4-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
            {"P1I5-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
            {"P1I1-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
            {"P1I2-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
            {"P1I3-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
            {"P1I4-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
            {"P1I5-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
            {"P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS", 2} 
        };

        List<string> l = new List<string>();
            l.Add("P1I1-1MS    P2I1-1MS    3I-1MS    4I-1MS");
            l.Add("P1I2-1MS    P2I1-1MS    3I-1MS    4I-1MS");
            l.Add("P1I3-1MS    P2I1-1MS    3I-1MS    4I-1MS");
            l.Add("P1I4-1MS    P2I1-1MS    3I-1MS    4I-1MS");
            l.Add("P1I5-1MS    P2I1-1MS    3I-1MS    4I-1MS");
            l.Add("P1I1-1MS    P2I2-1MS    3I-1MS    4I-1MS");
            l.Add("P1I2-1MS    P2I2-1MS    3I-1MS    4I-1MS");
            l.Add("P1I3-1MS    P2I2-1MS    3I-1MS    4I-1MS");
            l.Add("P1I4-1MS    P2I2-1MS    3I-1MS    4I-1MS");
            l.Add("P1I5-1MS    P2I2-1MS    3I-1MS    4I-1MS");
            l.Add("P1I1-1MS    P2I3-1MS    3I-1MS    4I-1MS");
            l.Add("P1I2-1MS    P2I3-1MS    3I-1MS    4I-1MS");
            l.Add("P1I3-1MS    P2I3-1MS    3I-1MS    4I-1MS");
            l.Add("P1I4-1MS    P2I3-1MS    3I-1MS    4I-1MS");
            l.Add("P1I5-1MS    P2I3-1MS    3I-1MS    4I-1MS");
            l.Add("P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS");


        Stopwatch sw = new Stopwatch();

        string temp = "P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS";

        bool inDictionary = false;

        sw.Start();
        if (d.ContainsKey(temp))
        {
            sw.Stop();
            inDictionary = true;
        }
        else sw.Reset();

        Console.WriteLine(sw.ElapsedTicks.ToString());
        Console.WriteLine(inDictionary.ToString());


        bool inList = false;

        sw.Reset();
        sw.Start();
        if (l.Contains(temp))
        {
            sw.Stop();
            inList = true;
        }
        else sw.Reset();

        Console.WriteLine(sw.ElapsedTicks.ToString());
        Console.WriteLine(inList.ToString());

        Console.ReadLine();
    }

编辑

修改 Matthew Watson 的代码。

Answer 1

这是一个正确的测试:

Dictionary<string, int> d = new Dictionary<string, int>()
{
    {"P1I1-1MS    P2I1-1MS    3I-1MS    4I-1MS", 2},
    {"P1I2-1MS    P2I1-1MS    3I-1MS    4I-1MS", 1},
    {"P1I3-1MS    P2I1-1MS    3I-1MS    4I-1MS", 0},
    {"P1I4-1MS    P2I1-1MS    3I-1MS    4I-1MS", -1},
    {"P1I5-1MS    P2I1-1MS    3I-1MS    4I-1MS", 0},
    {"P1I1-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
    {"P1I2-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
    {"P1I3-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
    {"P1I4-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
    {"P1I5-1MS    P2I2-1MS    3I-1MS    4I-1MS", 0},
    {"P1I1-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
    {"P1I2-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
    {"P1I3-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
    {"P1I4-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
    {"P1I5-1MS    P2I3-1MS    3I-1MS    4I-1MS", 0},
    {"P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS", 2} 
};

List<string> l = new List<string>
{
    "P1I1-1MS    P2I1-1MS    3I-1MS    4I-1MS", 
    "P1I2-1MS    P2I1-1MS    3I-1MS    4I-1MS", 
    "P1I3-1MS    P2I1-1MS    3I-1MS    4I-1MS", 
    "P1I4-1MS    P2I1-1MS    3I-1MS    4I-1MS", 
    "P1I5-1MS    P2I1-1MS    3I-1MS    4I-1MS",
    "P1I1-1MS    P2I2-1MS    3I-1MS    4I-1MS", 
    "P1I2-1MS    P2I2-1MS    3I-1MS    4I-1MS",
    "P1I3-1MS    P2I2-1MS    3I-1MS    4I-1MS",
    "P1I4-1MS    P2I2-1MS    3I-1MS    4I-1MS",
    "P1I5-1MS    P2I2-1MS    3I-1MS    4I-1MS", 
    "P1I1-1MS    P2I3-1MS    3I-1MS    4I-1MS", 
    "P1I2-1MS    P2I3-1MS    3I-1MS    4I-1MS",
    "P1I3-1MS    P2I3-1MS    3I-1MS    4I-1MS", 
    "P1I4-1MS    P2I3-1MS    3I-1MS    4I-1MS",
    "P1I5-1MS    P2I3-1MS    3I-1MS    4I-1MS", 
    "P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS"
};

int trials = 4;
int iters  = 1000000;

Stopwatch sw = new Stopwatch();

string target = "P1I1-1MS    P2I4-1MS    3I-1MS    4I-1MS";

for (int trial = 0; trial < trials; ++trial)
{
    sw.Restart();

    for (int i = 0; i < iters; ++i)
        d.ContainsKey(target);

    sw.Stop();
    Console.WriteLine("Dictionary took " + sw.Elapsed);
    sw.Restart();

    for (int i = 0; i < iters; ++i)
        l.Contains(target);

    sw.Stop();
    Console.WriteLine("List took " + sw.Elapsed);
}

在任何调试器之外运行此版本的发布版本。

我的结果:

Dictionary took 00:00:00.0587588
List took 00:00:00.2018361
Dictionary took 00:00:00.0578586
List took 00:00:00.2003057
Dictionary took 00:00:00.0611053
List took 00:00:00.2033325
Dictionary took 00:00:00.0583175
List took 00:00:00.2056591

字典显然更快，即使条目很少。

有了更多条目，Dictionary 将比列表更快。

使用字典的查找时间为 O(1)，而列表则为 O(N)。对于较大的 N 值，这当然会产生巨大的差异。