de base Queue Optimisations

Question

Comment peut-on optimiser une file d'attente pour le typique:

accès/magasin

utilisation de la mémoire

je ne suis pas sûr de toute façon à réduire la mémoire en plus d'essayer d'exécuter un algorithme de compression sur cela, mais cela prendrait beaucoup de temps de magasin comme un compromis - il faudrait recompresser tout ce que je pense.

En tant que tel, je pense à la liste liée typique avec des pointeurs .... une file d'attente de cercle?

Des idées?

Remerciements

Éditer: indépendamment de ce qui précède; Comment fait-on essentiellement la structure de file d'attente de base la plus rapide/la moins intensive en mémoire?

Answer 1

Les listes liées ne sont en fait pas très typiques (sauf dans les langages fonctionnels ou lorsque les débutants pensent à tort qu'une liste liée est plus rapide qu'un tableau dynamique). Un tampon circulaire dynamique est plus typique. La croissance (et, facultativement, le rétrécissement) fonctionne légèrement différemment que dans un tableau dynamique: si la "partie de conservation de données" traverse la fin du tableau, les données doivent être copiées dans le nouvel espace de manière à rester contiguës (étendre simplement le tableau créerait un écart au milieu des données).

Comme d'habitude, il présente certains avantages et quelques inconvénients.

Désavantages:

• un peu plus compliqué la mise en œuvre
• ne convient pas pour

Avantages synchronisation sans verrou:

• plus compact: dans le pire des cas (quand il juste augmenté ou est sur le point de rétrécir mais n'a pas encore) il a un frais généraux d'environ 100%, un sing ly lié liste presque toujours a un overhead de 100% ou plus (sauf si les éléments de données sont plus grands qu'un pointeur) et une liste doublement liée est encore pire. Cache efficace: la lecture se produit près de la lecture précédente, l'écriture se produit près de l'écriture précédente. Les échecs de cache sont donc rares, et lorsqu'ils surviennent, ils lisent les données les plus pertinentes (ou dans le cas de l'écriture: ils obtiennent une ligne de cache qui sera probablement réécrite bientôt). Dans une liste chaînée, la localité est mauvaise et environ la moitié de chaque cache manqué est gaspillée sur la surcharge (pointeurs vers d'autres nœuds).

Habituellement, ces avantages l'emportent sur les inconvénients.