¿Cómo visito todos los de una matriz cuadrada (0,1)?

Answer 1

Para el hardware de uso general, no puedo pensar en nada significativamente mejor que revisarlos secuencialmente.

Sin embargo, si tiene hardware de gráficos, existe una forma mucho mejor de utilizar un tipo de operación reducida. Esto es tan rápido que puede considerar las operaciones sobre texturas como una sola operación, y hay una gran cantidad de paralelismo. Representa la matriz como una textura. Digamos que es 512 por 512. Dibuje esto en una textura de 256 por 256, de modo que cada píxel sea 1 si alguno de los cuadrados de 4 píxeles es 1. Eso toma O (log n) pasos, suponiendo que cada dibujo es un paso, bastante razonable con buen hardware de gráficos. Luego, camine de regreso al cuadrático virtual, omitiendo en cada punto subcuadrantes sin 1s.

Hay infinitas variaciones en esta técnica, como dibujar siempre en un píxel comprobable y hacer que el árbol sea dinámico.