我有一個非常簡單的數據結構（基本上是一個包含一些數組和單值的結構），但我需要記錄數據結構的歷史記錄，以便我可以高效地獲取數據結構的內容時間。Java：版本化的數據結構？
有沒有比較直接的方法來做到這一點？
我能想到的最好的方法是用一些處理所有變異操作的東西封裝整個數據結構，將數據存儲在functional data structures中，然後對每個變異操作在Map索引中緩存數據結構的副本通過時間排序（例如，具有實時時間的TreeMap作爲關鍵字，或具有突變操作的計數器的HashMap與結合存儲在TreeMaps中的一個或多個索引結合實時/滴答計數等映射到突變操作）
任何建議？在一個案例中，我已經有一系列事務的歷史（這是從數據文件中讀取項目），所以我可以重放它們，但是這需要O（n）個步驟（n =＃...）。交易）每次我需要訪問數據。我正在尋找替代品。
多級撤消可以基於模型（即數據結構）和一系列操作。每個操作都支持兩種操作：「執行」和「撤消」。要對模型進行更改，請註冊一個新操作並「執行」。這允許您在歷史中來回「走動」，但是在特定索引處的模型狀態不能以恆定時間訪問。
也許這樣的事情會適用於您的情況？
你是對的。將數據存儲在純功能數據結構中是一種可行的方法。使用do/undo動作支持任何適度複雜的任何事情都依賴於程序員意識到每個操作的所有副作用，它不會縮放封裝。
既可以按照您的建議操作，也可以使用代表不同變化的子類的基類。然後通過將版本/時間戳/任何東西傳遞給工廠，讓您返回正確的類，從而在運行時獲得適當的類。
如果你只是存儲一點點的數據，沒有太多的改變，那麼存儲每個版本都可以。
如果你不需要經常訪問舊版本的數據，我不會緩存每一個數據，我只是讓它可以重建它。
你可以通過保存的突變事務和重播交易（與停在任意點的能力做到這一點。
所以，你開始用空的數據結構，你可能會得到一個「添加」指令之後一個「更改」和另一個「添加」，然後可能是一個「刪除」。這些對象中的每一個都將包含一個COPY（不是指向同一對象的指針）被添加或更改的東西
您將連接每個操作變成列表，同時突變你的收藏
如果你發現你需要一箇舊版本的時間戳，從一個新的空集合開始，重放直到你點擊該時間戳然後停止，並且你擁有當時的集合。
如果這是一個非常長時間運行的應用程序，並且您經常需要訪問接近結尾的項目，則可以爲每個添加/更改/刪除操作對象編寫一個「撤消」，並實際來回地變更數據。所以想象你有你的數據對象和這個突變數組，你可以輕鬆地在突變列表中上下運行，將數據對象來回更改爲任何你想要的版本。你甚至可以包含多個數據對象，只需創建一個新的空對象並將其運行到突變數組（將其視爲時間軸 - 每個存儲的突變將包含時間戳或某個版本號），直到獲得它到你想要的時間戳 - 這樣你就可以擁有你可以立即到達的「里程碑」 - 例如，如果你爲每個線程分配了一個里程碑，你可以使addMutation方法同步，並且這個數據集合將成爲100％線程安全。
請注意，如果您實際返回數據對象，則應只返回數據的副本 - 否則，下次您突變該里程碑時，它會改變您返回的數據對象。嗯，你也可以包含「Rollup」功能 - 如果你決定不需要訪問尾部（前幾個事務），你可以將它們應用到「開始」結構，然後刪除它們 - 從那時起，您將複製起始結構以從頭開始，而不是始終以空的數據結構開始。
男人，這是一個很棒的模式 - 現在我想實現它。
應用程序將運行多久？
您似乎可以按照您的建議進行操作 - 回放事務 - 但在特定時間點（每小時或每天）緩存數據結構和事務處理列表，以緩解必須每次需要從頭開始重建集合時，都要經過O（n）操作。當然，在空間（緩存佔用）和重新構建它所需的操作數量之間肯定存在權衡，但希望您能夠爲它找到一個愉快的媒介。
您應該使用某種形式的永久性數據結構，這種結構是不可變的並且基於結構共享（即，使得數據結構中不會在版本之間更改的部分僅存儲一次）。
我創造了這樣的數據結構的一個開源的Java庫在這裏：
http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent
這些都一定程度上受到Clojure的持久數據結構的啓發，這也可能是適合您的需要（它們也被寫入使用Java）。
謝謝：我已經有了可以重放的操作歷史，但是當然這需要O（n）操作來在任意時間點訪問模型的狀態（需要在點之前重放所有操作有問題） – 2010-06-11 17:22:29