Reimplementación de estructuras de datos en el mundo real

Question

El tema de la clase de algoritmos hoy era la reimplementación de estructuras de datos, específicamente ArrayList en Java. El hecho de que pueda personalizar una estructura de varias maneras definitivamente me interesó, particularmente con las variaciones de los métodos add() & iterator.remove().

¿Pero está reimplementando y personalizando una estructura de datos algo que es de más interés para los académicos frente a los programadores del mundo real? ¿Alguien ha vuelto a implementar su propia versión de una estructura de datos en una aplicación/programa comercial, y por qué eligió esa ruta en la implementación de su idioma particular?

Answer 1

Saber cómo se implementan y se pueden implementar las estructuras de datos es definitivamente de interés para todos, no solo para los académicos. Aunque lo más probable es que no reimplemente una estructura de datos si el lenguaje ya proporciona una implementación con funciones y características de rendimiento adecuadas, es muy posible que tenga que crear su propia estructura de datos componiendo otras estructuras de datos ... o puede necesitar implementar una estructura de datos con un comportamiento ligeramente diferente a una estructura de datos conocida. En ese caso, sin duda tendrá que saber cómo se implementa la estructura de datos original. Alternativamente, puede terminar necesitando una estructura de datos que no existe o que proporciona un comportamiento similar a una estructura de datos existente, pero la forma en que se utiliza requiere que se optimice para un conjunto diferente de funciones. Nuevamente, tal situación requeriría que usted supiera cómo implementar (y alterar) la estructura de datos, por lo que sí es interesante.

Editar
Soy no abogando que reimplementar estructuras de datos existentes! No hagas eso. Lo que estoy diciendo es que el conocimiento tiene una aplicación práctica. Por ejemplo, puede que necesite crear una estructura de datos de mapa bidireccional (que puede implementar componiendo dos estructuras de datos de mapa unidireccionales), o puede necesitar crear una pila que realice un seguimiento de una variedad de estadísticas (como min, max, significa) mediante el uso de una estructura de datos de pila existente con un tipo de elemento que contiene el valor, así como estas diversas estadísticas. Estos son algunos ejemplos triviales de cosas que podría necesitar implementar en el mundo real.

Answer 2

He vuelto a implementar algunas de las estructuras de datos, funciones y clases integradas en un idioma en varias ocasiones. Como desarrollador integrado, la razón principal por la que lo haría es por la velocidad o la eficiencia. Las bibliotecas y tipos estándar fueron diseñados para ser útiles en una variedad de situaciones, pero hay muchos casos en los que puedo crear una versión más especializada que se personaliza para aprovechar las características y limitaciones de mi plataforma actual. Si el idioma no proporciona una forma de abrir y modificar las clases existentes (como se puede hacer en Ruby, por ejemplo), la reimplementación de la clase/función/estructura puede ser el único camino a seguir.

Por ejemplo, un sistema en el que trabajé usaba una CPU MIPS que era rápida cuando se trabajaba con números de 32 bits, pero más lenta cuando se trabaja con las más pequeñas. Recribí varias estructuras de datos y funciones para usar enteros de 32 bits en lugar de enteros de 16 bits, y también especifiqué que los campos estuvieran alineados con los límites de 32 bits. El resultado fue un aumento de velocidad notorio en una sección de código que estaba embotellando otras partes del software.

Dicho esto, no fue un proceso trivial. Terminé teniendo que modificar todas las funciones que usaban esa estructura y terminé teniendo que volver a escribir varias funciones de biblioteca estándar también. En esta instancia particular, los beneficios superan el trabajo. En el caso general, sin embargo, generalmente no vale la pena el problema. Existe un gran potencial para problemas difíciles de depurar, y casi siempre es más trabajo de lo que parece. A menos que tenga requisitos específicos o restricciones que las estructuras/clases existentes no cumplan, recomendaría no volver a implementarlas.

Como menciona Michael, de hecho es útil saber cómo para volver a implementar las estructuras, incluso si nunca lo hace. Puede encontrar un problema en el futuro que pueda resolverse aplicando los principios y las técnicas utilizadas en las estructuras de datos existentes.