“如果你只有一个锤子…”

…那么所有东西看起来都像钉子”，这句谚语是这么说的。

我将用一个关于我有时看到的一个常见错误的简短故事来阐释这一点。

(代码示例使用 C#，但仅使用基本功能，因此 C++ 和 Java 开发者应该不会太迷茫。)

静态数组

当你开始编程时，你使用的第一个 集合 很有可能是 定长数组，因此你已经习惯了，甚至可以说是沉迷于它的 方括号 [] 索引。这很有道理：这是一个非常简单直观的 接口，用于访问集合的元素，一个很好的 锤子。

所以当你想要计算一个钉子，呃，我的意思是 int[] 数组的所有元素的总和时，你使用了这样的代码

long sum = 0;
for (int i = 0; i < array.Length; ++i)
{
    sum += array[i];
}

简单高效！

动态数组

后来，你遇到了无法预先知道集合的 最终长度 的情况，你发现了 动态数组，例如 List<T>。 你很自然地复制粘贴了你的旧代码，并很快发现你唯一需要更改的就是将“Length”属性替换为“Count”属性

long sum = 0;
for (int i = 0; i < list.Count; ++i)
{
    sum += list[i];
}

一切都运行良好，即使处理大数据集也没有问题。 看起来列表也像一个 钉子，到目前为止一切都很好…

关联数组

再后来，你发现有时使用连续整数进行索引是不够的，你需要将一个更丰富的 标识符 与集合的每个元素关联起来。 谷歌 告诉你，你需要的是一个被称为 关联数组、映射 或 字典 的东西，而 C# 提供了一些实现，如 Dictionary<TKey, TValue>。

但这一次，情况更复杂：你仍然可以使用 Count 属性，但你已经失去了性感的 方括号索引 ！这很令人沮丧，你有一个锤子，一个真正酷炫强大的锤子，多年来在无数情况下都有效，但现在你不得不处理一些乍一看并不像钉子的东西。 但通过再次查看 Dictionary 类型，你发现由于 Linq 及其 ElementAt() 扩展方法，它可能看起来像一个钉子，不，它变成了钉子，不不，它是钉子，钉子，是的，钉子！

然后你这样做

long sum = 0;
for (int i = 0; i < dictionary.Count; ++i)
{
    sum += dictionary.ElementAt(i).Value;
}

哇！ 哇！ 它工作了！

好吧，至少在处理一小部分数据的玩具程序中是这样的…

它几乎奏效了

因为后来，当你的老板让你处理一个巨大的 1G 文件时，你感觉有些不对劲，因为它慢得要命。 后来，你的老板回来了，开始探头探脑地看着你，焦急地等待结果，因为他需要在下午 4 点的会议上使用它们。 当你用尽了所有的玩笑并且它仍在运行时，你明白它可能无法按时完成，并且感觉很好… 尴尬。

那么发生了什么？

答案很简单：字典 不是钉子，你无法像使用基于 连续内存区域（可以在恒定时间内访问元素） 也就是 O(1) 的 数组 或 列表 那样快速地索引它。 所以当你让 Linq 获取 dictionary 的第 i^th 个元素时，它只会 枚举元素并计数，直到它到达 i 并返回当前元素。 这种枚举的复杂度是 O(n)，不算太疯狂。 但请记住，你在主循环的每次迭代中都使用它 => 你的总和的整个复杂度是 O(n²)，哎哟！

解决方案

我们已经看到整数索引不适合 dictionary，所以我们将使用另一种抽象：对元素进行简单 迭代

long sum = 0;
foreach (KeyValuePair<int, int> pair in dictionary)
{
    sum += pair.Value;
}

这导致了完全不同的代码，虽然不是那么复杂，但这一次你获得了不错的性能。

基准测试

这是我使用的基准测试

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

class Test
{
    static void Main()
    {
        const int N = (int)5e4;
        
        int[] array = new int[N];
        List<int> list = new List<int>(N);
        Dictionary<int, int> dictionary = new Dictionary<int, int>(N);
        
        Random rand = new Random();
        
        for (int i = 0; i < N; ++i)
        {
            int n = rand.Next() % 100;
        
            array[i] = n;
            list.Add(n);
            dictionary[i] = n;
        }
        
        long sumA = 0, sumL = 0, sumD = 0, sumD2 = 0;
        
        Stopwatch sw = new Stopwatch();
        
        sw.Start();
        for (int i = 0; i < array.Length; ++i)
        {
            sumA += array[i];
        }
        sw.Stop();
        
        long arrayDuration = sw.ElapsedTicks;
        
        sw.Restart();
        for (int i = 0; i < list.Count; ++i)
        {
            sumL += list[i];
        }
        sw.Stop();
        
        long listDuration = sw.ElapsedTicks;
        
        sw.Restart();
        for (int i = 0; i < dictionary.Count; ++i)
        {
            sumD += dictionary.ElementAt(i).Value;
        }
        sw.Stop();
        
        long dictionaryDuration = sw.ElapsedTicks;
        
        sw.Restart();
        foreach (KeyValuePair<int, int> pair in dictionary)
        {
            sumD2 += pair.Value;
        }
        sw.Stop();
        
        long dictionaryDuration2 = sw.ElapsedTicks;

        string outputTemplate = @"+----------------------+
|TYPE  |TICKS   |FACTOR|
+----------------------+
|array |{0,8}|{4,6}|
+----------------------+
|list  |{1,8}|{5,6}|
+----------------------+
|dico1 |{2,8}|{6,6}|
+----------------------+
|dico2 |{3,8}|{7,6}|
+----------------------+";
        
        Console.WriteLine(outputTemplate, arrayDuration, listDuration, 
           dictionaryDuration, dictionaryDuration2,
           1, listDuration / arrayDuration, 
           dictionaryDuration / arrayDuration, 
           dictionaryDuration2 / arrayDuration);
    }
}

以下是一些结果

+----------------------+
|TYPE  |TICKS   |FACTOR|
+----------------------+
|array |     240|     1|
+----------------------+
|list  |     704|     2|
+----------------------+
|dico1 |53844427|224351|
+----------------------+
|dico2 |    2367|     9|
+----------------------+

正如你所看到的，朴素的 ElementAt 迭代比 foreach 迭代 慢 20000 倍，比参考定长数组实现慢 200000 倍！

结论

底线很简单：停止将所有东西都看作钉子，并尝试适应每种情况，在这里适应每个集合以获得最佳效果。