2

I was under the impression that it was quicker to look up items in a Dictionary than a List, the follow code seems to suggest otherwise:

Dictionary : 66 ticks

List: 32 ticks

Im assuming ive screwed up somewhere?

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();
    }

EDIT

Modification to Matthew Watson's code.

4

3 回答 3

4

这是一个适当的测试：

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)，而 List 需要 O(N)。这当然会对较大的 N 值产生巨大的影响。

于 2013-08-15T08:22:39.883 回答
2

这是由于大数定律。简而言之

根据规律，大量试验得到的结果的平均值应该接近预期值，并且随着试验次数的增加而趋于接近。

另一个约束是Big-O 表示法，它实际上在小范围内是无用的。例如，对于小于某个小数字的给定n ，您可以说 O(1) ~ O(N) ~ O(n!) 。

运行一个好的实验需要满足一些非常严格的条件，例如：

  • 确保算法具有可比性
  • 在算法中有大量的迭代
  • 在相同的硬件上运行
  • 以最大优化的发布模式运行
  • 不应附加调试器或性能分析工具
  • 进行许多实验并计算平均值 + 标准偏差
  • ...
于 2013-08-15T08:20:28.077 回答
2

Dictionary 在单词的渐近意义上比 List 快：O(1) < O(n); 这意味着有这样一个大小 X 开始在 Dictionary 上比 List 更快。例如，如果 Dictionary/List 包含 10000 个或更多项目，Dictionary 总是更快（如果要存储的项目更少，比如 5 个，List 可能会更快）。Dictionary 还有一个问题：它需要GetHashCode()方法；如果 GetHashCode() 实施不当，字典可能会非常缓慢。

于 2013-08-15T08:17:44.547 回答