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

Existe esta estructura de datos que intercambia el rendimiento del acceso a la matriz frente a 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 "borrar" aumenta el contador de generación. En cada acceso, usted compara contadores de generación locales versus globales; si difieren, el valor se trata como "limpio".

Esto ha surgido en esta respuesta en Stack Overflow recientemente, pero no recuerdo si este truco tiene un nombre oficial. ¿Lo hace?

Un caso de uso es el algoritmo de Dijkstra si solo un pequeño subconjunto de los nodos tiene que ser relajado, y si esto tiene que hacerse repetidamente.

algorithms terminology krlmlr
fuente

Truco interesante, pero tiene bastante sobrecarga. Entonces, me pregunto qué usos tienen la limpieza de la matriz como una operación tan común que paga el precio. (¡Pregunta sincera!)

Joachim Sauer

@JoachimSauer: Editado.

krlmlr

Suena muy costoso en el caso general tanto para el uso de memoria como para el costo de acceso. El caso de uso de esta técnica debe ser muy específico.

Martin York

@Joachim: Se utiliza para borrar rápidamente los buffers para renderizar, aproximadamente. Simplemente tienen un "bit claro" por 64kb o algo así.

DeadMG

@ user946850 "amortizado" significa que puede probar que una operación costosa ocurre raramente en la imagen general que no contribuye más que, por ejemplo, O (1)

Respuestas:

El enfoque antes mencionado requiere que cada celda pueda contener un número lo suficientemente grande como para contener el número de veces que la matriz puede necesitar reinicializarse, lo cual es una penalización de espacio sustancial. Si una ranura es capaz de contener al menos un valor que nunca se escribirá legítimamente, se puede evitar tener cualquier otra penalización de espacio (no constante) a expensas de agregar una O(Wlg(N))penalización de tiempo, donde Wes el número de ranuras de matriz distintas escritas entre operaciones de limpieza y Nes el tamaño de la matriz. Por ejemplo, suponga que uno almacenará enteros de -2,147,483,647 a 2,147,483,647 (pero nunca -2,147,483,648) y 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 valorB) Cuando lea una ranura de matriz para la aplicación, informe un valor de Bcero. Antes de escribir ranura de matriz I, comprobar si se llevó a cabo By si es así, y Ies mayor que uno, almacena un cero a la ranura I/4después de realizar una comprobación similar para esa ubicación (y, si se llevó a cabo B, I/16etc).

Para borrar la matriz, comience con I0 o 1, dependiendo de la base de la matriz (el algoritmo como se describe funcionará para cualquiera de los dos). Luego repita el siguiente procedimiento: Si el ítem Ies B, incremente Iy, si lo hace, produce un múltiplo de cuatro, divida por cuatro (termine si la división produce un valor de 1); si el artículo Ino lo está B, guárdelo Ballí y multiplique Ipor cuatro (si Icomienza en cero, multiplicar por cuatro lo dejará en cero, pero como el artículo 0 estará en blanco, Ise incrementará).

Tenga en cuenta que uno podría reemplazar la constante "cuatro" anterior con otros números, con valores más grandes que generalmente requieren menos etiquetado de trabajo, pero valores más pequeños generalmente requieren menos limpieza de trabajo; dado que los espacios de la matriz que están etiquetados tienen que borrarse, un valor de tres o cuatro es casi seguro óptimo; dado que el valor cuatro es ciertamente óptimo, es mejor que dos u ocho y es más conveniente que cualquier otro número, parece la opción más razonable.

Super gato
fuente

Es suficiente tener un contador de versiones capaz de acomodar suficientes reinicios secuenciales antes de que todas las celdas se actualicen con valores nuevos. En la práctica, un byte podría ser suficiente, o incluso menos, en bucles más ajustados.

9000

@ 9000: el código que se basa en dicho comportamiento es propenso a ser frágil, especialmente dado que la única razón para usar un enfoque tan 'pseudo-claro' (en lugar de simplemente borrar la matriz) sería si el conjunto de elementos que necesitaría Por lo general, el borrado era pequeño y variable: un par de condiciones que conspiran para aumentar la probabilidad de que un artículo se use, "borre" y luego permanezca intacto durante un tiempo arbitrariamente largo. Uno podría considerar escanear la matriz y borrar físicamente cualquier ranura vieja cuando el contador se va a ajustar, pero ...

supercat

... si el valor de ajuste del contador es constante, la cantidad promedio de trabajo para cada operación de eliminación de matriz sería O (N), siendo N el tamaño de la matriz. No es que tal cosa no sea útil en la práctica, ya que una implementación de O (N) que se acelera por un factor de 65,536 seguiría siendo O (N), pero también sería 65,536 veces más rápida que la no mejorada . Por cierto, los casos en los que estos enfoques serían útiles también pueden beneficiarse del uso de una estructura de datos de matriz dispersa, que podría utilizar el espacio O (AlgN) para mantener una matriz con una matriz de tamaño N con elementos A no en blanco.

supercat

Yo lo llamaría "reinicialización de células de 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.

Aleksander Adamowski
fuente

Creo que es un caso especial de memorización , excepto en este caso, los "memorandos" implícitamente "envejecen" con cada incremento del contador global. Supongo que una especie de "memoria hacia atrás".

defube
fuente