在C#中迭代字典

Question

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秒.我可以通过两种方法获得键和值.我想知道第二种方法是否有缺点.由于我能找到的评价最高的问题不包括这种迭代字典的方式,我想知道为什么没有人使用它以及它如何更快地工作.

Answer 1

你的时间测试有一些根本性的缺陷:

• 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次,它就像你再次迭代内部哈希表结构一样昂贵.