Cấu trúc dữ liệu hiệu quả để truy cập ngẫu nhiên nhanh, tìm kiếm, chèn và xóa

Question

Tôi đang tìm cấu trúc dữ liệu (hoặc cấu trúc) cho phép tôi giữ cho tôi danh sách thứ tự các số nguyên, không trùng lặp, với chỉ mục và giá trị trong cùng một phạm vi.

tôi cần bốn hoạt động chính là hiệu quả, để thô quan trọng:

1. lấy giá trị từ một chỉ số cho trước
2. tìm chỉ số của một giá trị nhất định
3. chèn một giá trị tại một đưa chỉ số
4. xóa một giá trị tại một chỉ số cho trước

Sử dụng một mảng tôi có 1 tại O (1), nhưng 2 là O (N) và chèn và xóa là tốn kém (O (N) là tốt, tôi tin).

Danh sách liên kết có O (1) chèn và xóa (khi bạn có nút), nhưng 1 và 2 là O (N) do đó phủ nhận lợi ích.

Tôi đã cố giữ hai mảng [index] = value và b [value] = index, biến 1 và 2 thành O (1) nhưng chuyển 3 và 4 thành hoạt động tốn kém hơn.

Có cấu trúc dữ liệu nào phù hợp hơn cho điều này không?

Answer 1

Tôi sẽ sử dụng red-black tree để ánh xạ khóa cho giá trị. Điều này cung cấp cho bạn O (log (n)) cho 1, 3, 4. Nó cũng duy trì các khóa theo thứ tự sắp xếp.

Đối với 2, tôi sẽ sử dụng bảng băm để ánh xạ giá trị cho các khóa, cung cấp cho bạn hiệu suất O (1). Nó cũng bổ sung thêm O (1) chi phí để giữ bảng băm được cập nhật khi thêm và xóa các khóa trong cây đỏ đen.

Answer 2

Cách sử dụng mảng được sắp xếp với tìm kiếm nhị phân?

Chèn và xóa chậm. nhưng với thực tế là dữ liệu là số nguyên đơn giản có thể được tối ưu hóa với các cuộc gọi đến memcpy() nếu bạn đang sử dụng C hoặc C++. Nếu bạn biết kích thước tối đa của mảng, bạn thậm chí có thể tránh bất kỳ phân bổ bộ nhớ nào trong quá trình sử dụng mảng, vì bạn có thể preallocation nó đến kích thước tối đa.

Cách tiếp cận "tốt nhất" tùy thuộc vào số lượng mặt hàng bạn cần lưu trữ và tần suất bạn sẽ cần chèn/xóa so với tìm kiếm. Nếu bạn hiếm khi chèn hoặc xóa một mảng được sắp xếp với O (1) truy cập vào các giá trị chắc chắn là tốt hơn, nhưng nếu bạn chèn và xóa thường xuyên một cây nhị phân có thể tốt hơn mảng. Đối với một đủ nhỏ n mảng có nhiều khả năng đập cây trong mọi trường hợp.

Nếu kích thước bộ nhớ là mối quan tâm, mảng cũng tốt hơn so với cây. Cây cũng cần phải cấp phát bộ nhớ cho mỗi mục mà chúng lưu trữ và chi phí cấp phát bộ nhớ có thể có ý nghĩa khi bạn chỉ lưu trữ các giá trị nhỏ (số nguyên).

Bạn có thể muốn cấu hình nhanh hơn, sao chép các số nguyên nếu bạn chèn/xóa từ mảng đã sắp xếp hoặc cây có phân bổ bộ nhớ (de).

Answer 3

Howabout a Treemap? log (n) cho các hoạt động được mô tả.

Answer 4

Tôi thích cây nhị phân cân bằng rất nhiều. Đôi khi chúng chậm hơn so với bảng băm hoặc các cấu trúc khác, nhưng chúng có thể dự đoán được nhiều hơn; chúng thường là O(log n) cho tất cả các hoạt động. Tôi khuyên bạn nên sử dụng số Red-black tree hoặc AVL tree.

Answer 5

Tôi không biết bạn đang sử dụng ngôn ngữ nào, nhưng nếu là Java, bạn có thể tận dụng LinkedHashMap hoặc một Bộ sưu tập tương tự. Nó có tất cả các lợi ích của Danh sách và Bản đồ, cung cấp thời gian liên tục cho hầu hết các hoạt động và có dấu chân bộ nhớ của một con voi. :)

Nếu bạn không sử dụng Java, ý tưởng về LinkedHashMap có lẽ vẫn phù hợp với cấu trúc dữ liệu có thể sử dụng được cho vấn đề của bạn.

Answer 6

Nếu bạn đang làm việc trong .NET, sau đó theo các tài liệu MS http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

• SortedDictionary và SortedList cả hai đều có O (log n ) để thu hồi
• SortedDictionary đã O (log n ) để chèn và xóa các hoạt động, trong khi SortedList có O (n).

Hai điểm khác nhau theo mức sử dụng bộ nhớ và tốc độ chèn/xóa. SortedList sử dụng ít bộ nhớ hơn SortedDictionary. Nếu SortedList được điền tất cả cùng một lúc từ dữ liệu được sắp xếp, nó sẽ nhanh hơn SortedDictionary. Vì vậy, nó phụ thuộc vào tình hình mà thực sự là tốt nhất cho bạn.

Ngoài ra, đối số của bạn cho Danh sách được liên kết không thực sự hợp lệ vì nó có thể là O (1) để chèn, nhưng bạn phải duyệt qua danh sách để tìm điểm chèn, vì vậy nó thực sự không.

Answer 7

Làm cách nào để đạt được 2 bằng RB-cây? Chúng tôi có thể làm cho họ đếm con của họ với mọi hoạt động chèn/xóa. Điều này không làm cho các hoạt động này kéo dài lâu hơn đáng kể. Sau đó, xuống cây để tìm nguyên tố thứ i có thể trong thời gian đăng nhập. Nhưng tôi thấy không thực hiện phương pháp này trong java cũng không stl.

Answer 8

Sử dụng véc tơ để truy cập mảng.

Sử dụng bản đồ làm chỉ mục tìm kiếm cho chỉ số vào vectơ.

• cho một subscript lấy giá trị từ O vector (1)
• cho một chìa khóa, sử dụng bản đồ để tìm subscript giá trị. O (LNN)
• chèn một giá trị, đẩy lùi trên O vector (1) phân bổ dần, chèn subscript vào bản đồ O (LNN)
• xóa một giá trị, xóa từ O bản đồ (lnN)