Tìm nhanh một mục trong một hashtable hoặc trong danh sách được sắp xếp là nhanh hơn?

Question

Tìm nhanh một mục trong một hashtable hoặc trong danh sách được sắp xếp nhanh hơn?

Answer 1

Độ phức tạp của thuật toán là điều tốt để biết, và hashtables được gọi là 0 (1) trong khi một véc-tơ được sắp xếp (trong trường hợp của bạn là tốt hơn để sử dụng mảng được sắp xếp hơn danh sách). n) thời gian truy cập.

Nhưng bạn nên biết rằng ký pháp phức tạp cung cấp cho bạn thời gian truy cập cho N sẽ vô hạn. Điều đó có nghĩa là nếu bạn biết rằng dữ liệu của mình sẽ tiếp tục tăng, ký pháp phức tạp sẽ cung cấp cho bạn một số gợi ý về thuật toán đã chọn.

Khi bạn biết rằng dữ liệu của bạn sẽ giữ độ dài khá thấp: ví dụ chỉ có một vài mục trong mảng/có thể bắt đầu, bạn phải đi với đồng hồ và thước đo của mình. Vì vậy, có một thử nghiệm.

Ví dụ: trong một vấn đề khác: sắp xếp một mảng. Đối với một vài mục bong bóng sắp xếp thời gian O (N^2) có thể nhanh hơn .. các loại nhanh chóng, trong khi nó là (n log n) ..

Ngoài ra, phù hợp để câu trả lời khác, và tùy thuộc vào bạn mục, bạn phải cố gắng tìm hàm băm tốt nhất cho thể hiện hashtable của bạn. Nếu không, nó có thể dẫn đến hiệu suất xấu đáng kể để tra cứu trong hashtable của bạn (như đã chỉ ra trong câu trả lời của Hank Gay).

Chỉnh sửa: Hãy xem bài viết này để hiểu the meaning of Big O notation.

Answer 2

Trừ khi thuật toán băm là cực kỳ chậm (và/hoặc xấu), hàm bắt đầu sẽ nhanh hơn.

CẬP NHẬT: Khi người nhận xét đã chỉ ra, bạn cũng có thể bị suy giảm hiệu suất do quá nhiều va chạm không phải vì thuật toán băm của bạn kém nhưng đơn giản vì hashtable không đủ lớn. Hầu hết các triển khai thư viện (ít nhất là ở các ngôn ngữ cấp cao) sẽ tự động phát triển khả năng mở rộng của bạn đằng sau hậu trường - điều này sẽ gây ra hiệu suất chậm hơn mong đợi trên đoạn chèn kích hoạt tăng trưởng - nhưng nếu bạn đang phát triển cân nhắc.

Answer 3

Giả sử rằng theo 'danh sách được sắp xếp', bạn có nghĩa là 'bộ sưu tập được sắp xếp ngẫu nhiên, được sắp xếp'. Một danh sách có thuộc tính mà bạn chỉ có thể đi qua phần tử đó theo phần tử, điều này sẽ dẫn đến độ phức tạp O (N). Cách nhanh nhất để tìm một phần tử trong bộ sưu tập có thể lập chỉ mục được sắp xếp là tìm kiếm N-ary, O (logN), trong khi một hashtable mà không có collissions có độ phức tạp tìm thấy của O (1).

Answer 4

Trong một số trường hợp, nó phụ thuộc vào kích thước của bộ sưu tập (và ở mức độ thấp hơn, chi tiết triển khai). Nếu danh sách của bạn là rất nhỏ, 5-10 mục có thể, tôi đoán danh sách sẽ nhanh hơn. Nếu không xtofl có nó đúng.

Answer 5

HashTable sẽ hiệu quả hơn đối với danh sách chứa hơn 10 mục. Nếu danh sách có ít hơn 10 mục, chi phí do băm sẽ giảm nhiều hơn.

Trong trường hợp bạn cần từ điển nhanh nhưng cũng cần phải giữ các mục theo kiểu đặt hàng sử dụng OrderedDictionary. (.Net 2.0 trở lên)

Answer 6

Hoạt động get trong SortedList là O(log n) trong khi cùng một hoạt động e HashTable là O(1). Vì vậy, thường là, số HashTable sẽ nhanh hơn nhiều.Nhưng điều này phụ thuộc vào một số yếu tố:

• Kích thước của danh sách
• Hiệu suất của thuật toán băm
• Số va chạm/chất lượng của thuật toán băm

Answer 7

Nó phụ thuộc hoàn toàn về lượng dữ liệu bạn đã lưu trữ.

Giả sử bạn có đủ bộ nhớ để ném vào nó (vì vậy bảng băm đủ lớn), bảng băm sẽ định vị dữ liệu đích trong một khoảng thời gian cố định, nhưng cần tính băm sẽ thêm một số (cũng cố định) trên không.

Tìm kiếm danh sách được sắp xếp sẽ không có chi phí băm, nhưng thời gian cần thiết để thực hiện công việc thực sự định vị dữ liệu mục tiêu sẽ tăng khi danh sách tăng lên.

Vì vậy, nói chung, danh sách được sắp xếp thường sẽ nhanh hơn đối với các tập dữ liệu nhỏ. (Đối với các tập dữ liệu cực kỳ nhỏ thường xuyên bị thay đổi và/hoặc không thường xuyên được tìm kiếm, một danh sách được sắp xếp un được sắp xếp thậm chí có thể nhanh hơn, vì nó tránh được chi phí cho việc sắp xếp.) thời gian tìm kiếm sẽ làm lu mờ chi phí cố định của băm, và bảng băm trở nên nhanh hơn.

Nơi điểm ngắt đó sẽ thay đổi tùy thuộc vào bảng băm cụ thể của bạn và triển khai danh sách được sắp xếp-tìm kiếm. Chạy thử nghiệm và hiệu suất điểm chuẩn trên một số tập dữ liệu có kích thước thông thường để xem dữ liệu nào sẽ thực sự hoạt động tốt hơn trong trường hợp cụ thể của bạn. (Hoặc, nếu mã đã chạy "đủ nhanh", đừng. Chỉ cần sử dụng cái nào bạn thấy thoải mái hơn và đừng lo lắng về việc tối ưu hóa thứ gì đó không cần phải được tối ưu hóa.)