¿Por qué elegir la estructura de datos incorrecta hace que un programa sea ineficiente?

Cuando los datos con los que trabaja un programa son pequeños, casi cualquier estructura de datos funcionará. Esto se debe a que la cantidad de trabajo está limitada por la cantidad de datos que se deben trabajar. A medida que crecen los datos de un programa, la elección de la estructura de datos muestra más. Para obtener más datos, la forma en que trata los datos se vuelve más importante. Elegir una forma de tratar un gran conjunto de datos puede marcar la diferencia entre minutos y horas de tiempo de procesamiento.

Cada estructura de datos tiene múltiples formas de acceso. Leído, escrito, dividido, ordenado, buscado, fusionado, etc. La forma más abstracta de verlos es como una recopilación de datos. Cuando puede verlos más específicamente, como una recopilación de datos donde debe poder encontrar cualquier elemento aleatorio rápidamente mientras también necesita escrituras para tomar muy poco tiempo, mejor será el algoritmo disponible para encontrar información en esos datos. La razón de esto es que puede hacer suposiciones, atajos, que le permiten obtener la misma respuesta con menos trabajo. Cuanto mejores sean sus suposiciones a medida que crecen los datos, menos trabajo se necesita para usar los datos para generar información.

Una de las más importantes que escuché fue la herramienta JavaDoc para generar documentación para programas Java. Era una herramienta de alto perfil y solía ser muy lenta. Después de muchos años, alguien descubrió que el camino era estructuras de datos transversales, creo que usar un algoritmo O (n ^ 2) para hacer una tarea que podría hacerse en O (n). Una vez que arreglaron que la velocidad del programa mejoró dramáticamente.

Esta pregunta es demasiado amplia. Pero para dar una respuesta simple, es porque las personas han puesto las cosas que quieren en el lugar equivocado.

Una estructura de datos le brinda un acceso directo de un lugar a otro. Las diferentes estructuras de datos le ofrecen diferentes tipos de atajos. Por ejemplo, puede direccionar directamente un elemento con su número de secuencia si ese elemento está almacenado en una matriz, pero no si está en una lista vinculada. Como resultado, para obtener el ítem i-ésimo, necesita O (1) tiempo con una matriz, pero O (n) tiempo con una lista vinculada, a veces una gran diferencia en el rendimiento.

En un curso de sistemas operativos, una de las ideas clave es la localidad de referencia. Por supuesto, es específico del contexto, pero generalizando la premisa, toda organización (desde limpiar su habitación hasta diseñar su modelo de datos) se trata de ahorrar tiempo al evitar la necesidad de obtener las cosas que necesita juntas cuando las usa juntas.

Analogía simple: si está pintando su casa pero insiste en mantener toda la pintura en los escalones delanteros de su vecino de al lado, perderá un montón de tiempo caminando de un lado a otro. Puede organizarse por adelantado una vez, o puede organizarse repetidamente mientras trabaja.

Probar esta característica de video de Quora nuevamente para responder una pregunta de eficiencia general con una respuesta estrechamente relacionada con lo que discutí en esta respuesta: ¿Cuándo usaría el método de Búsqueda Binaria sobre el método de Búsqueda Secuencial?

Básicamente, algunas estructuras de datos están limitadas por su estructura a realizar ciertas operaciones (como búsquedas o inserciones) en ciertos tiempos de cálculo que otras no.

Como las inserciones en una matriz ordenada (para mantener una O (log n) contiene tiempo de función) frente a las inserciones en un árbol binario creado a partir de objetos de nodo.

0: 00-7: 04