Se habla mucho sobre estructuras de datos, pero no puedo encontrar una lista simple de estructuras de datos y su uso práctico por ahí. Estoy tratando de estudiar para una entrevista y creo que esto me ayudaría, junto con muchos otros. Estoy buscando algo como esto:
Estructura de datos - Ejemplo / Usado para
Tabla hash: búsqueda rápida de datos ... luego dé un ejemplo
Matriz - ...
Árbol binario - ...
Si hay un recurso como este en alguna parte, hágamelo saber.
¡Gracias!
EDITAR: Me refiero a que wikipedia es buena y todo, pero en la mayoría de las páginas no enumeran los usos prácticos. Estoy buscando algo más que eso.
data-structures
Joel
fuente
fuente
Estoy en el mismo barco que tú. Necesito estudiar para entrevistas técnicas, pero memorizar una lista no es realmente útil. Si tiene de 3 a 4 horas libres y desea hacer una inmersión más profunda, le recomiendo que consulte
mycodeschool
He buscado en Coursera y otros recursos como blogs y libros de texto, pero los encuentro o no lo suficientemente completos o en el otro extremo del espectro, demasiado densos con terminologías de ciencias de la computación prerrequisito.
El tipo del video tiene un montón de conferencias sobre estructuras de datos. No te preocupes por los dibujos tontos o el ligero acento en absoluto. Debe comprender no solo qué estructura de datos seleccionar, sino algunos otros puntos a considerar cuando la gente piensa en estructuras de datos:
También publiqué notas en github si estás interesado.
fuente
Según tengo entendido, la estructura de datos es cualquier dato que reside en la memoria de cualquier sistema electrónico que se puede administrar de manera eficiente. Muchas veces es un juego de memoria o una accesibilidad más rápida a los datos. En términos de memoria, nuevamente, hay compensaciones hechas con la administración de datos en función del costo para la empresa de ese producto final. Administrado de manera eficiente nos dice cuál es la mejor manera de acceder a los datos en función del requisito principal del producto final. Esta es una explicación de muy alto nivel, pero las estructuras de datos son temas muy amplios. La mayoría de los entrevistadores se sumergen en estructuras de datos que pueden permitirse discutir en las entrevistas en función del tiempo del que disponen, que son listas vinculadas y temas relacionados.
Ahora, estos tipos de datos se pueden dividir en primitivos, abstractos, compuestos, según la forma en que se construyen y acceden lógicamente.
Espero que esto te ayude a sumergirte.
fuente
El excelente libro " Algorithm Design Manual" de Skienna contiene un enorme depósito de algoritmos y estructura de datos.
Para toneladas de problemas, las estructuras de datos y el algoritmo se describen, comparan y discuten el uso práctico. El autor también proporciona referencias a implementaciones y artículos de investigación originales.
El libro es excelente para tenerlo en su escritorio si busca la mejor estructura de datos para resolver su problema. También es muy útil para la preparación de entrevistas.
Otro gran recurso es el Diccionario NIST de estructuras y algoritmos de datos .
fuente
Pocas aplicaciones más prácticas de estructuras de datos
Árboles rojo-negro (se usan cuando hay inserciones / eliminaciones frecuentes y pocas búsquedas) - Agrupación de K-mean usando árbol rojo negro, bases de datos, base de datos simple, búsqueda de palabras dentro de diccionarios, búsqueda en la web
Árboles AVL (más búsqueda y menos inserción / eliminación): análisis de datos y minería de datos y las aplicaciones que implican más búsquedas
Min montón: algoritmos de agrupación
fuente
Cualquier clasificación de varias estructuras de datos estará, al menos parcialmente, ligada al contexto del problema. Sería útil aprender a analizar el rendimiento espacial y temporal de los algoritmos. Normalmente, se utiliza la "notación O grande", por ejemplo, la búsqueda binaria está en tiempo O (log n), lo que significa que el tiempo para buscar un elemento es el registro (en base 2, implícitamente) del número de elementos. De manera intuitiva, dado que cada paso descarta la mitad de los datos restantes como irrelevantes, duplicar el número de elementos aumentará el tiempo en 1 paso. (La búsqueda binaria se escala bastante bien.) El rendimiento espacial se refiere a cómo crece la cantidad de memoria para conjuntos de datos más grandes. Además, tenga en cuenta que la notación O grande ignora los factores constantes: para conjuntos de datos más pequeños, un algoritmo O (n ^ 2) aún puede ser más rápido que un algoritmo O (n * log n) que tiene un factor constante más alto.
Además del tiempo y el espacio, otras características incluyen si una estructura de datos está ordenada (los árboles y skiplists están ordenados, las tablas hash no), persistencia (los árboles binarios pueden reutilizar punteros de versiones anteriores, mientras que las tablas hash se modifican en su lugar), etc.
Si bien necesitará aprender el comportamiento de varias estructuras de datos para poder compararlas, una forma de desarrollar una idea de por qué difieren en el rendimiento es estudiar de cerca algunas. Sugeriría comparar listas enlazadas individualmente, árboles de búsqueda binarios y listas de omisión , todos los cuales son relativamente simples, pero tienen características muy diferentes. Piense en cuánto trabajo se necesita para encontrar un valor, agregar un nuevo valor, encontrar todos los valores en orden, etc.
Hay varios textos sobre el análisis del rendimiento de la estructura de datos / algoritmos que la gente recomienda, pero lo que realmente hizo que tuvieran sentido para mí fue aprender OCaml. Lidiar con estructuras de datos complejas es el punto fuerte de ML, y su comportamiento es mucho más claro cuando puede evitar los punteros y la gestión de la memoria como en C. (Sin embargo, aprender OCaml solo para comprender las estructuras de datos es casi seguro que el camino más largo. :))
fuente