implementaciones del mundo real de "algoritmos clásicos"

Question

Me pregunto cuántos de ustedes han implementado una de las ciencias de la computación "classical algorithms" como Dijkstra's algorithm o estructuras de datos (por ejemplo, los árboles binarios de búsqueda) en un mundo real, no académica ¿proyecto?

¿Hay algún beneficio en nuestros dayjobs para conocer estos algoritmos y estructuras de datos cuando hay toneladas de bibliotecas, marcos y API que le dan la misma funcionalidad?

Answer 1

Conocer, o ser capaz de entender estos algoritmos es importante, estas son las herramientas de su oficio . No significa que deba ser capaz de implementar A * en una hora desde la memoria. Pero deberías ser capaz de descubrir cuáles son las ventajas de usar un árbol rojo-negro en comparación con un árbol desequilibrado normal para que puedas decidir si lo necesitas o no. Usted necesita poder juzgar la idoneidad de un algoritmo para resolver su problema. Esto podría sonar demasiado típico de la escuela pero estos "algoritmos clásicos" no fueron inventados para dar preguntas a los estudiantes universitarios, fueron inventados para resolver problemas o mejorar las soluciones actuales, como la matriz, la lista vinculada o la pila son bloques de construcción para escribir un programa, así son algunos de estos. Al igual que en matemáticas, donde pasa de la suma y la resta a la integración y la diferenciación, estas son técnicas avanzadas que le ayudarán a resolver los problemas que existen.

Puede que no sean directamente aplicables a sus problemas o situación laboral, pero a la larga conocerlos le ayudará como ingeniero de software profesional.

Para responder a su pregunta, hice una implementación de A * recientemente para un juego.

algoritmos

Answer 2

Bueno, alguien tiene que escribir las bibliotecas. Mientras trabajaba en una empresa de software de mapas, implementé Dijkstra, así como árboles de búsqueda binaria, b-trees, n-ary trees, bk-trees y modelos de markov ocultos.

Además, si todo lo que quiere es un único algoritmo "conocido", y también quiere la libertad de especializarlo y optimizarlo si se vuelve crítico para el rendimiento, incluso una biblioteca completa parece una mala elección.

Answer 3

En mi lugar de trabajo anterior, que era una empresa EDA, implementamos versiones de los algoritmos de Prim y Dijsktra, estructuras de datos de conjuntos disjuntos, búsqueda A * y más. Todos estos tenían una significación del mundo real. Creo que esto depende del dominio del problema: algunos dominios son más intensivos en algoritmos y otros menos.

Habiendo dicho eso, hay una línea fina para caminar: no veo ningún motivo comercial para volver a implementar STL o Java Generics. En muchos casos, una biblioteca estándar es mejor que "inventar una rueda". Cuanto más cerca esté de su aplicación principal, más puede ser necesario implementar un algoritmo de libro de texto o una estructura de datos.

Answer 4

¿Hay un beneficio para nuestros dayjobs en conocer estos algoritmos y estructuras de datos cuando hay toneladas de las bibliotecas, los marcos y las API que le dan la misma funcionalidad?

La biblioteca no sabe cuál es el dominio de su problema y no podrá elegir el algoritmo correcto para realizar el trabajo. Es por eso que creo que es importante saber sobre ellos: entonces USTED puede hacer la elección correcta de los algoritmos para resolver SU problema.

Answer 5

¿Hay algún beneficio en comprender sus herramientas, en lugar de simplemente saber que existen?

Sí, por supuesto que sí. Tomando un ejemplo trivial, ¿no crees que hay un beneficio en saber cuál es la diferencia List (o la implementación de matriz dinámica equivalente de tu idioma) y LinkedList (o el equivalente de tu idioma)? Es muy importante saber que uno tiene un tiempo de acceso aleatorio constante, mientras que el otro es lineal. Y uno requiere N copias si inserta un valor en el medio de la secuencia, mientras que el otro puede hacerlo en tiempo constante.

¿No cree que es una ventaja entender que el mismo algoritmo de clasificación no siempre es óptimo? Eso para datos casi ordenados, quicksort apesta, por ejemplo? Simplemente llamando a Sort() y esperando lo mejor puede volverse ridículamente caro si no entiendes lo que sucede bajo el capó.

