Java：版本化的数据结构？ [英] Java: versioned data structures?

问题描述

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

有没有一个比较直接的方法呢？

我可以想到的最好的方法将通过将数据存储在功能数据中来封装整个数据结构，处理所有突变操作结构，然后对于每个突变操作，在由时间排序索引的Map（例如，具有实时作为键的TreeMap）或具有突变操作的计数器的HashMap中组合数据结构的副本缓存一个或多个更多索引存储在TreeMaps中映射实时/滴答计数等到变异操作）

任何建议？

编辑：在一种情况下，我已经将历史记录作为一系列事务（这是从数据文件读取项目），所以我可以重播它们，但是每次我都需要O（n）个步骤（n =＃个事务）需要访问数据。我正在寻找替代品。

解决方案

你应该使用一些永久性的数据结构是不可变的，基于结构共享（即使数据结构的不在版本之间变化的部分只能存储一次）。

我在这里创建了一个这样的数据结构的开源Java库：

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

这些被Clojure持久的数据结构所启发，这些结构也可能适合您的目的（也用Java编写）。

I have a data structure that is pretty simple (basically a structure containing some arrays and single values), but I need to record the history of the data structure so that I can efficiently get the contents of the data structure at any point in time.

Is there a relatively straightforward way to do this?

The best way I can think of would be to encapsulate the whole data structure with something that handles all the mutating operations by storing data in functional data structures, and then for each mutation operation caching a copy of the data structure in a Map indexed by time-ordering (e.g. a TreeMap with real time as keys, or a HashMap with a counter of mutation operations combined with one or more indexes stored in TreeMaps mapping real time / tick count / etc. to mutation operations)

any suggestions?

edit: In one case I already have the history as a series of transactions (this is reading items from a data file) so I can replay them, but this takes O(n) steps (n = # of transactions) every time I need to access the data. I'm looking for alternatives.

解决方案

You should use some form of persistent data structure that is immutable and is based on structural sharing (i.e. so that the parts of the data structure which do not change between versions only get stored once).

I created an open source Java library of such data structures here:

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

These were somewhat inspired by Clojure's persistent data structures, which might also be suitable for your purposes (they are also written in Java).

这篇关于Java：版本化的数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！