Dictionary.Điều chỉnh hiệu suất

Question

Câu hỏi này dường như là vô nghĩa. Hành vi không thể được sao chép một cách đáng tin cậy.

So sánh các chương trình thử nghiệm sau đây, tôi quan sát thấy một khổng lồ chênh lệch hiệu suất giữa đầu tiên và thứ hai trong những ví dụ sau đây (ví dụ đầu tiên là do yếu tố mười chậm hơn so với thứ hai):

dụ đầu tiên (chậm):

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

dụ thứ hai (nhanh):

// 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 

Funnily, sự khác biệt biến mất (ví dụ đầu tiên cũng nhanh) nếu tôi thay đổi loại biến thành viên TestClass.wrappedDict từ IWrappedDict thành WrappedDict. Giải thích của tôi về điều này là Dictionary.Count tính lại các phần tử mỗi khi nó được truy cập và bộ nhớ đệm tiềm năng của số lượng các phần tử được thực hiện bằng cách tối ưu hóa trình biên dịch chỉ.

Ai đó có thể xác nhận điều này không? Có cách nào để có được số lượng các phần tử trong một Dictionary theo cách thực hiện không?

Answer 1

Âm thanh như thời gian của bạn bị tắt; Tôi nhận được:

#1: 330ms 
#2: 335ms 

khi chạy sau trong chế độ phát hành, bên ngoài của 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 
} 

Về cơ bản: "không thể tái tạo". Ngoài ra: để hoàn thành, không: .Count không đếm tất cả các mục (nó đã biết đếm), cũng không trình biên dịch thêm bất kỳ ma thuật tự động bộ nhớ đệm mã (lưu ý: có một vài ví dụ giới hạn của những thứ như thế; ví dụ, các JIT có thể loại bỏ việc kiểm tra giới hạn trên một vòng lặp for qua một số vectơ).

Answer 2

Không, từ điển hoặc hashtable không bao giờ lặp lại các mục nhập để xác định độ dài.

Sẽ (hoặc phải) luôn theo dõi số lượng mục nhập.

Do đó, độ phức tạp thời gian là O(1).

Answer 3

Không, Dictionary.Count không không kể lại các phần tử mỗi lần sử dụng. Từ điển duy trì số lượng và phải nhanh như phiên bản thứ hai của bạn.

Tôi nghi ngờ rằng trong thử nghiệm ví dụ thứ hai, bạn đã có WrappedDict thay vì IWrappedDict và điều này thực sự là về quyền truy cập thành viên giao diện (luôn ảo) và JIT biên soạn cuộc gọi nội bộ đến thuộc tính khi nó biết loại bê tông.

Nếu bạn vẫn tin rằng Count là vấn đề, bạn có thể chỉnh sửa câu hỏi của mình để hiển thị chương trình ngắn nhưng đầy đủ thể hiện cả phiên bản nhanh và chậm, kể cả cách bạn định thời gian.