Java: версии данных структуры данных?

У меня есть структура данных, которая довольно проста (в основном структура, содержащая некоторые массивы и одиночные значения), но мне нужно записать историю структуры данных, чтобы я мог эффективно получать содержимое структуры данных в любой точке вовремя.

Существует ли относительно простой способ сделать это?

Лучший способ, который я могу представить, - инкапсулировать всю структуру данных на то, что обрабатывает все мутирующие операции, сохраняя данные в функциональных структурах данных, а затем для каждой операции мутации кэширование копии структуры данных в Map, индексированной по времени (например, TreeMap с реальным временем в виде ключей или HashMap с счетчиком операций мутации в сочетании с одним или несколькими индексами, хранящимися в картировании TreeMaps в реальном времени/количество меток/и т.д. для операций мутации)

любые предложения?

edit: В одном случае у меня уже есть история как серия транзакций (это чтение элементов из файла данных), поэтому я могу их воспроизвести, но это занимает O (n) шагов ( n = количество транзакций) каждый раз, когда мне нужно получить доступ к данным. Я ищу альтернативы.

Ответ 1

Вы должны использовать некоторую форму постоянной структуры данных, которая является неизменной и основана на структурном совместном использовании (то есть, чтобы части структуры данных, которые не изменяются между версиями, сохраняются только один раз).

Я создал библиотеку Java с открытым исходным кодом таких структур данных здесь:

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

Они были несколько вдохновлены Clojure постоянными структурами данных, которые также могут быть подходящими для ваших целей (они также написаны на Java).

Ответ 2

Вы правы. Сохранение данных в чисто функциональной структуре данных - это путь. Поддержка любого умеренно сложного использования операций do/undo зависит от того, что программист знает обо всех побочных эффектах каждой операции, которая не масштабирует и не прерывает инкапсуляцию.

Ответ 3

Либо сделайте так, как вы уже предложили, либо получите базовый класс с подклассами, которые представляют разные изменения. Затем верните класс во время выполнения, передав версию/временную метку/независимо от factory, которая вернет вам правильный.

Ответ 4

Если вы только сохраняете немного данных и не имеете большого количества изменений, то сохранение каждой версии в порядке.

Если вам не нужно слишком часто обращаться к старой версии данных, я бы не кэшировал каждую из них, я бы просто сделал это, чтобы вы могли перестроить его.

Вы можете сделать это, сохранив мутации в качестве транзакций и переигровки транзакций (с возможностью остановки в любой точке.

Итак, вы начинаете с пустой структуры данных, и вы можете получить команду "Добавить", а затем "Изменить" и другую "добавить", а затем, возможно, "Удалить". Каждый из этих объектов будет содержать COPY (не указатель на тот же объект) добавляемой или измененной вещи.

Вы объединяете каждую операцию в список и одновременно мутируете свою коллекцию.

Если вы обнаружите, что вам нужна версия с более старой отметкой времени, начните с новой пустой коллекции, повторите ее, пока вы не нажмете эту метку времени, а затем остановитесь, и у вас есть коллекция, как это было бы в то время.

Если это было очень долгое приложение, и вам часто приходилось обращаться к элементам ближе к концу, вы могли бы написать "Отменить" для каждого объекта операции добавления/изменения/удаления и фактически мутировать данные взад и вперед.

Итак, представьте себе, что у вас есть объект данных и этот массив мутаций, вы можете легко запускать и изменять список мутаций, изменяя объект данных взад и вперед на любую желаемую версию.

Вы даже можете содержать несколько объектов данных, просто создайте новый пустой и запустите его в мутационном массиве (подумайте об этом как о временной шкале - где каждая сохраненная мутация будет содержать временную метку или номер версии), пока вы ее не получите к метке времени, которую вы хотите - таким образом, вы могли бы иметь "вехи", которые вы могли бы достичь мгновенно - например, если вы выделили одну веху для каждого потока, вы можете сделать метод addMutation синхронизированным, и этот сбор данных станет 100% -ным потокобезопасным.

Обратите внимание, что если вы действительно возвращаете объект данных, вы должны возвращать только копию данных, иначе в следующий раз, когда вы изменили эту веху, он будет мутировать возвращаемый объект данных.

Хм, вы могли бы также включить функциональность "Rollup" - если вы когда-нибудь решите, что вам не нужен доступ к хвосту (первые несколько транзакций), вы можете применить их к структуре "Пуск", а затем удалить их - с этого момента вы копируете начальную структуру, чтобы начать с самого начала, а не всегда начинать с пустой структуры данных.

Человек, это потрясающий шаблон - теперь я хочу его реализовать.

Ответ 5

Многоуровневая отмена может основываться на модели (т.е. структуре данных) и последовательности действий. Каждое действие поддерживает две операции: "делать" и "отменять". Чтобы выполнить изменение модели, вы регистрируете новое действие и "делаете" его. Это позволяет вам "ходить" вперед и назад в истории, но состояние модели по конкретному индексу невозможно получить за постоянное время.

Возможно, что-то подобное применимо к вашей ситуации?

Ответ 6

Как долго будет работать приложение?

Кажется, вы могли бы сделать то, что вы предложили, - сыграть транзакции назад, - но кешировать структуру данных и список транзакций в определенные моменты времени (каждый час или каждый день?), чтобы облегчить боль, через операции O (n) каждый раз, когда вам нужно перестроить коллекцию с нуля.

Конечно, существует определенная компромисс между пространством (который занимает кеш) и количеством операций, необходимых для его повторной сборки, но, надеюсь, вы сможете найти для него счастливую среду.