5

この質問はナンセンスに思えます。動作を確実に再現することはできません。

次のテスト プログラムを比較すると、次の例の 1 番目と 2 番目の例では大きなパフォーマンスの違いが見られました (最初の例は 2 番目の例よりも 10 倍遅くなります)。

最初の例 (遅い):

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

2 番目の例 (高速):

// 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ません。ディクショナリはカウントを維持し、2 番目のバージョンと同じくらい高速である必要があります。

2 番目の例のテストでは、 のWrappedDict代わりに既にIWrappedDict.

それでも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 vectorforに対するループの境界チェックを削除できます)。

于 2013-01-02T09:43:16.497 に答える
3

いいえ、辞書またはハッシュテーブルは、長さを決定するためにエントリを反復することはありません。

常にエントリ数を追跡します (または追跡する必要があります)。

したがって、時間計算量はO(1)です。

于 2013-01-02T09:34:55.163 に答える