5

这个问题似乎是无稽之谈。该行为无法可靠地再现。

比较以下测试程序，我观察到以下示例中的第一个和第二个之间存在巨大的性能差异（第一个示例比第二个慢十倍）：

第一个例子（慢）：

interface IWrappedDict {
    int Number { get; }
    void AddSomething (string k, string v);
}

class WrappedDict : IWrappedDict {
    private Dictionary<string, string> dict = new Dictionary<string,string> ();


    public void AddSomething (string k, string v) {
        dict.Add (k, v);
    }

    public int Number { get { return dict.Count; } }
}

class TestClass {
    private IWrappedDict wrappedDict;

    public TestClass (IWrappedDict theWrappedDict) {
        wrappedDict = theWrappedDict;
    }

    public void DoSomething () {
        // this function does the performance test
        for (int i = 0; i < 1000000; ++i) {
            var c = wrappedDict.Number; wrappedDict.AddSomething (...);
        }
    }
}

第二个例子（快速）：

// IWrappedDict as above
class WrappedDict : IWrappedDict {
    private Dictionary<string, string> dict = new Dictionary<string,string> ();
    private int c = 0;

    public void AddSomething (string k, string v) {
        dict.Add (k, v); ++ c;
    }

    public int Number { get { return c; } }
}
// rest as above

有趣的是，如果我将成员变量的类型TestClass.wrappedDict从IWrappedDict更改为 ，差异就会消失（第一个示例也很快） WrappedDict。我对此的解释是，Dictionary.Count每次访问元素时都会重新计算元素，并且元素数量的潜在缓存仅由编译器优化完成。

有人可以证实这一点吗？有没有办法以Dictionary一种高性能的方式获取元素的数量？

4

3 回答 3

5

不，每次使用时都不会Dictionary.Count重新计算元素。字典保持计数，应该和你的第二个版本一样快。

我怀疑在您对第二个示例的测试中，您已经WrappedDict使用了IWrappedDict，这实际上是关于接口成员访问（它始终是虚拟的）和 JIT 在知道具体类型时编译对属性的内联调用。

如果您仍然认为Count是问题所在，您应该能够编辑您的问题以显示一个简短但完整的程序，该程序演示快速和慢速版本，包括您如何计时。

于 2013-01-02T09:35:19.187 回答
4

听起来你的时机不对；我得到：

#1: 330ms
#2: 335ms

在 IDE 之外以发布模式运行以下命令时：

public void DoSomething(int count) {
    // this function does the performance test
    for (int i = 0; i < count; ++i) {
        var c = wrappedDict.Number; wrappedDict.AddSomething(i.ToString(), "a");
    }
}
static void Execute(int count, bool show)
{
    var obj1 = new TestClass(new WrappedDict1());
    var obj2 = new TestClass(new WrappedDict2());

    GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
    GC.WaitForPendingFinalizers();
    var watch = Stopwatch.StartNew();
    obj1.DoSomething(count);
    watch.Stop();
    if(show) Console.WriteLine("#1: {0}ms", watch.ElapsedMilliseconds);

    GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
    GC.WaitForPendingFinalizers();
    watch = Stopwatch.StartNew();
    obj2.DoSomething(count);
    watch.Stop();
    if(show) Console.WriteLine("#2: {0}ms", watch.ElapsedMilliseconds);
}
static void Main()
{
    Execute(1, false); // for JIT
    Execute(1000000, true); // for measuring
}

基本上：“无法复制”。另外：为了完整起见，否：.Count不计算所有项目（它已经知道计数），编译器也没有添加任何神奇的自动缓存代码（注意：有一些有限的例子；例如，JIT可以删除对向量for循环的边界检查）。

于 2013-01-02T09:43:16.497 回答
3

不，字典或哈希表从不迭代条目以确定长度。

它将（或应该）始终跟踪条目数。

因此，时间复杂度为O(1)。

于 2013-01-02T09:34:55.163 回答