¿Cuál es la estructura de datos más complicada que ha utilizado en una situación práctica? [cerrado]

El germen de esta pregunta surgió de una discusión que estaba teniendo con un par de colegas desarrolladores de la industria.

Resulta que, en muchos lugares, los gerentes de proyecto desconfían de las estructuras de datos complejas y, en general, insisten en lo que exista fuera de la caja de la biblioteca / paquetes estándar. La idea general parece ser usar una combinación de lo que ya está disponible a menos que el rendimiento se vea seriamente impedido. Esto ayuda a mantener la base del código simple, lo que para los no diplomáticos significaría "tenemos un alto desgaste, y los nuevos que contratamos pueden no ser tan buenos".

Por lo tanto, no hay filtros de floración ni listas de omisión o árboles de despliegue para sus adictos a CS. Así que aquí está la pregunta (nuevamente): ¿Cuál es la estructura de datos más complicada que hizo o usó en la oficina?

Ayuda a tener una idea de cuán bueno / sofisticado es el software del mundo real.

Han usado listas de omisión para la búsqueda. Donde trabajo, hay una implementación estándar y se alienta a todos a usarla. Han utilizado los intentos de Patricia para almacenar y recuperar direcciones IP de manera eficiente. Nuevamente, la implementación ya estaba presente.

Soy desarrollador de Java. Java Collection Framework puede resolver mis problemas de estructura de datos del 90%, otro 10% necesita esfuerzo. Creo que si realmente comprende la sofisticada biblioteca estándar escrita por expertos, encontrará que ayudan en la mayoría de los casos.

Las estructuras de datos complejas son difíciles de mantener en el mundo real. Para evitar desordenar el código, dividiré un problema en algunos más pequeños. Cada pequeño problema puede ser resuelto por Java Collection Framework . Quizás la solución no sea la más inteligente (necesita más memoria y más lenta), pero funciona y es fácil de mantener. Es una compensación.

Si debo escribir una estructura de datos compleja, recogeré el libro de texto :)

La estructura de datos más complicada que he usado en el trabajo fue un trie. Sin embargo, eso fue hace veinte años.

El problema con el desarrollo de software industrial es que la mayoría de los programadores industriales no son graduados en informática (CompSci); por lo tanto, las técnicas que el graduado promedio de CompSci da por sentado se consideran demasiado difíciles de mantener para los programadores de pan y mantequilla.

La falta de conocimiento general de CompSci en la industria es un problema grave. Por ejemplo, he perdido la cuenta de la cantidad de desarrolladores de software que he conocido que no entienden expresiones como! (A! = 5 && b! = 3) y a == 5 || b == 3 son lógicamente equivalentes. Cualquiera que sepa cómo aplicar el teorema de DeMorgan puede reconocer que estas expresiones son lógicamente equivalentes. La mayoría de los graduados que no son de CompSci nunca han oído hablar del Teorema de DeMorgan. Si se examina cualquier base de código sustancial, se encontrarán muchas ocurrencias de expresiones que niegan subexpresiones lógicas negativas. La legibilidad del código que contiene subexpresiones lógicas negativas negadas casi siempre se mejora transformando estas expresiones en su forma no negada.

Una vez escribí una cola de calendario (cola de prioridad O (1)) para una simulación basada en eventos en la que el perfil mostró que el montón existente era un cuello de botella.

También lancé un producto que contenía una máquina de estados finitos con aproximadamente 80000 estados; el código para generarlo era un poco complicado, por decir lo menos.

Hace mucho, mucho tiempo, en una galaxia ... Trabajé en un equipo que usó los "amortiguadores de amigos" de Knuth en un RTOS en ensamblador.

Además, Conway's Game of Life con 256 generaciones para un mundo de 1024 x 1024.

Realmente no usé nada demasiado especial, desde cero sería una lista doblemente vinculada .

No es muy emocionante, he usado otras estructuras. Pero su pregunta dijo desde cero.

Un árbol de tablas de hash que contiene listas genéricas de datos financieros, ni siquiera pregunte. A veces desearía ser un vaquero. Ah, la vida simple bajo las estrellas ...

Tuve que escribir una estructura circular de lista doblemente vinculada desde cero para algoritmo Dancing Links para un solucionador de Sudoku. Se sintió como diseñar un cubo de Rubik. Toda la estructura era básicamente una lista de listas, con cada nodo apuntando a otros cuatro.

Una vez utilicé un árbol de longitud de ruta ponderada para un caché especializado. Eso fue divertido. También escribí mis propias rutinas de gestión de almacenamiento dinámico para un malloc()reemplazo, pero mucha gente lo ha hecho.

Después de pensarlo, la estructura de datos más "complicada" que he hecho desde cero es modelar una red de elementos basada en listas doblemente vinculadas. Pero eso fue hace años cuando solía hacer programación a nivel de sistema.

En estos días apenas creo estructuras de datos sofisticadas. La mayor parte ocurre en la base de datos donde decide lo que pone en una tabla, tal vez algún valor precalculado, tal vez la ID de algún registro relacionado para una recuperación rápida para evitar búsquedas innecesarias.

Personalmente, creo que la tarea en cuestión define los medios. ¿Por qué esforzarse por hacer uso de alguna estructura de datos exóticos si no sirve de nada? Y si puedo decir en la mayoría de la programación práctica aplicada, probablemente no haya necesidad de reinventar la rueda.

¿Cuenta una cola prioritaria? Eso aparece en casi todas las aplicaciones en tiempo real que he escrito. Se convirtió en parte de la biblioteca estándar de Java recientemente (Java 1.5).

Aparte de eso, no puedo pensar en nada complicado que realmente quisiera que no haya podido sacar de una biblioteca. No dejaría que eso me detuviera, pero me preguntaría por qué necesitaba una estructura de datos demasiado exótica para que las bibliotecas la incluyeran. Definitivamente, buscaría una implementación de código abierto existente de un filtro trie o bloom o una lista de omisión antes de intentar escribir uno yo mismo.

En general, estoy de acuerdo con su gerente en que el costo de construir y mantener una estructura de datos personalizada demasiado esotérica para que no haya una versión de biblioteca probablemente supere cualquier beneficio de rendimiento derivado de ella. Quisiera que mostraras, a través de la creación de perfiles, que las estructuras de la biblioteca simple están causando una penalización de rendimiento significativa antes de dejarte seguir adelante y optimizarlas con algo elegante. Porque como regla general, es más barato comprar ciclos de procesador que ciclos de ingeniería.