Mi instinto para esta pregunta es seguir con 2 preguntas más: ¿ventajas frente a qué? (lista vinculada? tabla hash? valores individuales?) y qué matrices?
Permítanme elaborar el segundo seguimiento: hay muchas cosas llamadas “matriz”. En su mayoría están relacionadas, pero tienen ventajas específicas en casos extremos. Por ejemplo, algunos idiomas (¿perl6?) Admiten “matrices de análisis” cuando inicia una matriz con un índice muy alto; una matriz de análisis es básicamente una tabla hash con índice entero. Otro ejemplo, una matriz de valores y una matriz de referencias puede comportarse de manera ligeramente diferente, especialmente con respecto a la tasa de pérdida de caché. Otro ejemplo, cuanto más alto sea su idioma, menos relevantes son muchas ventajas; por ejemplo, cuando se mueve a nubes de cuadros múltiples, “ventaja de caché” deja de significar nada.
Con la elaboración anterior en su lugar, permítame definir “matriz” rápidamente y responder la pregunta. Una matriz es, en términos generales, una serie de valores que son a) tipados de manera similar, b) consecutivos en memoria, yc) con un tamaño conocido (el tamaño puede cambiar, pero debe conocer el tamaño sin rastrear la colección completa). Puede indexar los valores, generalmente comienza con 0 y termina con longitud-1.
- ¿Son los gráficos la mejor estructura de datos para representar circuitos? ¿Hay algo mejor?
- Cómo resolver UVA 10407
- Cómo encontrar el salto más pequeño
- ¿Cuál es el algoritmo generador de números aleatorios más avanzado disponible ahora?
- ¿Cuál es mejor, búsqueda binaria o búsqueda lineal?
Contra otros tipos de colecciones (lista vinculada, árbol, tabla hash), las matrices tienen las siguientes ventajas:
- Caché amigable : dado que los valores están cerca uno del otro en la memoria, es fácil para la CPU almacenar en caché. Esto significa que la iteración sobre una matriz es más rápida que la iteración sobre cualquier otra cosa.
- Nota 1: “parse array” anula esto.
- Nota 2: la matriz de referencia puede o no tener esta ventaja, depende del uso; Si tiene que hacer referencia al valor, la ventaja de caché se reduce.
- Tiempo más predecible : en teoría, tanto la tabla hash como la matriz proporcionan tiempo de acceso O (1). Sin embargo, el O (1) de la tabla hash es realmente muy complicado y generalmente implica múltiples pasos, cada uno de los cuales puede involucrar errores de caché y recarga de memoria; Sin embargo, con las matrices, el sistema sabe dónde está la dirección precisa de cada valor en la memoria, por lo que acceder a ellas no solo es rápido, sino también previsible.
- Nota 1: los lenguajes de nivel superior pueden anular esto un poco, depende de la implementación, ya que debe saltar algunos niveles de código de alto nivel para acceder realmente a los datos.
- Nota 2: las operaciones de recopilación de alto nivel (mapa, reducción, filtro, etc.) abordan bien este problema para todas las colecciones, por lo que las matrices no tienen ventaja allí.
- Nota 3: recordatorio: la lista vinculada toma O (n) para acceder a un valor arbitrario, mientras que los árboles binarios balanceados toman O (log (n)).
- Comprobación de errores más fácil : lleva mucho tiempo saber si un índice es válido en una lista vinculada; es bastante complicado hacerlo en hashtable (especialmente con optimización y demás); es aritmética (¡y solo 2 op!) en matriz.
- Nota 1: las buenas implementaciones pueden almacenar en caché el tamaño y los índices para todas las colecciones. Este es un caso general.
- Más compacto en el uso de la memoria : en teoría (an en C), una matriz requiere solo espacio de memoria para los valores, la dirección de inicio y la longitud; en contraste, una lista vinculada (o un árbol) requiere un puntero para cada valor u O (n) datos adicionales; El requisito de memoria de hashtable depende de la implementación, pero generalmente requiere una asignación adicional.
- Nota 1: si una matriz almacena referencias (es decir, punteros) en lugar de valores, el uso de la memoria cambia, así que tenga cuidado.
- Nota 2: los lenguajes de nivel superior (por ejemplo, Java, C #, Javascript) también tienen otras funciones asociadas con una matriz (cachés, referencias de clase, etc.) que aumentan el uso de la memoria.
