Elegir una estructura de datos

Se utilizan diferentes estructuras de datos según el requisito, pero ¿cómo sabría qué estructura de datos debería usar? ¿Sólo quiero saber cómo elegir una estructura de datos adecuada? Gracias

Este diagtwig de flujo es para el STL en C ++, pero puede implementar cualquiera de las estructuras de datos admitidas por los contenedores STL en C.

  • La lista es una lista enlazada
  • Vector es una matriz dinámica
  • Deque es algo así como una lista de arrays dynamics, algo así como la diferencia.
  • La cola y la cola de prioridad son como dicen (normalmente la cola se implementa en términos de deque, la cola de prioridad se implementa generalmente en términos de un montón dentro de un vector o deque)
  • Set / Map / Multiset / Multimap se implementan utilizando algún tipo de árbol binario equilibrado.

Actualización 2016: Aparentemente, la imagen que solía enlazar aquí se ha roto, pero puedes ver varias imágenes equivalentes en esta pregunta: ¿ En qué escenario utilizo un contenedor STL en particular?

Debe investigar qué estructuras de datos se utilizan para cumplir qué requisitos (no hay nadie aquí que vaya a pasar el tiempo para deletrear todas las opciones para usted y decirle exactamente cuándo usarlo).

Una vez que conozca los detalles, debería poder (con una certeza razonable) elegir la estructura de datos adecuada para sus necesidades.

Cada estructura de datos tiene diferentes costos para diferentes tipos de acciones: debe preguntarse:

  1. ¿Necesito poder encontrar un elemento específico (dame la persona llamada “bob”)?
  2. ¿Me importa el pedido (es decir, encontrar regularmente el primero o el último)?
  3. ¿Necesito poder borrar de manera eficiente otros registros que el último?
  4. ¿Necesito acceso aleatorio (dame el 20)?
  5. ¿Necesito poder tener lectura y escritura multihilo eficientes?

nota: una pregunta que no está en la lista es “¿necesito poder recorrer todo el contenido de la tienda?”, ya que todos los almacenes de datos prácticos pueden acceder a todos los Estados en tiempo O (n)

Además, todos estos comentarios son generalizaciones:

si la respuesta a 1. es “sí”, entonces eso elimina varias estructuras de tipo de matriz no ordenadas (vectores, matrices sin clasificar, listas enlazadas)

si la respuesta a 2. es “sí”, entonces eso descarta las tiendas basadas en hash (hashmap, etc …) ya que dan un orden predecible para ayudar a la eficiencia de búsqueda. Probablemente necesites un conjunto de árboles o una lista ordenada.

si la respuesta a 3. es “sí”, entonces eso excluye las listas (matrices sin clasificar, listas enlazadas) y probablemente necesite un conjunto de árboles, una lista ordenada o un mapa hash.

si la respuesta a 4 es “sí”, eso elimina los hashmaps y las listas vinculadas (nota, esta es una pregunta diferente a 1, ya que los hashmaps almacenan todo en función de un índice, no los almacenan en ningún orden específico)

Si la respuesta a 5 es “sí”, entonces es probable que hagas una pregunta con tus requisitos específicos, ya que esto complica cada respuesta dada en los puntos anteriores (las listas vinculadas, los hashmaps y las matrices de crecimiento lento permiten implementaciones paralelas eficientes, clasificadas como Es difícil de hacer en parralel).

si se está preguntando por qué el conjunto de árboles está en todas esas opciones pero generalmente no se recomienda; es porque si la respuesta a 2 es “no”, el hashmap suele ser mejor (el tiempo para agregar y eliminar elementos aumenta mucho más lentamente que el conjunto de árboles a medida que crece la colección). Del mismo modo, si la respuesta a cualquiera de las otras preguntas es “no”, hay mejores recomendaciones.

en general: si necesita acceso aleatorio, hashmap. Si necesita un conjunto de árboles ordenados, de lo contrario una lista enlazada. (Todos estos vienen con una sobrecarga de memoria en comparación con una matriz directa, así que asumí que la memoria no es altamente restrictiva)

Es difícil responder sin saber qué partes de la decisión le están dando problemas.

En su mayor parte, desea la estructura de datos más pequeña y simple que contenga los datos que necesita almacenar.

¿Hubo un caso en particular que le estaba dando problemas?

No es lo que buscas, pero depende .

Depende de los datos que esté almacenando, de las restricciones para acceder a esos datos, ¿necesita poder consultar las cosas realmente rápido? ¿Necesita mantener algún tipo de clase en los datos? ¿Lo ordenarás más tarde?

Incluso cuando elige una estructura de datos (Lista vinculada, Mapa, Conjunto), existen numerosas variantes entre ellas que podrían impulsar su decisión.

Mi regla de oro es esta:

Vaya con lo más simple que pueda hasta que sepa que necesita algo más complicado.

Si su preocupación es una búsqueda rápida y eficiente, ¿qué estructura de datos elegirá para almacenar los datos? Dar razones para justificar la estructura de datos seleccionada.