data-structures - book - data structures types
¿Cuáles son las estructuras de datos más útiles para saber de adentro hacia afuera? (15)
Estoy interesado en descubrir qué personas considerarían las estructuras de datos más útiles para saber en programación. ¿Qué estructura de datos usas todo el tiempo?
Las respuestas a esta publicación deberían ayudar a los nuevos programadores interesados en encontrar una estructura de datos útil para su problema. Las respuestas probablemente deberían incluir la estructura de datos, información sobre ella o un enlace relevante, la situación en la que se está utilizando y por qué es una buena opción para este problema (por ejemplo, complejidades de cómputo ideales, simplicidad y comprensión, etc.)
Cada respuesta debe ser sobre una sola estructura de datos.
Gracias por las perlas de sabiduría y experiencia que la gente puede compartir.
Esta publicación es demasiado vaga. Hay innumerables estructuras de datos: matrices, diccionarios, etc. Cada estructura de datos se puede usar para resolver diferentes problemas.
Sería mucho más productivo pedir DS por un problema específico.
Esto es un poco como preguntar qué herramientas en la caja de herramientas de un carpintero son las mejores para aprender a usar. Cada uno de ellos es bueno para cierto tipo de trabajo, y usted necesita aprender los básicos (mapas, listas, bolsas, juegos, etc.) por igual.
Me encuentro utilizando matrices con mucha frecuencia en combinación con la estructura de control "foreach" para recorrer los elementos. En el pasado utilicé matrices con un índice numérico y el "para (i = 1; i <n; i ++)". Descubrí que al recorrer las matrices con "foreach" en lugar de un índice numérico explícito, se obtiene una solución más general y legible.
Me encuentro utilizando una matriz asociativa bastante, básicamente matrices con una cadena como índice.
No creo que haya una estructura de datos que uno deba saber. Cada estructura de datos tiene sus propias propiedades y, por lo tanto, es adecuada para un problema específico.
Para una apreciación básica, debe conocer algunos tipos de datos abstractos (conjunto, diccionario, lista ordenada, cola, pila, etc.) y varias formas de implementar cada uno con sus ventajas y desventajas relativas.
Es probable que esto requiera que comprenda matrices, listas enlazadas (vinculadas simples y dobles), tablas hash, árboles de búsqueda binarios (con cierta comprensión de la heurística de equilibrio simple) y montones binarios. Conozca esto al revés y podrá recorrer un largo camino hacia la comprensión de estructuras de datos más complejas e interesantes. Además, si los ha implementado todos, tendrá una biblioteca preparada que usted comprenderá para la programación de proyectos (aunque, obviamente, más bibliotecas de batalla como Boost o lo que sea más apropiado para el código de producción).
Esto proporciona un vocabulario muy útil de estructuras de datos, lo que puede marcar una diferencia significativa en la forma en que escribe sus programas. Puede encontrar que ha estado resolviendo problemas con muchas implementaciones parciales de una cola, por ejemplo, que ahora puede reemplazar con una implementación canónica.
Siempre he encontrado una gran variedad de usos para las pilas, aunque menos en la programación orientada a objetos. Realmente, todas las estructuras de datos tienen sus usos, y no son complejas. Aprende todo lo que puedas
Tendré que ignorar su requisito sobre una estructura de datos por publicación; estos son los que he usado más y la mayoría de los programas que encuentro requieren principalmente uno entre estos o una combinación.
arrays : el más básico y proporciona el acceso más rápido. los vectores son la improvisación sobre los viejos arreglos simples y son reemplazos de facto utilizados comúnmente en estos días. dequeue es otra variación de este tema y ofrece de nuevo tiempo consind / acceso aleatorio pero optimizado para inserciones y eliminaciones rápidas al principio y al final.
Lista de enlaces : muy útil para mantener una lista de datos que se descarta e inserta con frecuencia, pero que es muy lenta para iterar / buscar. por ejemplo, listas gratuitas / usadas dentro de páginas de memoria
árboles - una estructura básica que forma la base de estructuras más complejas. Hay muchas formas de esta estructura. Proporciona tiempos de búsqueda logn cuando el árbol se mantiene ordenado. Resulta útil para elementos de datos de gran tamaño, como diccionarios. Los árboles binarios / AVL y rojo-negro son los más comunes.
mapas y hashes : no se trata exactamente de estructuras de datos, sino de complejos algoritmos de búsqueda rápida implementados mediante una combinación de lógica inteligente y la estructura de datos anterior.
Esta estructura de datos y su implementación están disponibles en la biblioteca STL en C ++. Otros idiomas también tienen sus implementaciones nativas. Una vez que conozca estas estructuras básicas de datos y algunas de sus variaciones (cola, pila, colas de prioridad) y algo sobre los algoritmos de búsqueda, diría que los conceptos básicos estarían bien cubiertos.
Una de las estructuras de datos que uso más (más allá de los vectores, por supuesto) es la Hashtable. Es casi la única opción si necesita poder buscar grandes cantidades de datos en O (1) vez, lo que significa que el tiempo de búsqueda no aumenta a medida que crece el tamaño de la colección.
El inconveniente es que los tiempos de inserción y eliminación son mayores que en otras estructuras de datos, y debe tener algún tipo de clave con la que buscar en la colección. Cada elemento debe tener una clave. El algoritmo toma la clave de cada elemento y calcula un código hash que indica la ranura en la tabla hash en la que buscar. Luego, dependiendo de la implementación, sigue una lista de artículos que cayeron en ese cubo para encontrar su artículo o busca en los cubos cercanos. El tamaño del hastable es determinante para la eficacia del hash que se ve bastante afectado por la cantidad de colisiones de códigos hash entre claves.
Úselo cada vez que necesite un mapa y el número esperado de elementos del mapa exceda aproximadamente 10. Es un poco más intensivo de memoria que otras estructuras ya que necesita muchas ranuras sin usar en la tabla para ser eficiente.
C # tiene una gran implementación con Dictionary<keytype, valuetype> e incluso tiene un HybridDictionary que decide internamente cuándo usar una tabla hash o un vector. Cualquier buen libro de programación lo describe, pero estará bien servido por wikipedia: http://en.wikipedia.org/wiki/Hashtable
No creo que haya una respuesta general aquí. Debería estar limitado a algún caso de uso. Por ejemplo, en mi carrera de más de 10 años como programador / gerente, nunca he usado árboles binarios. Dudo que eso signifique que los árboles binarios no son útiles, pero que en el kernel y el mundo integrado la lista enlazada probablemente se ajuste mejor.
De hecho, cuando pienso en descartar algunas excepciones, utilizo solo listas simples vinculadas.
Y luego, incluso en el embebido probablemente no sea la única estructura utilizada. Estoy viviendo en el mundo de los protocolos de hardware de bajo nivel, probablemente "más arriba", más estructuras de datos utilizadas ...
Las ventajas de las listas enlazadas son que son muy baratas para agregar / eliminar nodos. A diferencia de las matrices, [...] no requieren reasignar más memoria al expandirse.
Si tiene una matriz y duplica el tamaño de la asignación cada vez que la rellene, habrá amortizado O (1). Además, es probable que recorrer todos los elementos de una matriz sea más rápido (en tiempo de pared) que pasar por encima de una lista vinculada, debido a los efectos de almacenamiento en caché (a menos que los asocies en grandes fragmentos y no los desordenes demasiado )
Además, las matrices son más pequeñas: se guarda la sobrecarga de palabra por elemento, más la sobrecarga por asignación (que es probablemente al menos dos palabras: una para el tamaño y una para el puntero siguiente en la lista libre).
Ordenación rápida
Mergesort
Ordenamiento de burbuja
Estos son realmente buenos para aprender y entender cómo funcionan. La clasificación es divertida y se puede aplicar a muchas áreas :)
Los gráficos son una estructura de datos que se pasa por alto muy poderosa.
Se pueden resolver muchos problemas construyendo un gráfico que modele su problema y luego use un algoritmo bien conocido en el gráfico. Algunos ejemplos son el procesamiento del lenguaje natural (el peso del borde que conecta los nodos puede representar la probabilidad de que una palabra siga a otro) los videojuegos (use gráficos para determinar las rutas más cortas para los caracteres AI) y la topología de la red.
Aprendí sobre los gráficos de The Algorithm Design Manual , que Steve Yegge recomendó en una publicación de blog .
Me gustan los árboles binarios. Especialmente la variante Splay-Tree. Es algo similar a un árbol binario de auto-equilibrio, pero también se adapta al patrón de uso de la aplicación. Casi nunca se topa con el peor caso O (n) comportamiento.
Una buena ventaja es que también son más fáciles de escribir y necesitan menos código que otros árboles binarios autoequilibrados. Es una de mis estructuras de datos favoritas porque funciona increíblemente bien en la práctica.
Listas enlazadas / listas doblemente enlazadas / otras variantes
Todos deberían conocer los pros y los contras de una lista vinculada, y por la completa falta de uso, parece ser algo que mucha gente parece olvidar.
Las ventajas de las listas enlazadas son que son muy baratas para agregar / eliminar nodos. A diferencia de las matrices o estructuras de datos que usan una matriz en el núcleo, no requieren la reasignación de más memoria al expandirse.
Las desventajas son que no funcionan bien para buscar. Lo que sería una búsqueda O (1) en una matriz es O (n) para una lista vinculada.
Al igual que todas las estructuras, las listas vinculadas son ideales solo bajo ciertas condiciones. Pero utilizados en el momento adecuado, son muy poderosos.