शब्दकोश। गणना प्रदर्शन

Question

यह प्रश्न बकवास लगता है। व्यवहार विश्वसनीय रूप से पुन: उत्पन्न नहीं किया जा सकता है।

पहले उदाहरण (:

निम्नलिखित परीक्षण कार्यक्रमों की तुलना करना, मैं पहले और निम्न उदाहरण के दूसरे जो विशाल प्रदर्शन अंतर (पहला उदाहरण कारक दस सेकंड की तुलना में धीमी कर रहा है) मनाया धीमी गति से):

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 

मजेदार, अंतर गायब हो जाता है (पहला उदाहरण तेज़ हो जाता है) यदि मैं IWrappedDict से WrappedDict से सदस्य चर TestClass.wrappedDict का प्रकार बदलता हूं। इसकी मेरी व्याख्या यह है कि Dictionary.Count प्रत्येक बार जब इसे एक्सेस किया जाता है तो तत्वों को दोबारा गिना जाता है और तत्वों की संख्या की संभावित कैशिंग केवल कंपाइलर अनुकूलन द्वारा की जाती है।

क्या कोई इसकी पुष्टि कर सकता है? क्या किसी प्रदर्शन के तरीके में Dictionary में तत्वों की संख्या प्राप्त करने का कोई तरीका है?

Answer 1

आपके समय की तरह ध्वनि बंद है; मैं:

#1: 330ms 
#2: 335ms 

जब रिलीज़ मोड में निम्न चल रहा है, आईडीई के बाहर:

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 सभी वस्तुओं की गणना नहीं करता है (यह पहले से ही गिनती जानता है), न ही संकलक किसी भी जादू स्वचालित कैशिंग कोड को जोड़ता है (नोट: इस तरह की चीजों के कुछ सीमित उदाहरण हैं; उदाहरण के लिए, जेआईटी लूप को वेक्टर पर सीमा-जांच को हटा सकता है)।

Answer 2

नहीं, एक शब्दकोश या हैशटेबल लंबाई निर्धारित करने के लिए प्रविष्टियों को कभी भी दोहराता नहीं है।

यह (या चाहिए) हमेशा प्रविष्टियों की संख्या का ट्रैक रखेगा।

इस प्रकार, समय जटिलता O(1) है।

Answer 3

नहीं है, Dictionary.Countनहीं ब्योरा तत्वों हर बार यह प्रयोग किया जाता है। शब्दकोश एक गिनती बनाए रखता है, और आपके दूसरे संस्करण के जितना तेज़ होना चाहिए।

मुझे लगता है कि दूसरे उदाहरण के अपने परीक्षण में, आप पहले से ही IWrappedDict के बजाय WrappedDict था, और यह वास्तव में इंटरफ़ेस सदस्य पहुँच के बारे में है (जो हमेशा आभासी है) और JIT संपत्ति को इनलाइन करने कॉल संकलन जब यह जानता है ठोस प्रकार।

आपको अभी भी लगता Count समस्या है, तो आप अपने प्रश्न संपादित करने के लिए एक छोटा लेकिन पूरा कार्यक्रम है जो आप इसे कैसे सभी समय कर रहे हैं सहित दोनों तेज और धीमी संस्करणों, यह दर्शाता है दिखाने के लिए सक्षम होना चाहिए।