Quelle est la structure de données la plus efficace pour stocker des séries chronologiques de matrices partiellement changeantes?

Question

Mon problème est que j'ai un tableau d'objets de taille N. après chaque fois (t + 1), certaines des valeurs du tableau peuvent ou ne peuvent pas changer. alors disons que t + 1 index 15 change mais tout le reste reste le même.

Quel est le moyen le plus efficace pour stocker quelque chose comme ça (en mémoire) en plus de simplement avoir un tableau de tableaux bien sûr? Je veux être en mesure d'obtenir toutes les valeurs de la matrice pour tout moment, par exemple getValues ​​(long time) de la manière la plus efficace possible.

Say pour 4 tableaux

temps 1 null null null xyz

temps 2 null null abc xyz

(notez que seulement abc a changé ici) mais nous toujours garder les valeurs du dernier indice du temps 1.

Answer 1

Ce que vous demandez est connu dans le domaine CS académique comme "tableaux partiellement persistants". Pour plus d'informations sur la persistance, voir the survey of Kaplan.

Une solution simple consiste à utiliser des arbres de recherche au lieu de tableaux. Vous pouvez utiliser des arborescences de recherche équilibrées purement fonctionnelles pour garantir que chaque lecture ou écriture prend O (lg n) dans le pire des cas (où n est la taille du tableau), au lieu de O (1). (Si vous conservez les versions horodatées dans un tableau extensible, l'ajout d'une nouvelle version est O (1) amorti et l'accès à une ancienne version est O (1) dans le pire des cas.)

Si vous n'êtes pas familier avec purement arbres de recherche fonctionnelle, vous pouvez lire this introduction to Clojure's persistent arrays. Ce sont des arbres purement fonctionnels indexés sur des entiers à largeur fixe (sous la forme d'un trie), et ont donc une profondeur fixe. Cela pourrait être la solution la plus rapide à votre problème, à la fois le pire des cas et le monde réel.

Les seuls autres tableaux partiellement persistants dont je suis conscient peuvent prendre plus de temps dans le pire des cas. Certains ont mieux amorti la complexité et certains ont une meilleure complexité attendue si les tableaux sont accessibles de différentes manières.