Q: Optimierte Datenstruktur für Branched und Versioned Entities

Question

Gegeben eine Entität (sagen Sie eine Datei oder eine Bibliothek/ein Paket), die ihre Versionen und Zweige im Laufe der Zeit entwickeln kann, auf der Suche nach einer optimierten Datenstruktur, die ich durch die Versionen navigieren kann zu einer bestimmten Instanz der Entität.

Zum Beispiel (ein bisschen konstruiertes Beispiel) gegeben Einträge wie:

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" 

Ich vermute, so etwas gibt es bereits (seit Paketverwaltung oder Quellcodeverwaltung zu der oben genannten Zugriffssemantik ähnlich nutzt).

Ich suchte nach In-Memory-Datenstrukturen für die oben genannten mit guter spätester/frühester Zugriffszeit, sondern auch Sinkflug einfügen/entfernen Geschwindigkeit.

In einer brutalen Kraft Ansatz, denke ich, dass das oben mit Min Max heap für jeden Zweig implementiert werden kann, die Versionen haben kann.

Allerdings kann es da draußen schon etwas Besseres geben. ich meine übliche Quelle für diese Art von Dingen auch geprüft, Redisson - aber nicht sehen, wenn es eine explizite Implementierung der Datenstruktur ist oben für die oben

Der DSL meiner eigenen Konstruktion ist, hat wahrscheinlich einige Löcher Auch wenn es bessere DSLs/APIs für diese Art des Datenzugriffs gibt - würde ich gerne auch lernen.

Answer 1

Wenn Ihre Liste klein ist, ist es wahrscheinlich die schnellste Lösung, eine sortierte Sammlung Ihrer Entitäten zu scannen, die nicht gewünschten zu filtern oder einfach die erste zu finden, die Ihren Kriterien entspricht (zB können Sie über Ihre Entitäten oben iterieren) umgekehrte Reihenfolge und schnappen Sie sich die erste "archMIPS ~ fbsd", um die "neueste" zu bekommen.

Wenn Ihre Liste ist groß dann werden Sie Ihre Zweige/Versionen indizieren möchten und Sie können dies tun, eine In-Memory-Datenbank wie H2 Database Engine, HSQLDB, CQEngine usw.