Bộ sưu tập .NET nào cung cấp tìm kiếm nhanh nhất

Question

Tôi có 60k mục cần được kiểm tra trong danh sách tra cứu 20k. Có một đối tượng bộ sưu tập (như List, HashTable) cung cấp phương pháp đặc biệt nhanh chóng Contains() không? Hoặc tôi sẽ phải viết của riêng tôi? Trong các từ khác, phương thức mặc định là Contains() chỉ quét từng mục hoặc sử dụng thuật toán tìm kiếm tốt hơn.

foreach (Record item in LargeCollection) 
{ 
    if (LookupCollection.Contains(item.Key)) 
    { 
     // Do something 
    } 
} 

Lưu ý. Danh sách tra cứu đã được sắp xếp.

Answer 1

Trong trường hợp chung nhất, hãy xem xét System.Collections.Generic.HashSet làm cấu trúc dữ liệu bảng tính mặc định "Chứa" của bạn, vì phải mất thời gian liên tục để đánh giá Contains.

Câu trả lời thực tế cho "Bộ sưu tập có thể tìm kiếm nhanh nhất" phụ thuộc vào kích thước dữ liệu cụ thể, yêu cầu đặt hàng, chi phí băm và tần suất tìm kiếm của bạn.

Answer 2

Nếu bạn không cần phải đặt hàng, hãy thử HashSet<Record> (mới vào NET 3.5)

Nếu bạn làm, sử dụng một List<Record> và gọi BinarySearch.

Answer 3

Bạn đã xem xét List.BinarySearch(item)?

Bạn đã nói rằng bộ sưu tập lớn của bạn đã được sắp xếp nên đây có vẻ là cơ hội hoàn hảo? Một băm chắc chắn sẽ là nhanh nhất, nhưng điều này mang lại những vấn đề riêng của mình và đòi hỏi nhiều chi phí hơn để lưu trữ.

Answer 4

Nếu bạn không lo lắng về việc kêu vo vo từng bit cuối cùng của hiệu suất, đề xuất sử dụng tìm kiếm nhị phân hoặc tìm kiếm nhị phân là rắn. Các tập dữ liệu của bạn không đủ lớn để điều này có thể là vấn đề 99% thời gian. Nhưng nếu đây chỉ là một trong hàng ngàn lần bạn sẽ thực hiện điều này và hiệu suất là rất quan trọng (và được chứng minh là không thể chấp nhận được bằng cách sử dụng tìm kiếm nhị phân), bạn chắc chắn có thể viết thuật toán của riêng mình mà đi các danh sách đã sắp xếp so sánh như bạn đã đi. Mỗi danh sách sẽ được đi nhiều nhất một lần và trong các trường hợp bệnh lý sẽ không tệ (một khi bạn đã đi tuyến đường này bạn có thể thấy rằng so sánh, giả sử đó là một chuỗi hoặc giá trị không tách rời khác, sẽ là chi phí thực tế và tối ưu hóa đó sẽ là bước tiếp theo).

Answer 5

Nếu có thể sắp xếp các mục của bạn thì có cách nhanh hơn để thực hiện việc này, sau đó thực hiện tra cứu chính thành một thẻ có thể bắt đầu hoặc b-tree. Mặc dù nếu bạn là các mục không thể sắp xếp, bạn có thể không thực sự đặt chúng vào một b-tree anyway.

Dù sao, nếu sắp xếp được sắp xếp cả hai danh sách thì đó chỉ là vấn đề đi bộ danh sách tra cứu theo thứ tự.

Walk lookup list 
    While items in check list <= lookup list item 
    if check list item = lookup list item do something 
    Move to next lookup list item 

Answer 6

Nếu bạn đang sử dụng Net 3.5, bạn có thể làm cho mã sạch sử dụng:

foreach (Record item in LookupCollection.Intersect(LargeCollection)) 
{ 
    //dostuff 
} 

Tôi không có Net 3.5 ở đây và vì vậy đây là chưa được kiểm tra. Nó dựa trên một phương pháp mở rộng. Không phải là LookupCollection.Intersect(LargeCollection) có lẽ không giống như LargeCollection.Intersect(LookupCollection) ... sau này có thể chậm hơn nhiều.

này giả LookupCollection là một HashSet

Answer 7

Giữ cả hai danh sách x và y theo thứ tự sắp xếp.

Nếu x = y, thực hiện hành động của bạn, nếu x < y, trước x, nếu y < x, chuyển y cho đến khi danh sách trống.

Thời gian chạy của ngã tư này là tỷ lệ thuận với min (kích thước (x), kích thước (y))

Đừng chạy() vòng lặp Chứa, đây là tỷ lệ thuận với x * y đó tồi tệ hơn nhiều.

Answer 8

Bạn nên đọc this blog tốc độ đó đã kiểm tra một số loại bộ sưu tập và phương pháp khác nhau cho từng loại sử dụng cả kỹ thuật đơn và đa luồng.

Theo kết quả, một tìm kiếm nhị phân trên danh sách và SortedList là những người biểu diễn hàng đầu liên tục chạy cổ-cổ khi nhìn lên một cái gì đó như là một "giá trị".

Khi sử dụng bộ sưu tập cho phép "khóa", Từ điển, ConcurrentDictionary, Hashset và HashTables thực hiện tổng thể tốt nhất.