En los lenguajes de programación donde una matriz crece dinámicamente en tamaño, ¿no es una preocupación porque es O (n) complejidad de tiempo?

Me refiero a la implementación de matriz dinámica más común aquí:

Casi todos estos crecen esos arreglos en pasos en lugar de solo un elemento a la vez. La práctica más común es crecer por algún factor (generalmente el doble de la cantidad necesaria). Por lo tanto, el tiempo perdido en el crecimiento de una matriz solo ocurre de manera intermitente. Y cuanto más grande sea la matriz, mayores serán los períodos de tiempo entre estas ralentizaciones de crecimiento.

Como beneficio adicional, la mayoría de estos sistemas tienden a usar instrucciones extremadamente optimizadas cuando copian la matriz pequeña anterior a la nueva grande. Por lo general, se usa incluso algo como las instrucciones SSE2 de la CPU, en lugar de copiar un elemento a la vez. Lo que reduce bastante el tiempo perdido en el crecimiento de la matriz.

Además, en realidad es un proceso que consume mucho tiempo asignar solo un espacio adicional. Por ejemplo, si una lista vinculada solo solicita una ranura adicional, debe asignar memoria para esa ranura, una por vez. La llamada al sistema operativo para permitir la RAM adicional asignada al proceso no es un retorno instantáneo, podría tomar varios ciclos de reloj. Pero asignar numerosos bytes adicionales (como pedir una nueva matriz completa) lleva aproximadamente el mismo tiempo. Por lo tanto, pedir un lote de más espacio toma casi el mismo tiempo que pedir solo uno más. Por lo tanto, crecer en lotes también hace que la asignación de memoria sea más rápida en promedio (por ranura).

En la práctica, se ha descubierto que una colección tiende a crecer hasta cierto punto y luego se mantiene razonablemente cerca de esa cantidad. Por lo tanto, el crecimiento solo ocurre para una parte de la ejecución del programa. Después de lo cual no ocurre (tanto). Por lo tanto, esta implementación tiende a funcionar bastante bien y, en promedio, ofrece un rendimiento bastante bueno (si no el mejor).

Hay algunas otras implementaciones también. Por ejemplo, una forma de “cubos” donde la “matriz dinámica” es en realidad una lista de matrices vinculadas entre sí (ya sea como una lista vinculada de matrices o como una “matriz dinámica” de punteros a matrices). Cada vez que necesita crecer, se agrega un nuevo “cubo” a la lista en el tiempo O (1). El problema aquí es que cada vez que se calcula un índice, se convierte en una operación div / mod para determinar a cuál de los depósitos se refiere y en qué ranura de ese depósito. Por lo tanto, cada operación de índice se vuelve más lenta que una simple calibración de desplazamiento normal. Hay algunas posibilidades de optimización (por ejemplo, desplazamiento de bits en lugar de div / mod), pero nunca se convertiría en una operación + como con un desplazamiento de matriz normal. Entonces, en este caso, es una compensación hacer que la operación más común (indexación) sea más lenta, mientras que la menos común (crecimiento) sea más rápida.

La razón más común para este tipo de estructura posterior no es la velocidad, sino el espacio. Una sola matriz tiende a tener un límite impuesto por su longitud por el entorno. Mediante tal compartimentación es posible ir más allá de esos límites.

En general, las matrices de crecimiento dinámico como ArrayList de Java cuestan alrededor de un factor de dos (en operaciones de lectura y escritura) sobre una matriz preasignada. También desperdician en promedio aproximadamente 1/4 de su tamaño, y 1/2 peor de los casos.

Ahora si ese es un problema importante depende de su caso de uso. Si su matriz es bastante pequeña, la simplicidad y flexibilidad generalmente valen el tiempo y la memoria perdidos. Para una matriz de 1GB, probablemente quieras ser más juicioso.

También señalaré que el rendimiento de matrices muy grandes (y otras estructuras de datos muy grandes) es muy diferente de lo que su libro DS de la universidad podría decirle. A esas escalas, factores como el almacenamiento en caché, las latencias de acceso al disco, etc. pueden dominar su rendimiento real. Por lo general, es una buena idea volver a examinar todo su enfoque y asegurarse de estar utilizando la estructura de datos correcta y de hacerlo de manera adecuada.

Probablemente también escriba algunos datos razonables en la matriz. Escribir n celdas requiere O ( n ) y (a menos que solo esté escribiendo ceros o algo así) con un coeficiente mayor que la reasignación y la copia, que en realidad son muy rápidas. Y dado que esta reasignación no se realiza en cada paso, sino solo cuando el tamaño de la matriz se duplica, cada celda se mueve menos de dos veces en promedio.

En general, en la mayoría de los casos, solo lleva un poco más de tiempo. La memoria se duplica, lo que es más probable que sea un problema.

Con std :: vector en C ++, si estas pequeñas desventajas son un problema, puede:

