13 
var dict = new Dictionary<int, string>();
for (int i = 0; i < 200000; i++)
    dict[i] = "test " + i;

我使用下面的代码迭代了这个字典：

foreach (var pair in dict)
    Console.WriteLine(pair.Value);

然后，我用这个迭代它：

foreach (var key in dict.Keys)
    Console.WriteLine(dict[key]);

第二次迭代减少了约 3 秒。我可以通过这两种方法获取键和值。我想知道的是第二种方法是否有缺点。由于我能找到的最受好评的问题不包括这种迭代字典的方式，我想知道为什么没有人使用它以及它如何更快地工作。

4

1 回答 1

23

您的时间测试有一些基本缺陷：

  • Console.Writeline 是一种 I/O 操作，它所花费的时间比内存访问和 CPU 计算多几个数量级。迭代时间的任何差异可能与此操作的成本相比相形见绌。这就像在铸铁炉子里测量硬币的重量。
  • 你没有提到整个操作花了多长时间，所以说一个比另一个少花 3 秒是没有意义的。如果第一次运行需要 300 秒，第二次运行需要 303 秒，那么您就是在进行微优化。
  • 你没有提到你是如何测量运行时间的。运行时间是否包括加载和引导程序集的时间？
  • 您没有提到可重复性：您是否多次运行这些操作？几百次？在不同的订单？

这是我的测试。请注意我如何尽我最大的努力确保迭代方法是唯一改变的东西，并且我包括一个控件来查看纯粹因为for循环和分配而占用了多少时间：

void Main()
{
    // Insert code here to set up your test: anything that you don't want to include as
    // part of the timed tests.
    var dict = new Dictionary<int, string>();
    for (int i = 0; i < 2000; i++)
        dict[i] = "test " + i;
    string s = null;
    var actions = new[]
    {
        new TimedAction("control", () => 
        {
    for (int i = 0; i < 2000; i++)
            s = "hi";
        }),
        new TimedAction("first", () => 
        {
            foreach (var pair in dict)
            s = pair.Value;
        }),
        new TimedAction("second", () => 
        {
            foreach (var key in dict.Keys)
            s = dict[key];
        })
    };
    TimeActions(100, // change this number as desired.
        actions);
}


#region timer helper methods
// Define other methods and classes here
public void TimeActions(int iterations, params TimedAction[] actions)
{
    Stopwatch s = new Stopwatch();
    foreach(var action in actions)
    {
        var milliseconds = s.Time(action.Action, iterations);
        Console.WriteLine("{0}: {1}ms ", action.Message, milliseconds);
    }

}

public class TimedAction
{
    public TimedAction(string message, Action action)
    {
        Message = message;
        Action = action;
    }
    public string Message {get;private set;}
    public Action Action {get;private set;}
}

public static class StopwatchExtensions
{
    public static double Time(this Stopwatch sw, Action action, int iterations)
    {
        sw.Restart(); 
        for (int i = 0; i < iterations; i++)
        {
            action();
        }
        sw.Stop();

        return sw.Elapsed.TotalMilliseconds;
    }
}
#endregion

结果

控制：1.2173ms
第一：9.0233ms
第二：18.1301ms

所以在这些测试中，使用索引器所花费的时间大约是迭代键值对的两倍，这是我所期望的*。如果我将条目数和重复次数增加一个数量级，这将保持大致成比例，如果我以相反的顺序运行这两个测试，我会得到相同的结果。

* 为什么我会期待这个结果？Dictionary 类可能在内部将其条目表示为 KeyValuePairs，因此当您直接迭代它时，它真正要做的就是遍历其数据结构一次，将每个条目交给调用者。如果您只迭代 Keys，它仍然必须找到每个 KeyValuePair，并为您提供Key财产，因此仅此一步将花费与首先迭代它大致相同的金额。然后你必须调用索引器，它必须计算提供的键的哈希值，跳转到正确的哈希表存储桶，并对在那里找到的任何 KeyValuePairs 的键进行相等性检查。这些操作并不是非常昂贵，但是一旦你做了 N 次，它的成本大致与你再次迭代内部哈希表结构一样昂贵。

于 2012-07-17T19:30:25.697 回答