Parcours efficace d'une liste de modifications

Question

J'ai une liste de modifications apportées à une liste - Ajouts et Suppressions. La liste pourrait être énorme - disons 10 000 articles.

Je souhaite connaître l'état de la liste après le changement 9'000.

Je pourrais parcourir la liste depuis le début jusqu’à changer 9'000. Cela me semble un peu long.

Je pourrais garder une liste d'éléments et enregistrer quand ils sont ajoutés et quand ils sont supprimés, puis parcourez cette liste pour voir ce qu'il y a dans la liste à un changement particulier. Si les ajouts et les suppressions étaient également probables, je diviserais par deux le nombre d’éléments de la liste que j’aurais besoin de parcourir ...

Mais la notation Big O indique que réduire de moitié la taille du problème ne rend pas les choses plus efficaces (si je l’ai bien compris).

Je pourrais mettre en cache l’état de la liste à chaque 100e ou 1000e changement ... mais encore une fois, le grand O dit que diviser le nombre d’articles par "n" ne rend pas les choses plus efficaces.

Alors, quel est le moyen efficace de le faire? Existe-t-il un moyen efficace de le faire?

Plus de détails: En particulier, je suis en train de suivre les allocations / désallocations de mémoire dans un allocateur personnalisé. Chaque allocation / désallocation est un événement de la liste. Chaque allocation a un identifiant unique. J'aimerais savoir ce qui est actuellement alloué après (par exemple) 9 000 événements.

Ma première idée a été de stocker, pour chaque identifiant, l'événement auquel il a été attribué et l'événement auquel il a été désalloué. Ensuite, parcourir cette liste jusqu'à la première allocation dont l'événement alloc est supérieur à 9 000. Mais, comme je l'ai dit, cela ne ferait que réduire de moitié le nombre d'éléments qu'il me faudrait parcourir.

J'aime le point soulevé par Mike F - marcher à partir du 100ème article le plus proche est un temps constant ...

Answer 1

Si vous mettez en cache l’état de la liste à chaque Xième modification, vous pouvez effectuer une opération binaire pour obtenir deux états mis en cache délimitant la modification recherchée. Ensuite, vous parcourez au maximum X éléments pour accéder à l’élément. lui-même. C'est O (log N), plus ou moins.

Mais plus généralement, réduire le gros problème de complexité est le moyen, pas la fin. Si votre liste contient généralement 10 000 éléments, vous devez vous inquiéter de la rapidité avec N = 10 000, soit en réduisant la complexité, soit en la rendant simplement plus rapide.

Modifier: Oups, je viens de lire votre question plus attentivement. Si vous cachez l'état tous les (par exemple) 100 articles, vous n'effectuez aucune recherche et vous n'avez même pas besoin d'effectuer une opération de hachage binaire; vous passez directement à l'état mis en cache le plus proche et parcourez au maximum 100 éléments pour atteindre l'élément. lui-même. Donc, c'est un algorithme à temps constant non?

Answer 2

Avec quelle sorte de structure travaillez-vous? Il n’existe pas de moyen efficace de parcourir une structure de données générique, mais il existe des milliers de méthodes d’optimisation et de méthodes efficaces pour des structures spécifiques.

Et oui, si vous avez un algorithme de complexité temporelle O (n), diviser par deux le nombre d'éléments ne le changera pas de complexité O (n) ... mais cela signifiera que chaque nouvel élément n'a que la moitié l'effet qu'il avait à l'origine. La notation Big O est un bon moyen de classer les algorithmes, mais elle n’entre pas dans l’efficacité sans compter des nombres énormes (un bon exemple est le tri. Quicksort est pire complexité que mergesort dans le pire des cas ... mais vous pouvez implémenter quicksort plus efficacement que mergesort pour presque toutes les applications autres que celles qui traitent le tri de millions d’articles)

Answer 3

"Horodatage" ou marquez chaque insertion et suppression, il suffirait alors d'une simple traversée pour trouver les modifications (O (n)).