Java: cấu trúc dữ liệu được phiên bản?

Question

Tôi có cấu trúc dữ liệu khá đơn giản (về cơ bản là cấu trúc chứa một số mảng và giá trị đơn), nhưng tôi cần phải ghi lại lịch sử của cấu trúc dữ liệu để tôi có thể có được hiệu quả nội dung của cấu trúc dữ liệu tại bất kỳ thời điểm nào thời gian.

Có cách nào tương đối đơn giản để thực hiện việc này không? Cách tốt nhất tôi có thể nghĩ đến là đóng gói toàn bộ cấu trúc dữ liệu bằng cách xử lý tất cả các hoạt động đột biến bằng cách lưu trữ dữ liệu trong functional data structures, và sau đó cho mỗi hoạt động đột biến lưu vào bộ nhớ cấu trúc dữ liệu trong Bản đồ được lập chỉ mục bằng cách đặt hàng thời gian (ví dụ: TreeMap với thời gian thực dưới dạng khóa hoặc HashMap với bộ đếm hoạt động đột biến được kết hợp với một hoặc nhiều chỉ mục được lưu trữ trong ánh xạ thời gian thực/đánh dấu TreeMaps để hoạt động đột biến)

any đề xuất?

chỉnh sửa: Trong một trường hợp tôi đã có lịch sử dưới dạng một loạt giao dịch (đây là đọc các mục từ tệp dữ liệu) để tôi có thể phát lại, nhưng điều này có các bước O (n) (n = # giao dịch) mỗi khi tôi cần truy cập dữ liệu. Tôi đang tìm giải pháp thay thế.

Answer 1

Hoàn tác nhiều cấp có thể dựa trên mô hình (tức là cấu trúc dữ liệu) và một chuỗi các hành động. Mỗi hành động hỗ trợ hai hoạt động: "làm" và "hoàn tác". Để thực hiện một thay đổi trên mô hình, bạn đăng ký một hành động mới và "làm" nó. Điều này cho phép bạn "đi" qua lại trong lịch sử, nhưng trạng thái của mô hình tại một chỉ mục cụ thể không thể được truy cập trong thời gian không đổi.

Có thể điều gì đó như thế này sẽ áp dụng cho trường hợp của bạn?

Answer 2

Bạn đúng. Lưu trữ dữ liệu trong một cấu trúc dữ liệu thuần túy là cách để đi. Hỗ trợ bất cứ điều gì phức tạp vừa phải bằng cách sử dụng các hành động do/undo phụ thuộc vào lập trình viên đang nhận thức được tất cả các tác dụng phụ của mọi hoạt động, không quy mô và phá vỡ đóng gói.

Answer 3

Hoặc làm như bạn đã đề xuất hoặc có lớp cơ sở của một số loại với các lớp con đại diện cho các thay đổi khác nhau. Sau đó, có được lớp học thích hợp vào thời gian chạy bằng cách chuyển phiên bản/dấu thời gian/bất kỳ thứ gì đến một nhà máy đưa bạn trở lại đúng.

Answer 4

Nếu bạn chỉ lưu trữ một ít dữ liệu và không có nhiều thay đổi thì việc lưu trữ từng phiên bản là tốt.

Nếu bạn không cần truy cập vào phiên bản cũ của dữ liệu quá thường xuyên, tôi sẽ không lưu từng bộ nhớ cache, tôi chỉ làm cho nó để bạn có thể xây dựng lại nó.

Bạn có thể làm điều này bằng cách tiết kiệm đột biến như các giao dịch và phát lại các giao dịch (với khả năng ngăn chặn bất cứ lúc nào.

Vì vậy, bạn bắt đầu với một cấu trúc dữ liệu rỗng và bạn có thể nhận được một lệnh "Add" tiếp theo "Thay đổi" và "thêm" khác và sau đó có thể là "Xóa". Mỗi đối tượng trong số này sẽ chứa COPY (không phải là con trỏ đến cùng một đối tượng) của nội dung đang được thêm hoặc thay đổi. hoạt động vào danh sách đồng thời tắt bộ sưu tập của bạn.

Nếu bạn thấy rằng mình cần phiên bản tại dấu thời gian cũ hơn, bắt đầu bằng bộ sưu tập trống mới, phát lại cho đến khi bạn nhấn dấu thời gian đó rồi dừng lại và bạn có bộ sưu tập như lúc đó.Nếu đây là một ứng dụng rất dài và bạn thường cần truy cập các mục gần cuối, bạn có thể viết "Hoàn tác" cho từng đối tượng hoạt động thêm/thay đổi/xóa và thực sự biến đổi dữ liệu qua lại. Vì vậy, hãy tưởng tượng bạn có đối tượng dữ liệu của bạn và mảng đột biến này, bạn có thể dễ dàng chạy lên và xuống danh sách đột biến thay đổi đối tượng dữ liệu qua lại cho bất kỳ phiên bản nào bạn muốn. Bạn thậm chí có thể chứa nhiều đối tượng dữ liệu, chỉ cần tạo một đối tượng dữ liệu mới và chạy nó lên mảng đột biến (nghĩ về nó như là một dòng thời gian - nơi mỗi đột biến được lưu trữ sẽ chứa dấu thời gian hoặc số phiên bản) cho đến khi bạn nhận được với dấu thời gian bạn muốn - theo cách này bạn có thể có "mốc" mà bạn có thể truy cập ngay lập tức - ví dụ: nếu bạn chỉ định một cột mốc cho mỗi chuỗi bạn có thể làm cho phương thức addMutation được đồng bộ hóa và bộ sưu tập dữ liệu này sẽ trở thành 100% threadsafe . Lưu ý rằng nếu bạn thực sự trả về đối tượng dữ liệu, bạn chỉ nên trả về một bản sao của dữ liệu - nếu không thì lần sau bạn đột biến mốc đó, nó sẽ làm biến đổi đối tượng dữ liệu bạn trả về.

Hmm, bạn cũng có thể bao gồm chức năng "Rollup" - nếu bạn quyết định không cần truy cập vào đuôi (vài giao dịch đầu tiên), bạn có thể áp dụng chúng cho cấu trúc "Bắt đầu" và sau đó xóa chúng - từ đó bạn sao chép cấu trúc bắt đầu để bắt đầu từ đầu thay vì luôn bắt đầu với một cấu trúc dữ liệu rỗng.

Con người, đây là một mẫu tuyệt vời - bây giờ tôi muốn triển khai nó.

Answer 5

Ứng dụng sẽ chạy trong bao lâu? Có vẻ như bạn có thể làm những gì bạn đề nghị - chơi các giao dịch trở lại - nhưng nhớ cache cấu trúc dữ liệu và danh sách các giao dịch tại các thời điểm cụ thể trong thời gian (mỗi giờ hoặc mỗi ngày?) Để giảm bớt nỗi đau khi phải đi qua các hoạt động O (n) mỗi khi bạn cần xây dựng lại bộ sưu tập từ đầu.

Được cấp, chắc chắn có một sự cân bằng giữa không gian (bộ nhớ cache chiếm) và số lượng hoạt động cần thiết để xây dựng lại nó, nhưng hy vọng bạn sẽ có thể tìm thấy một phương tiện vui vẻ cho nó.

Answer 6

Bạn nên sử dụng một số cấu trúc dữ liệu liên tục không thay đổi và dựa trên chia sẻ cấu trúc (tức là các phần của cấu trúc dữ liệu không thay đổi giữa các phiên bản chỉ được lưu trữ một lần).

Tôi tạo ra một nguồn thư viện mở Java của cấu trúc dữ liệu như ở đây:

http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent

Chúng được phần nào lấy cảm hứng từ cấu trúc dữ liệu dai dẳng Clojure, mà cũng có thể phù hợp cho mục đích của bạn (họ cũng được viết bằng Java).