• si sabe cuántas celdas necesita de antemano, puede reservar este espacio desde el principio,
• use std :: array o una matriz C simple y simple en su lugar, que además puede hacer que su programa se ejecute más rápido debido a la menor indirección.

Suponga que tiene una estructura de datos vectoriales que está implementando con la asignación dinámica de memoria.

Además, suponga que está agregando al final de este vector. ¿Cuánto tiempo lleva esto? Bueno, más a menudo que no, tendrás espacio para este nuevo elemento, e insertarlo lleva [math] \ Theta (1) [/ math] tiempo.

Sin embargo, ¿qué sucede cuando nos quedamos sin espacio? Creamos una nueva matriz que es el doble del tamaño y luego copiamos todo. Esto cuesta tiempo [matemáticas] \ Theta (n) [/ matemáticas], lo cual no es muy bueno.

Retrocedamos y notemos que es muy conveniente tener que cambiar el tamaño de la matriz. Solo sucede cada potencia de 2. Si n es muy grande, que es la suposición en la notación [matemática] \ Theta [/ matemática], las operaciones [matemática] \ Theta (n) [/ matemática] son ​​poco frecuentes. Por lo tanto, podemos distribuir el costo de cada operación de cambio de tamaño sobre todas las demás operaciones de inserción baratas. A esto lo llamamos un análisis amortizado .

Aunque técnicamente es correcto decir que el peor de los casos para cualquier inserción es [matemática] \ Theta (n) [/ matemática], si realiza muchas operaciones de inserción, podemos decir que cada una de ellas toma [matemática] \ Theta ( 1) [/ math] tiempo amortizado.

La forma en que esto se implementa a menudo es que la capacidad de la matriz se duplica cada vez que se copia, por lo que para obtener su ejemplo de 1G, la matriz se habría copiado aproximadamente 30 veces y la cantidad total de datos copiados sería (creo) 2G. Esa no es una cantidad horrible de copia y reasignación, por lo que funciona bastante bien. Pierde algo de memoria. Puede hacer que desperdicie menos memoria multiplicando la capacidad por menos de 2X, pero luego su asignación y el tiempo de copia aumentan.

Una razón por la que todo esto funciona tan bien es que las matrices son estructuras de datos muy amigables con la caché. Eso compensa muchas ineficiencias que podrías generar al reasignar el espacio.

No es razonable tener 1 concierto de datos en una matriz o cualquier otra estructura de datos. El único tipo de caso de uso en el que estaría bien es si tiene un búfer o un caché de algún tipo, donde tiene un tamaño estrictamente oculto. Es decir, seguro que puedo optimizar mi procesamiento al retener hasta N bytes en la memoria. Pero en este caso, debe controlar el cambio de tamaño de su matriz de una manera muy intencional y deliberada que probablemente tenga en cuenta la dinámica de datos específica de su aplicación.

Pero si esto es algo más genético, como “leamos todos los registros de clientes en la memoria” de lo que está mal, no solo por el tiempo requerido, sino también en términos de uso de sus recursos. Porque pronto ese gigbyte se convertirá en diez y luego se quedará sin RAM y el sistema comenzará a paginar la memoria en el disco. No quieres eso. Para esa cantidad de datos, necesita una base de datos de algún tipo.

Para una pequeña cantidad de datos, una matriz redimensionable está bien y generalmente reduce la complejidad de su código. Ayuda a que la capacidad inicial sea correcta, pero muchas veces puedes ser casual sin ningún efecto negativo. Todo depende.

Definitivamente es una preocupación dependiendo de para qué los esté usando y dependiendo de si la reasignación está en la ruta de acceso de un programa.

Para mitigar el costo de las reubicaciones de arreglos, la mayoría de las implementaciones de listas de arreglos crecerán en más elementos de los estrictamente necesarios.

Por ejemplo, este es el complemento en la ArrayList integrada en java:

public boolean add (E e) {
sureCapacity (tamaño + 1); // Incrementos modCount !!
elementData [tamaño ++] = e;
volver verdadero;
}

…

