Initialiser le tableau en temps constant amorti - comment s'appelle cette astuce?

Il existe cette structure de données qui échange les performances de l'accès aux baies contre la nécessité de les itérer lors de leur effacement. Vous gardez un compteur de génération à chaque entrée, ainsi qu'un compteur de génération global. L'opération "clear" augmente le compteur de génération. Sur chaque accès, vous comparez les compteurs de génération locaux et globaux; s'ils diffèrent, la valeur est traitée comme "propre".

Cela est apparu récemment dans cette réponse sur Stack Overflow , mais je ne me souviens pas si cette astuce a un nom officiel. Le fait-il?

Un cas d'utilisation est l'algorithme de Dijkstra si seulement un petit sous-ensemble des nœuds doit être assoupli, et si cela doit être fait à plusieurs reprises.

algorithms terminology krlmlr
la source

Astuce intéressante, mais elle a tout à fait une surcharge. Je me demande donc quelles utilisations ont effacé le tableau en tant qu'opération courante dont le prix paie? (Question sincère!)

Joachim Sauer

@JoachimSauer: édité.

krlmlr

Cela semble très cher dans le cas général à la fois pour l'utilisation de la mémoire et le coût des accès. Le cas d'utilisation de cette technique doit être très spécifique.

Martin York

@Joachim: Il est utilisé pour effacer rapidement les tampons pour le rendu - en gros. Ils ont juste un "bit clair" par 64 Ko ou quelque chose comme ça.

DeadMG

@ user946850 "amorti" signifie que vous pouvez prouver qu'une opération coûteuse se produit assez rarement dans l'image globale pour ne pas contribuer plus que par exemple O (1)

Réponses:

L'approche susmentionnée nécessite que chaque cellule soit capable de contenir un nombre suffisamment grand pour contenir le nombre de fois que la matrice peut avoir besoin d'être réinitialisée, ce qui représente une pénalité d'espace substantielle. Si un slot est capable de contenir au moins une valeur qui ne sera jamais légitimement écrite, on peut éviter d'avoir une autre pénalité d'espace (non constante) au détriment de l'ajout d'une O(Wlg(N))pénalité de temps, où West le nombre de slots de tableau distincts écrits entre opérations de suppression et Ncorrespond à la taille du tableau. Par exemple, supposons que l'on stocke des entiers de -2 147 483 647 à 2 147 483 647 (mais jamais -2 147 483 648) et que l'on souhaite que les éléments de tableau vides soient lus comme des zéros. Commencez par remplir le tableau avec -2 147 483 648 (appelez cette valeurB). Lors de la lecture d'un emplacement de baie pour l'application, indiquez une valeur Bégale à zéro. Avant d' écrire fente de réseau I, vérifier si elle lieu Bet si oui , et Iest supérieur à un, stocker un zéro à fente I/4après avoir effectué un contrôle similaire pour cet emplacement (et, si elle lieu B, I/16etc.).

Pour effacer le tableau, commencez par Iégal à 0 ou 1, selon la base du tableau (l'algorithme tel que décrit fonctionnera pour l'un ou l'autre). Répétez ensuite la procédure suivante: Si item Iest B, incrémentez Iet, si cela donne un multiple de quatre, divisez par quatre (terminez si la division donne une valeur de 1); si l'élément Ine l'est pas B, stockez B-le et multipliez-le Ipar quatre (s'il Icommence à zéro, la multiplication par quatre le laissera à zéro, mais puisque l'élément 0 sera vide, Isera incrémenté).

Notez que l'on pourrait remplacer la constante "quatre" ci-dessus par d'autres nombres, avec des valeurs plus grandes nécessitant généralement moins d'étiquetage de travail, mais des valeurs plus petites nécessitant généralement moins d'effacement de travail; comme les emplacements de tableau marqués doivent être effacés, une valeur de trois ou quatre est presque certainement optimale; comme la valeur quatre est certainement proche de l'optimale, meilleure que deux ou huit, et plus pratique que n'importe quel autre nombre, cela semble le choix le plus raisonnable.

supercat
la source

Il suffit d'avoir un compteur de versions capable d'accueillir suffisamment de réinitialisations séquentielles avant que toutes les cellules ne soient mises à jour avec de nouvelles valeurs. En pratique, un octet peut être suffisant, voire moins dans des boucles plus serrées.

9000

@ 9000: Le code qui repose sur un tel comportement est susceptible d'être fragile, d'autant plus que la seule raison d'utiliser une telle approche `` pseudo-claire '' (par opposition à simplement effacer le tableau) serait si l'ensemble d'éléments qui aurait besoin le dédouanement était généralement petit et variable - une paire de conditions qui concourent à augmenter la probabilité qu'un article puisse être utilisé, "dédouané", puis reste intact pendant une période arbitrairement longue. On pourrait envisager de scanner le tableau et de

vider

... si la valeur de bouclage du compteur est constante, la quantité moyenne de travail pour chaque opération d'effacement de tableau serait O (N), N étant la taille du tableau. Non pas qu'une telle chose puisse ne pas être utile dans la pratique, car une implémentation O (N) accélérée par un facteur de 65 536 serait toujours O (N), mais serait également 65 536 fois plus rapide que celle non améliorée. . Soit dit en passant, les cas où ces approches seraient utiles peuvent également bénéficier de l'utilisation d'une structure de données à tableau fragmenté, qui pourrait utiliser l'espace O (AlgN) pour contenir un tableau avec un tableau de taille N avec des éléments non vides.

supercat

Je l'appellerais "réinitialisation de cellule de tableau paresseux", mais il ne semble pas avoir de nom établi (c'est-à-dire que le nom est largement utilisé).

L'algorithme est intelligent, mais très spécialisé et applicable dans un domaine très étroit.

Aleksander Adamowski
la source

Je crois que c'est un cas particulier de mémorisation , sauf dans ce cas, les "mémos" implicitement "vieillissent" à chaque incrément du compteur global. J'imagine une sorte de "mémorisation à l'envers".

désembuage
la source