¿Cuáles son las razones para aprender diferentes algoritmos / estructuras de datos que tienen el mismo propósito?

92

Me he estado preguntando acerca de esta pregunta desde que era estudiante de pregrado. Es una pregunta general, pero elaboraré con ejemplos a continuación.

He visto muchos algoritmos, por ejemplo, para problemas de flujo máximo, conozco alrededor de 3 algoritmos que pueden resolver el problema: Ford-Fulkerson, Edmonds-Karp y Dinic, con Dinic con la mejor complejidad.

Para estructuras de datos, por ejemplo, montones, hay montones binarios, montones binomiales y montones de Fibonacci, con el montón de Fibonacci que tiene la mejor complejidad general.

Lo que me mantiene confuso es: ¿hay alguna razón por la que necesitemos conocerlos a todos? ¿Por qué no simplemente aprender y familiarizarse con la mejor complejidad?

Sé que es mejor si los conocemos a todos, solo quiero saber si hay razones "más válidas", como algunos problemas / algoritmos que solo pueden resolverse usando A pero no B , etc.

shole
fuente
17
Como siempre digo: estos (por lo general) no es el "mejor". Una vez que define explícitamente lo que quiere decir con "mejor", la respuesta se vuelve obvia.
Raphael
2
Esta es una buena pregunta, pero habla de lo que yo consideraría un agujero en su educación que podría considerar corregir. Esa es una experiencia práctica, si en realidad no ha escrito estos algoritmos durante su educación, podría considerar escribirlos ahora, sospecho que la respuesta a esta pregunta se habría vuelto rápidamente obvia a medida que intenta encontrar usos para ellos.
Sam
@Sam Desde mi experiencia, lo que pensé es que en las conferencias, o en algunos libros de texto, son informativos, introducen muchos algoritmos, análisis, etc., pero no muchos casos prácticos o escenarios de muestra que A superen a B. Pueden cubrir un género de algoritmos de la A a la Z, y algunos problemas de tarea, pero para mí todos pueden resolverse solo con A, o solo con Z, etc., por lo tanto, se hizo la pregunta.
shole
55
Si insiste en dejar de lado el interés académico, la mejor razón práctica para aprender algoritmos menos que óptimos es para que pueda reconocerlos por lo que son y optimizarlos refactorizándolos a los óptimos. No puedes actualizar un arco y una flecha a una pistola si no sabes para qué sirven un arco y una flecha.
candied_orange
1
De hecho, hemos propuesto un sitio StackExchange para ayudar específicamente con preguntas de educación CS como esta. Venga a apoyarnos aquí: area51.stackexchange.com/proposals/92460/…
vk2015

Respuestas:

121

Hay un libro de texto en espera de ser escrito en algún momento, con el título de trabajo Estructuras de datos, algoritmos y compensaciones . Casi todos los algoritmos o estructuras de datos que probablemente aprenderá a nivel de pregrado tienen alguna característica que lo hace mejor para algunas aplicaciones que para otras.

Tomemos la clasificación como un ejemplo, ya que todos están familiarizados con los algoritmos de clasificación estándar.

En primer lugar, la complejidad no es la única preocupación. En la práctica, los factores constantes son importantes, por lo que (por ejemplo) la ordenación rápida tiende a usarse más que la ordenación en montón aunque la ordenación rápida tiene una terrible complejidad en el peor de los casos.

En segundo lugar, siempre existe la posibilidad de que te encuentres en una situación en la que estás programando bajo restricciones extrañas. Una vez tuve que hacer una extracción cuantílica de una colección de muestras de tamaño modesto (más o menos 1000) lo más rápido posible, pero estaba en un pequeño microcontrolador que tenía muy poca memoria de lectura y escritura de repuesto, por lo que descartó la mayoría de ordenar algoritmos. La ordenación de Shell fue la mejor compensación, ya que era subcuadrática y no requería memoria adicional.O(nlogn)

En otros casos, las ideas de un algoritmo o estructura de datos podrían ser aplicables a un problema de propósito especial. El ordenamiento de burbujas parece ser siempre más lento que el de inserción en hardware real, pero la idea de realizar un pase de burbuja es a veces exactamente lo que necesita.

