Guardar en inicialización de matriz

Hace poco leí que es posible tener matrices que no necesitan inicializarse, es decir, es posible usarlas sin tener que perder tiempo tratando de establecer cada miembro en el valor predeterminado. es decir, puede comenzar a usar la matriz como si se hubiera inicializado por el valor predeterminado sin tener que inicializarla. (Lo siento, no recuerdo dónde leí esto).

Por ejemplo, por qué eso puede ser sorprendente:

Supongamos que está intentando modelar una tabla hash del peor caso (para cada inserción / eliminación / búsqueda) de enteros en el rango .$\mathcal{O}(1)$$[1, n^2]$

Puede asignar una matriz de tamaño bits y usar bits individuales para representar la existencia de un número entero en la tabla hash. Nota: la asignación de memoria se considera tiempo .$n^2$$\mathcal{O}(1)$

Ahora, si no tuvo que inicializar esta matriz en absoluto, cualquier secuencia de decir operaciones en esta tabla hash ahora es el peor de los casos .$n$$\mathcal{O}(n)$

En efecto, tiene una implementación hash "perfecta", que para una secuencia de operaciones utiliza el espacio , ¡pero se ejecuta en tiempo !Θ ( n 2 ) O ( n $n$$\Theta(n^2)$$\mathcal{O}(n)$

¡Normalmente uno esperaría que su tiempo de ejecución sea al menos tan malo como su uso de espacio!

Nota: El ejemplo anterior podría usarse para una implementación de un conjunto disperso o una matriz dispersa, por lo que no solo es de interés teórico, supongo.

Entonces la pregunta es:

¿Cómo es posible tener una matriz como estructura de datos que nos permite omitir el paso de inicialización?

Este es un truco muy general, que puede usarse para otros fines que no sean el hash. A continuación doy una implementación (en pseudocódigo).

Deje tres vectores no inicializados , P y V de tamaño n cada uno. Los utilizaremos para realizar las operaciones solicitadas por nuestra estructura de datos. También mantenemos una variable p o s . Las operaciones se implementan de la siguiente manera:$A$$P$$V$$n$$pos$

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i) 
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i) 
  return A[i] 
else 
  return empty 

La matriz simplemente almacena los valores que se pasan a través del procedimiento s e t . Las matrices V y P funcionan como certificados que pueden determinar si se ha inicializado una posición determinada en $A$$set$$V$$P$$A$

Tenga en cuenta que en cada momento los elementos en van desde 0 a p o s - 1 se inicializan. Por tanto, podemos utilizar con seguridad estos valores como un certificado para los valores inicializados en una . Para cada posición i en A que se inicializa, hay un elemento correspondiente en el vector P cuyo valor es igual a i . Esto lo señala V [ i ] . Por lo tanto, si miramos el elemento correspondiente, P [ V [ i ] ] y su valor es $P$$0$$pos-1$$A$$i$$A$$P$$i$$V[i]$$P[V[i]]$$i$, sabemos que se ha inicializado (ya que P nunca miente, porque todos los elementos que estamos considerando se inicializan). De manera similar, si A [ i ] no se inicializa, entonces V [ i ] puede apuntar a una posición en P fuera del rango 0 .. p o s - 1 , cuando sabemos con certeza que no se inicializó, o puede apuntar a una posición dentro de ese rango. Pero esta particular P [ j ] corresponde a una posición diferente en A , y por lo tanto$A[i]$$P$$A[i]$$V[i]$$P$$0..pos-1$$P[j]$$A$ , entonces sabemos que A [ i ] no se ha inicializado.$P[j] \neq i$$A[i]$

Es fácil ver que todas estas operaciones se realizan en tiempo constante. Además, el espacio utilizado es para cada uno de los vectores, y O ( 1 ) para la variable p o s , por lo tanto O ( n ) en total.$O(n)$$O(1)$$pos$$O(n)$