Cấu trúc dữ liệu: Tôi nên sử dụng những điều kiện nào?

Question

Đây không phải là một câu hỏi khó, nhưng tôi chỉ muốn một người nào đó trả lời nó trước khi tôi tiếp tục. Tôi chỉ cần quyết định cấu trúc dữ liệu nào sẽ sử dụng dựa trên các hoạt động được mong đợi này:

1. Cần lặp lại thường xuyên theo thứ tự sắp xếp (bắt đầu từ đầu).
2. Cần phải xóa/khôi phục các phần tử tùy ý từ/chế độ xem được sắp xếp.
3. Sau đó tôi sẽ thường xuyên sử dụng dữ liệu và làm việc với nhiều chế độ xem được sắp xếp.
4. Ngoài ra sau này tôi sẽ thường xuyên thay đổi vị trí của các phần tử trong chế độ xem được sắp xếp của chúng.

Đây là trong Java, nhân tiện.

Đoán tốt nhất của tôi là tôi sẽ hoặc đang cuộn một số Bộ băm được liên kết tùy chỉnh (để sắp xếp các liên kết theo thứ tự được sắp xếp) hoặc có thể chỉ sử dụng Tập hợp cây. Nhưng tôi vẫn chưa hoàn toàn chắc chắn. Khuyến nghị?

Chỉnh sửa: Tôi đoán vì tùy ý xóa/khôi phục, tôi có lẽ nên gắn bó với Tập hợp cây, đúng không?

Thực ra, không nhất thiết. Hmmm ...

Answer 1

Về lý thuyết, tôi muốn nói rằng cấu trúc dữ liệu phù hợp là một cây đa chiều - tốt hơn là giống như cây B +. Theo truyền thống, đây là cấu trúc dữ liệu dựa trên đĩa, nhưng bộ nhớ chính hiện đại có nhiều đặc điểm tương tự do các lớp bộ nhớ đệm và bộ nhớ ảo.

Lặp lại thứ tự của cây B + rất hiệu quả vì (1) bạn chỉ lặp qua danh sách liên kết các nút lá - các nút nhánh là không cần thiết và (2) bạn có được vị trí cực kỳ tốt.

Tìm, xóa và chèn các phần tử tùy ý là nhật ký (n) như với bất kỳ cây cân bằng nào, mặc dù có các yếu tố không đổi khác nhau.

Khu nghỉ dưỡng trong cây chủ yếu là lựa chọn thuật toán mang lại hiệu suất tốt khi hoạt động trên danh sách khối liên kết (nút lá), giảm thiểu nhu cầu sử dụng nút lá - biến thể của quicksort hoặc mergesort có vẻ như ứng cử viên. Khi các mục được sắp xếp trong các nút nhánh, chỉ cần đẩy thông tin tóm tắt trở lại thông qua các nút lá.

NHƯNG - thực tế, đây chỉ là điều bạn sẽ làm nếu bạn chắc chắn rằng mình cần nó. Tỷ lệ cược là tốt mà bạn nên sử dụng một số container tiêu chuẩn. Thuật toán/tối ưu hóa cấu trúc dữ liệu là loại tối ưu hóa tốt nhất, nhưng nó vẫn có thể sớm.

Answer 2

Tiêu chuẩn LinkedHashSet hoặc LinkedMultiset từ bộ sưu tập của Google nếu bạn muốn cấu trúc dữ liệu lưu trữ không phải giá trị duy nhất.