public void allowCapacity (int minCapacity) {
modCount ++;
int oldCapacity = elementData.length;
if (minCapacity> oldCapacity) {
Objeto oldData [] = elementData;
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (nuevaCapacidad newCapacity = minCapacity;
// minCapacity generalmente está cerca del tamaño, por lo que esta es una ganancia:
elementData = Arrays.copyOf (elementData, newCapacity);
}
}

Lo que ves aquí es que la matriz tiene una capacidad, que es diferente del tamaño. El tamaño es cuántos elementos tiene la matriz, la capacidad es cuántos elementos puede contener la matriz antes de que necesite reubicación. El método allowCapacity tiene el peor caso de O (n) si termina reasignando debido a la llamada a la función Arrays.copyOf.

Digamos que la matriz tenía 10 elementos y capacidad 10 y alguien agrega un nuevo elemento, entonces la nueva capacidad de la matriz será (10 * 3) / 2 + 1 = 16. La matriz se reasigna para 6 elementos más en lugar de 1.

Cuando crea la matriz, puede decirle qué capacidad desea. Si sabe esto con anticipación, definitivamente debe pasarlo para evitar reasignaciones. Por ejemplo:

// preasigna espacio para 100 elementos para evitar reasignaciones
List

Otra forma de evitar el costo de las reasignaciones es utilizar listas vinculadas. Agregar o eliminar el encabezado o la cola de una lista vinculada es O (1) y nunca se reasigna, el intercambio es que obtener el enésimo elemento de la lista es O (n), que es mucho más lento que una ArrayList. Tampoco es una estructura amigable con el caché, lo que importa en el mundo real.

Sí, reasignar matrices es costoso. Entonces, hay varias estrategias para hacerlo tan raramente como sea posible.

Ejemplo simple: crea una nueva matriz con, digamos, diez elementos. Desea agregar un undécimo elemento. Así que ahora tienes que reasignar la matriz con un tamaño más grande …

Pero en lugar de asignar una nueva matriz de 11 elementos, asigna una matriz de 20 elementos y solo pretende que tenga 11 entradas. No es tanto espacio, y puede agregar otros 9 elementos antes de tener que reasignar nuevamente.

La reasignación en sí misma sigue siendo O (n), pero la complejidad amortizada es mucho menor, ya que las reasignaciones ocurren con menos frecuencia.

Y, por supuesto, siempre existe el hecho de que la mayoría de las matrices simplemente nunca alcanzan tamaños muy grandes. Miles de elementos aún son pequeños, por lo que no debe preocuparse la mayor parte del tiempo: un factor O pequeño (n) no hará ni interrumpirá su aplicación (siempre que la mantenga fuera de los lazos internos apretados).

Una matriz dinámica generalmente se implementa mediante la reasignación de 2n celdas de memoria una vez que la matriz de longitud n está completamente ocupada. De esa forma el costo amortizado de inserción es constante. Duplicar intuitivamente el tamaño de la matriz hace que la reasignación sea menos frecuente, de modo que el costo de la costosa acción de copiar las n celdas completas después de la reasignación se distribuye en n pasos de tiempo, produciendo un costo amortizado O (1).

Hay un par de ideas falsas aquí.
En primer lugar, porque algo es O (n) no significa que estemos bien. El tiempo real necesario para reasignar y copiar una matriz podría seguir siendo un problema. O (n) solo significa asintóticamente lineal. Puede ser 0.000001sxn y, por lo tanto, el caso n = 1,000,000 toma un segundo. Puede que eso no suene mucho, pero puede ser lento para el propósito previsto.

Sin embargo, lo más importante al copiar una matriz podría ser rápido, un algoritmo podría hacerlo muchas veces y luego la ley de escala para el algoritmo podría no ser lineal.
Por ejemplo, considere una rutina ingenua que lee 1,000,000 de elementos de un archivo. Lo hace leyendo un nuevo elemento, reasignando una matriz de longitud n-1 a longitud ny agregando el nuevo elemento.
Eso lleva 1 copia, 2 copias, 3 copias, etc. La respuesta real requiere n * (n + 1) / 2 copias y el caso de un millón de artículos requerirá 500,000,000,000 copias. Cualquiera sea el momento para una sola copia, es poco probable que sea una solución práctica.
Al repetir, el tiempo de ejecución de un algoritmo (incluso uno simple) que usa matrices puede ser superlineal incluso si la copia de la matriz es lineal.
En la práctica, los programas que usan matrices probablemente lograrían un mejor rendimiento al asignar una matriz de 100 largos y luego aumentarla (una estrategia común es duplicarla) cada vez que se excede. La escala asintótica sería entonces O (n * Ln (n)).

Es interesante y útil conocer la escala en la notación Big-O, pero en la práctica es importante saber cuál es la constante y es importante observar todo el proceso, ni un solo paso, especialmente si ese paso se repite.
Si está ampliando o eliminando de alguna lista, es muy probable que las matrices no ofrezcan un rendimiento aceptable incluso en tamaños pequeños (como cientos) y en muchas plataformas se vuelvan inutilizables en unos pocos miles. La mayoría de los sistemas recurren a listas vinculadas u otras estructuras no contiguas para estas tareas.
Simplemente es falso pensar porque O (n) es lineal y está bien que el único contenedor que necesita es una matriz.

Depende de la implementación del lenguaje. Algunos idiomas probablemente solo agreguen elementos al final de la matriz sin reasignar y copiar datos existentes. Eso sería O (1).

Python parece reasignar y copiar los datos cuando agrega, que es O (N). Pero ponga ese apéndice en un bucle y estará en [matemáticas] O (N ^ 2) [/ matemáticas], lo cual no es bueno.

Tal vez no quieres una matriz? Una lista vinculada individualmente tiene [math] O (1) [/ math] prepend, sin límite.