Considere, por ejemplo, algún tipo de visualización en 3D o videojuego en una tarjeta de video moderna, donde le gustaría dibujar objetos en orden desde el más cercano a la cámara hasta el más alejado de la cámara por razones de rendimiento, pero Si no obtiene el pedido exacto, el hardware se encargará de ello. Si se está moviendo por el entorno 3D, el orden relativo de los objetos no cambiará mucho entre fotogramas, por lo que realizar una pasada de burbuja en cada fotograma podría ser una compensación razonable. (El motor Source de Valve hace esto para los efectos de partículas).

Hay persistencia, concurrencia, localidad de caché, escalabilidad en un clúster / nube y una serie de otras posibles razones por las cuales una estructura de datos o algoritmo puede ser más apropiado que otro, incluso dada la misma complejidad computacional para las operaciones que le interesan.

Dicho esto, eso no significa que deba memorizar un montón de algoritmos y estructuras de datos por si acaso. La mayor parte de la batalla es darse cuenta de que hay una compensación para ser explotada en primer lugar, y saber dónde buscar si cree que podría haber algo apropiado.

Seudónimo
fuente
77
Gran respuesta con excelentes ejemplos! No sabía que incluso el pase de burbujas tiene su uso práctico en el mundo real ...
shole
1
@shole No tengo mucha experiencia en el negocio de los juegos, pero todo lo anterior es importante en diversos grados. (Obviamente, el tipo de algoritmos, estructuras de datos y matemáticas que necesitas para los juegos son probablemente diferentes de los requeridos para bases de datos o bioinformática o lo que tienes). Si yo fuera tú, iría aquí y comenzaría a mirar: handmadehero. org También puede valer la pena estar al acecho en gamedev.stackexchange.com
Seudónimo
1
La eficiencia de la memoria caché es un factor importante que está poco investigado (google "muro de memoria").
Raphael
66
Cuidado, Quicksort es mucho más rápido en promedio que Heapsort, pero Heapsort es más consistente (su variación en el tiempo de ejecución es menor y el peor de los casos es mucho mejor). Y el salto de Heapsort en la matriz frente a los escaneos lineales de Quicksort de izquierda a derecha hacen una gran diferencia una vez que el caché / paginación entra en juego.
vonbrand
1
@shole ¿Qué tipo de desarrollo de juegos te interesa? Hay al menos dos subcampos muy diferentes, gráficos en 3D y jugabilidad (que incluye IA). Solo tengo experiencia con gráficos, pero puedo decir que las estructuras de datos y las matemáticas son extremadamente importantes en gráficos y algoritmos también en menor medida. Si está utilizando un motor, la mayoría de estas cosas serán atendidas, pero aún debe comprender las matemáticas básicas de la geometría 3D.
cabeza de jardín
51

Además del hecho de que hay miles de medidas de costos (tiempo de ejecución, uso de memoria, errores de caché, predicciones erróneas de ramas, complejidad de implementación, factibilidad de verificación ...) en miles de modelos de máquinas (TM, RAM, PRAM, ...) , el promedio frente al peor de los casos, así como las consideraciones de amortización para sopesar entre sí, a menudo también hay diferencias funcionales más allá del alcance de la especificación básica del libro de texto.

Algunos ejemplos:

  • Mergesort es estable donde Quicksort no lo es.
  • Los árboles de búsqueda binarios le dan una iteración en orden, las tablas hash no.
  • Bellman-Ford puede lidiar con pesos de borde negativos, Dijkstra no puede.

También hay que hacer consideraciones didácticas :

  • ¿Qué tan fácil es entender una solución más complicada antes que las más simples? (Árboles AVL (y su análisis) sin BST; Dinic sin Ford-Fulkerson; ...)
  • ¿Ves los mismos principios y patrones cuando estás expuesto a una sola solución por problema en comparación con estar expuesto a muchas soluciones?
  • ¿La exposición a una sola solución por problema proporciona suficiente capacitación (hacia el dominio)?
  • ¿Debería saber la amplitud de las soluciones que se han encontrado (para evitar que reinvente la rueda una y otra vez)?
  • Cuando se expone a una sola solución por problema, ¿comprenderá otras soluciones que encuentre en la naturaleza (por ejemplo, en una biblioteca de programación del mundo real)?

  1. Esto es algo que vemos mucho de los tipos de programadores que no tienen una rica caja de herramientas CS a su disposición.
