Inicializar matriz en tiempo constante amortizado: ¿cómo se llama este truco?

13

Existe esta estructura de datos que intercambia el rendimiento del acceso a la matriz contra la necesidad de iterar sobre él al borrarlo. Mantiene un contador de generación con cada entrada, y también un contador de generación global. La operación "clear" aumenta el contador de generación. En cada acceso, se comparan los contadores de generación local y global; si difieren, el valor se trata como "limpio".

Esto surgió en esta respuesta en Stack Overflow recientemente, pero no recuerdo si este truco tiene una nombre oficial. ¿Lo hace?

Un caso de uso es algoritmo de Dijkstra si solo se debe relajar un pequeño subconjunto de nodos, y si Esto debe hacerse repetidamente.

    
pregunta krlmlr 09.07.2012 - 22:13

3 respuestas

2

El enfoque mencionado anteriormente requiere que cada celda pueda contener un número lo suficientemente grande como para contener el número de veces que la matriz deba reinicializarse, lo que es una penalización de espacio sustancial. Si una ranura es capaz de mantener al menos un valor que nunca se escribirá legítimamente, se puede evitar tener cualquier otra penalización (no constante) a expensas de agregar una penalización de tiempo O(Wlg(N)) , donde W es el número de distintas ranuras de matriz escritas entre operaciones de borrado y N es el tamaño de la matriz. Por ejemplo, supongamos que uno almacenará números enteros de -2,147,483,647 a 2,147,483,647 (pero nunca -2,147,483,648) y uno quiere que los elementos de la matriz en blanco se lean como cero. Comience llenando la matriz con -2,147,483,648 (llame a ese valor B ). Al leer una ranura de matriz para la aplicación, informe un valor de B como cero. Antes de escribir la ranura de la matriz I , verifique si contiene B y si es así y I es mayor que uno, almacene un cero en la ranura I/4 después de realizar una comprobación similar para esa ubicación (y, si se mantuvo B , I/16 , etc).

Para borrar la matriz, comience con I igual a 0 o 1, dependiendo de la base de la matriz (el algoritmo como se describe funcionará para cualquiera). Luego repita el siguiente procedimiento: Si el elemento I es B , aumente I y, si lo hace, produce un múltiplo de cuatro, divida por cuatro (finalice si la división produce un valor de 1); si el artículo I no es B , almacene B allí y multiplique I por cuatro (si I comienza en cero, multiplicando por cuatro lo dejará en cero, pero como el artículo 0 estará en blanco, I se incrementará).

Tenga en cuenta que uno podría reemplazar las "cuatro" constantes anteriores con otros números, ya que los valores más grandes generalmente requieren menos etiquetado de trabajo, pero los valores más pequeños generalmente requieren menos compensación de trabajo; como las ranuras de matriz que están etiquetadas deben borrarse, un valor de tres o cuatro es casi seguro que es óptimo; ya que el valor cuatro es ciertamente cercano al óptimo, es mejor que dos u ocho, y es más conveniente que cualquier otro número, parecería la opción más razonable.

    
respondido por el supercat 11.07.2012 - 18:26
1

Lo llamaría "reinicialización de la celda de la matriz perezosa", pero no parece tener ningún nombre establecido (es decir, el nombre está en uso generalizado).

El algoritmo es inteligente, pero muy especializado y aplicable en un área muy estrecha.

    
respondido por el Aleksander Adamowski 11.07.2012 - 16:43
1

Creo que es un caso especial de memoization , excepto en este caso, los "memos" implícitamente " edad "con cada incremento del contador global. Supongo que una especie de "memoria hacia atrás".

    
respondido por el defube 24.07.2012 - 08:06

Lea otras preguntas en las etiquetas