Tra cứu nhanh Danh sách <T>

Question

Tôi có hai danh sách chung. Giả sử chúng là List<A> và List<B>.

Lớp A có thuộc tính, loại là List<B>. Thuộc tính này chứa các đối tượng kiểu B, được lọc bởi một số mệnh đề khác của đối tượng A.

Vì vậy:

class A{ 
    public int Something1; 
    public int Something2; 
    public List<B> Something3; 
} 

class B{ 
    public int Anything1; 
    public int Anything2; 
} 

Tôi muốn thêm tất cả các đối tượng B như một danh sách để phản đối A (để tài sản được gọi là Something3), nơi chúng ta hãy nói đối tượng A.Something1 == B.Anything1.

Câu hỏi của tôi là: cách hiệu quả nhất để thêm List<B> mục vào mục List<A> là gì? Lưu ý, có thể có hàng trăm nghìn đối tượng trong cả hai danh sách.

(VS2010; C#; .Net4)

Answer 1

Tập đoàn B 's trên Anything1 tài sản và đưa trong từ điển. Sau đó, bạn lặp qua các A thể 's và hiệu quả chọn ra danh sách các B' s:

Dictionary<int, List<B>> beegroups = bees.GroupBy(b => b.Anything1).ToDictionary(g => g.Key, g => g.ToList()); 

foreach (A a in ayes) { 
    List<B> group; 
    if (beegroups.TryGetValue(a.Something1, out group)) { 
    a.Something3 = group; 
    } 
} 

Answer 2

Tôi sẽ sử dụng một bản đồ Kiểm tra nếu nó tồn tại trong danh sách B trước khi thêm vào danh sách Một

Answer 3

Nếu có rất nhiều dữ liệu như bạn đã đề cập, việc thực hiện các lựa chọn & hoạt động chèn là thứ tự sau đây.

Từ Generic Dictionaries in C#:

1. Dictionary<int,A>

   • Chọn: O (1) (có nghĩa là phức tạp)
   • Add: O (1) [hoặc O (n)]
   • Dựa trên bảng băm

2. SortedDictionary<int,A>

   • Chọn: O (log n)
   • Add: O (log n)
   • Dựa trên một cây tìm kiếm nhị phân

3. SortedList<int,A>

   • Chọn: O (log n) [hoặc O (n)]
   • Add: O (n)
   • Dựa trên một bộ sưu tập được sắp xếp (mảng khá lớn)

Xin lưu ý rằng nếu số lượng dữ liệu là tương đối nhỏ, nó List<int, A> sẽ là tốt. (Tùy thuộc vào kích thước dữ liệu của bạn, thứ tự trên sẽ được sắp xếp lại.)

Trong khi đó, bạn cần phải xem xét năng lực của Collection kiểu trong C#. Loại Collection có thể thay đổi kích cỡ, vì vậy nếu kích thước thiếu, Bộ sưu tập được tạo lại lớn hơn trước và các phần tử được chèn lại. Điểm này cho bạn biết rằng nếu bạn đã biết kích thước của Bộ sưu tập, bạn nên đặt công suất tại bộ dựng Bộ sưu tập.

Answer 4

Đây là phương pháp thay thế sử dụng LINQ hiệu quả hơn chứ không chỉ thay thế các danh sách trong mỗi A. Sử dụng một nhóm tham gia và thêm các mục trong mỗi nhóm vào A tương ứng.

List<A> myAs = ...; 
List<B> myBs = ...; 

var pairs = from a in myAs 
      join b in myBs on a.Something1 equals b.Anything1 into TheseBs 
      select new { A = a, TheseBs }; 

foreach (var pair in pairs) 
{ 
    pair.A.Something3.AddRange(pair.TheseBs); 
}