Q: Оптимизированная структура данных для разветвленных и версионных объектов

Question

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

Например (немного надуманный пример) даны записи, такие как:

MySIMDIntristicsLib.v1~archMIPS.v1~fbsd.v1 
MySIMDIntristicsLib.v1~archMIPS.v2~fbsd.v1
MySIMDIntristicsLib.v1~archX86.v1~win.v1
MySIMDIntristicsLib.v1~archX86.v2~win.v1
MySIMDIntristicsLib.v1~archX86.v2~win.v2
MySIMDIntristicsLib.v2~archX86.v1~win.v1


// get latest across all branches 
get( Entity="MySIMDIntristicsLib", branch[(latest) "~"] ) 
returns: "MySIMDIntristicsLib.v2~archX86.v1~win.v1"


// get latest across  archMips/fbsd branch 
get( Entity="MySIMDIntristicsLib", branch[(latest) "archMIPS~fbsd"] ) 
returns: "MySIMDIntristicsLib.v1~archMIPS.v2~fbsd.v1"



// get earliest   for archX86 v2 branch 
get( Entity="MySIMDIntristicsLib", branch[(earliest) "archX86.v2~"] ) 
returns "MySIMDIntristicsLib.v1~archX86.v2~win.v1"

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

Я искал структуры данных в памяти для вышеупомянутого с хорошим Последним / Самым ранним временем доступа, но также и скоростью вставки / удаления спуска.

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

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

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

Answer 1

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

Если ваш список большой, вам нужно будет проиндексировать ваши ветки / версии, и вы можете сделать это, используя базу данных в памяти, такую ​​как H2 Database Engine, HSQLDB, CQEngine и т. Д.