Por supuesto, hay muchos algoritmos que probablemente no necesite, pero aún así, el solo hecho de entender cómo funcionan puede hacer que le resulte más fácil encontrar algoritmos eficientes para resolver otros problemas no relacionados.

Answer 6

Si nunca trabaja con código de rendimiento crítico, considérese afortunado. Sin embargo, considero este escenario poco realista. Los problemas de rendimiento pueden ocurrir en cualquier lugar. Y luego es necesario saber cómo solucionar ese problema. Obviamente, el mero hecho de conocer algunos nombres de algoritmos no es suficiente aquí, a menos que desee implementarlos todos y probarlos uno tras otro.

No, conocer (al menos algunos de) el funcionamiento interno de diferentes algoritmos es importante para medir sus fortalezas y debilidades y para analizar cómo manejarían su situación.

Obviamente, si hay una biblioteca que ya está implementando exactamente lo que necesita, tiene mucha suerte. Pero seamos sinceros, incluso si hay una biblioteca de este tipo, su uso a menudo no es completamente sencillo (al menos, las interfaces y la representación de datos a menudo tienen que adaptarse) por lo que aún es bueno saber qué esperar.

Answer 7

A * para un clon Pac Man. Me tomó semanas llegar realmente, pero hasta el día de hoy lo considero una cosa de belleza.

Answer 8

He tenido que implementar algunos de los algoritmos clásicos del análisis numérico. Era más fácil escribir el mío que conectarme a una biblioteca existente. Además, tuve que escribir variaciones en algoritmos clásicos porque el caso del libro de texto no se ajustaba a mi aplicación.

Para estructuras de datos clásicas, casi siempre uso las bibliotecas estándar, como STL para C++. Recientemente, una vez que pensé que STL no tenía la estructura que necesitaba (un montón) hice solo, para que alguien me dijera casi inmediatamente que no tenía que hacer eso.

Answer 9

se utiliza una aplicación de cosecha propia de un generador de números p-azar de Knuth SemiNumeric como una ayuda en algún procesamiento estadístico

Answer 10

clásicos que se han utilizado en trabajo real:

• una ordenación topológica

• Un árbol rojo-negro (aunque lo haré confesar que yo sólo tenía que poner en práctica inserciones para esa aplicación y solo se usó en un prototipo). Esto se utilizó para implementar una estructura de tipo 'dict' ordenado en Python.

• Una cola de prioridad

• Las máquinas de estado de varios tipos

• Probablemente uno o dos más no puedo recordar.

En cuanto a la segunda parte de la pregunta:

La comprensión de cómo funcionan los algoritmos, su complejidad y la semántica se acostumbra en una base bastante regular. También informan el diseño de los sistemas. Ocasionalmente, uno tiene que hacer cosas que impliquen análisis o manejo de protocolo, o algún cálculo que sea levemente inteligente. Tener un conocimiento práctico de lo que hacen los algoritmos, cómo funcionan, qué tan caros son y dónde uno puede encontrarlos en el código de la biblioteca es una gran ayuda para saber cómo evitar la reinvención de la rueda.

Answer 11

Los algoritmos clásicos suelen asociarse con algo glamoroso, como los juegos, la búsqueda web o el cálculo científico. Sin embargo, tuve que usar algunos de los algoritmos clásicos para una mera aplicación empresarial.

que estaba construyendo una herramienta de migración de metadatos, y tuve que usar clasificación topológica para la resolución de dependencias, diversas formas de recorridos de gráficos para consultas sobre los metadatos, y una variación modificada de Tarjan unión-estructura de datos para la partición bosque-como metadatos estructurados a los árboles

Esa fue una experiencia realmente satisfactoria. La mayoría de esos algoritmos se implementaron antes, pero sus implementaciones carecían de algo que necesitaría para mi tarea. Es por eso que es importante entender sus aspectos internos.

Answer 12

Uso el algoritmo Levenshtein distance para ayudar a implementar un '¿Quisiste decir [palabra sugerida]?' función en nuestra búsqueda en el sitio web.

Funciona bastante bien cuando se combina con nuestro sistema de "etiquetado", que nos permite asociar palabras adicionales (distintas de las de título/descripción/etc.) con elementos en la base de datos. \

No es perfecto de ninguna manera, pero es mucho mejor que la mayoría de las búsquedas de sitios corporativos, si no lo digo yo;)