J'ai une structure de données assez simple (essentiellement une structure contenant des tableaux et des valeurs simples), mais je dois enregistrer l'historique de la structure de données afin que je puisse obtenir efficacement le contenu de la structure de données à tout moment. à temps.
Y a-t-il un moyen relativement simple de le faire?
La meilleure façon dont je peux penser serait d'encapsuler toute la structure de données avec quelque chose qui gère toutes les opérations de mutation en stockant des données dans structures de données fonctionnelles , puis pour chaque opération de mutation en cache une copie de la structure de données dans une carte indexée par la commande horaire (par exemple, un Treemap avec des clés en temps réel, ou un hashmap Avec une vente d'opérations de mutation combinées à un ou plusieurs index stockés dans TreeMaps mappant la cartographie / nombre en temps réel / etc. à des opérations de mutation)
Toute suggestion?
6 Réponses :
Un annulation multi-niveaux peut être basé sur un modèle (c.-à-d. Structure de données) et une séquence d'actions. Chaque action prend en charge deux opérations: "faire" et "annuler". Pour effectuer une modification du modèle, vous enregistrez une nouvelle action et "faire". Cela vous permet de "marcher" de l'histoire, mais l'état du modèle à un indice spécifique n'est pas accessible en temps constant.
Peut-être que quelque chose comme ça serait applicable à votre situation?
Merci: J'ai déjà des antécédents d'opérations que je peux rejouer, mais bien sûr, cela nécessite des opérations O (n) pour accéder à l'état du modèle à un moment arbitraire (besoin de rejouer toutes les opérations avant le point de question)
Vous êtes correct. Stocker les données dans une structure de données purement de fonction est la voie à suivre. Soutenir tout ce qui concerne modérément compliqué à l'aide des actions de DO / annulaires dépend du programmeur en cours de conscience de tous les effets secondaires de chaque opération, ce qui ne fait pas échouer et casse l'encapsulation.
Soit comme vous avez déjà suggéré ou avoir une classe de base d'une sorte avec des sous-classes qui représentent les différents changements. Ensuite, obtenez la classe appropriée au moment de l'exécution en passant la version / horodatage / quoi que ce soit pour une usine qui vous remet la bonne.
Si vous ne stockez qu'un peu de données et que vous n'avez pas beaucoup de modifications, le stockage de chaque version est bien.
Si vous n'avez pas besoin d'accéder trop souvent à l'ancienne version des données, je ne me cache pas si vous ne le feriez pas, je voudrais simplement le faire afin que vous puissiez vous reconstruire.
Vous pouvez le faire en enregistrant des mutations comme transactions et rejouer les transactions (avec la possibilité de s'arrêter à tout moment.
Vous démarrez donc avec une structure de données vide et vous pourriez obtenir une instruction "Ajouter" suivie d'un "changement" et d'une autre "Ajouter", puis peut-être une "Supprimer". Chacun de ces objets contiendrait une copie (pas un pointeur sur le même objet) de la chose ajoutée ou modifiée.
Vous concaténeriez chaque opération dans une liste tout en partant en même temps votre collection.
Si vous trouvez que vous avez besoin d'une version à un horodatage plus ancien, commencez par une nouvelle collection vide, rejouez jusqu'à ce que vous ayez frappé cet horodatage, puis vous arrêtez et vous avez la collection telle qu'elle serait à cette époque.
S'il s'agissait d'une application très longue en cours d'exécution et que vous aviez souvent besoin d'accéder à des articles à proximité de la fin, vous pouvez écrire un "Annuler" pour chaque objet d'ajout / modification / Supprimer de la modification des données d'avant entier.
Imaginez donc que vous avez votre objet de données et cette gamme de mutations, vous pouvez facilement exécuter la liste de mutation de la modification de l'objet de données en arrière vers une version souhaitée.
Vous pouvez même contenir plusieurs objets de données, créez simplement une nouvelle carte vide et exécutez-le dans la matrice de mutation (pensez-y comme une chronologie - où chaque mutation stockée contiendrait un chronomètre ou un numéro de version) jusqu'à ce que vous l'obtenez. À l'horodatage que vous voulez - de cette façon, vous pouvez avoir des "jalons" que vous pourriez atteindre instantanément - par exemple, si vous avez alloué une étape importante pour chaque thread, vous pouvez rendre la méthode addmutation synchronisée et cette collection de données deviendrait 100% threadsafe.
Notez que si vous retournez l'objet de données, vous ne devez renvoyer qu'une copie des données - sinon la prochaine fois que vous avez muté cette étape, elle muterait l'objet de données que vous avez retourné.
hmm, vous pouvez également inclure la fonctionnalité "Rollupt" - si vous décidez que vous n'ayez pas besoin d'accéder à la queue (les premières transactions), vous pouvez les appliquer à une structure "Démarrer", puis supprimez-les-- À partir de ce moment-là, copiez la structure de démarrage pour commencer à partir du début plutôt que de toujours commencer par une structure de données vide.
homme, c'est un motif génial - maintenant je veux le mettre en œuvre.
Combien de temps la demande sera-t-elle en marche?
On dirait que vous pouviez faire ce que vous avez suggéré - Jouer les transactions - mais mettre en cache la structure de données et la liste des transactions à des points particuliers à temps (toutes les heures ou tous les jours?) Pour alléger la douleur de devoir aller à travers O (n) des opérations à chaque fois que vous devez reconstruire la collection à partir de zéro.
accordé, il existe définitivement un compromis entre l'espace (que le cache prend) et le nombre d'opérations nécessaires pour le reconstruire, mais j'espère que vous pourrez trouver un support heureux pour cela.
Vous devez utiliser une forme de structure de données persistante qui est immuable et repose sur le partage structurel (c'est-à-dire que les parties de la structure de données qui ne changent pas entre versions ne sont stockées qu'une fois stockées).
J'ai créé une bibliothèque Java open source de ces structures de données ici:
http: // code.google.com/p/mikeralib/source/browse/#ssvn/trunk/mikera/src/mikera/persistent
Celles-ci étaient quelque peu inspirées des structures de données persistantes de Clojure, qui pourraient également convenir à vos besoins (elles sont également écrites en Java).