Rafael
fuente
44
¡+1 por incluir fundamentos didácticos! Relacionado con varios de los fundamentos (especialmente el segundo y el tercero), ver cómo se desarrollan y optimizan los algoritmos y las estructuras de datos enseña técnicas de desarrollo y optimización y una comprensión de las compensaciones (aprender no solo "qué" sino también "cómo" y "por qué" )
Paul A. Clayton
2
Una consideración adicional es que el análisis de las diferentes alternativas ofrece ejemplos de herramientas útiles para analizar nuevos algoritmos para configuraciones quizás inusuales.
vonbrand
1
Buen punto, @vonbrand. El análisis de complejidad amortizada se inventó para comprender el comportamiento de los árboles de separación, pero los árboles de separación rara vez se usan en la práctica. Bueno, no extienda los árboles como se publicó, de todos modos. El núcleo de Windows NT utiliza famosos árboles de despliegue para implementar mapas de memoria virtual, pero no se reordena en cada búsqueda.
Seudónimo
1
@vonbrand Sí. Sin embargo, entendería cómo alguien principalmente interesado en la dimensión de caja de herramientas en una clase de algoritmos se burlaría de esa razón.
Raphael
7

En el mundo real , en algún momento es probable que esté trabajando en un software que ha sido escrito por un equipo de otras personas. ¡Parte de este software habrá sido escrito antes de que nacieras!

Para comprender los algoritmos / estructuras de datos que se utilizan, es muy útil conocer una gran cantidad de algoritmos / estructuras de datos, incluidas las opciones que ya no se consideran "estado del arte".

También tendrá que trabajar en algoritmos que no son estándar y que solo se usan en la aplicación en la que está trabajando. Cuando tenga que mejorar estos algoritmos, encontrará que su cerebro se ha llenado de métodos útiles para mejorar los algoritmos, ya que ha estudiado cómo otras personas han mejorado los algoritmos.

Esto es lo que diferencia a alguien que ha estudiado informática aparte de alguien que acaba de aprender a programar. En la mayoría de los trabajos en los que he trabajado, ha habido un tiempo en que al estudiar ciencias de la computación pude resolver un problema que un programador "aprendido de los libros" no pudo, pero el 95% de las veces descubrí que haber estudiado ciencias de la computación no me daba ninguna ventaja. sobre otros programadores experimentados .

Ian Ringrose
fuente
a menos que el 95% de las cosas que intenta resolver estén relacionadas con el aprendizaje automático. No puedo ver cómo el programador normal puede tener la oportunidad correcta de intentar cualquiera de los problemas que enfrentan los problemas reales de ML.
Pinocho
3
Objetivo: conseguir un trabajo con una tasa superior al 5%.
Raphael
Recuerde que estudiar CS ha sido una excelente manera de reunir conocimiento sobre algoritmos y estructuras de datos. La codificación es la mejor ocupación, para los codificadores.
barba gris
5

Muchas personas han mencionado con razón que a menudo no hay un mejor algoritmo, depende de la situación.

También existe la posibilidad de que algún día te encuentres con una situación desconocida. Cuantos más algoritmos conozca, más posibilidades tendrá de conocer uno que sea casi una solución que pueda usar como base.

Bloke Down The Pub
fuente
55
Esta respuesta solo repite puntos de los anteriores.
Raphael
1

Muchas respuestas geniales, creo que falta algo, aunque la respuesta de Raphael menciona esto de alguna manera.

La facilidad de implementación también es algo a tener en cuenta.
Eso generalmente no es un problema con los algoritmos de clasificación, porque la mayoría de las plataformas / lenguajes ya tienen uno implementado (y a menudo mejor que lo que podría hacer), pero es posible que no haya algoritmos más inusuales disponibles.
Dependiendo de su problema, es posible que no necesite el mejor algoritmo absoluto si el tiempo de implementación es de 1 día versus 2 semanas.

Leherenn
fuente