¿Cuál es la estructura de datos más eficiente para admitir agregar al final del conjunto, así como acceder o actualizar el i-ésimo valor?

Así que aquí está el por qué nunca me fue bien en la clase de algoritmos.

Si los datos eventuales encajarán en DRAM, simplemente asigne el tamaño máximo de la lista y use una matriz. Obtener datos en caché será más rápido que extraer datos de un nodo de cómputo remoto.

Pero, ¿qué pasa si los datos son demasiado grandes para DRAM?

En lugar de salir al disco, probablemente solo desee que una matriz abarque toda la DRAM de su clúster. En LLNL, eso te llevará al rango de petabytes (1000 terabytes). Cada nodo cuida un subconjunto de la matriz, y puede hacer un poco de equilibrio de carga si su métrica es recuperaciones o agregados por segundo.

Pero, ¿qué pasa si sus datos son más grandes que eso?

Ahora tienes que ir a un sistema de archivos paralelo como lustre. Eso te llevará hasta 512 petabytes. Y ahora las preguntas se convierten en “¿Qué estructura de datos utiliza para volver a implementar un sistema de archivos de grado gubernamental que está optimizado para lecturas y anexos?” Eso será un poco más difícil.

Pero solo estamos a la altura de los petabytes. ¿Cómo cambia su solución si está trabajando con exabytes o zettabytes? ¿Qué tan rápido entran tus apéndices? Cuando tus clientes están haciendo lecturas, ¿cuánta localidad esperas?

Y algunas preguntas más:

¿Cuánta fiabilidad necesitas en el sistema? ¿Es suficiente una incursión? ¿O necesita inventar una estructura de datos que sea aún más rigurosa que eso? (Tenga en cuenta que el tiempo medio entre fallas probablemente será del orden de minutos una vez que se amplíe lo suficiente).

¿Está optimizando el tiempo medio de acceso o está tratando de cumplir con un SLA? ¿O es esto para la computación dura en tiempo real donde nunca puedes llegar tarde?

¿Cuáles son las características de los datos? ¿La compresión va a ser útil?

¿Cuál es la penalización si una lectura es incorrecta o se cae una escritura? ¿Se puede implementar la compresión con pérdida o se pueden usar algoritmos probabilísticos (filtros Bloom)?

Su libro de texto de algoritmos no entra en ninguno de esos detalles desagradables. Si estás estudiando algoritmos como disciplina matemática, está bien. Sin embargo, si está tratando de construir sistemas reales, debe prestar más atención a los coeficientes de lo que sugiere su libro de texto.

Un vector, tanto con respecto a la complejidad asintótica como prácticamente en el hardware actual.

Los accesos aleatorios en un vector son O (1) (aunque, prácticamente, con el almacenamiento en caché, eso no siempre es cierto), y se agrega a un vector que tiene una complejidad O (1) amortizada.

Con la complejidad asintótica, no mejora mejor que O (1) (y con respecto a la localidad de caché en el hardware actual, no mejora mejor que las matrices (dinámicas)).

Existen estructuras de datos estándar en la mayoría de los lenguajes / marcos optimizados para estas dos tareas exactamente.

En Java y C # se llaman ArrayLists. En C ++ se llaman vectores. En el objetivo C se llaman NSMutableArrays. Todo básicamente la misma idea. Todo diseñado para exactamente este requisito.