我有一个非常简单的数据结构（基本上是一个包含一些数组和单值的结构），但我需要记录数据结构的历史记录，以便我可以高效地获取数据结构的内容时间。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