Tu algoritmo favorito y la lección que te enseñó [cerrado]

StackOverflow https://stackoverflow.com/questions/26301

  •  09-06-2019
  •  | 
  •  

Pregunta

¿Qué algoritmo te enseñó más sobre programación o una característica específica del lenguaje?

Todos hemos tenido esos momentos en los que de repente sabemos, simplemente sabemos, que hemos aprendido una lección importante para el futuro basada en finalmente comprender un algoritmo escrito por un programador que se encuentra un par de pasos más arriba en la escalera evolutiva.¿De quién fueron las ideas y el código que te dieron el toque mágico?

¿Fue útil?

Solución

"Repetir es humano, recurrir es divino", citado en 1989 en la universidad.

PDPublicado por Woodgnome mientras espera la invitación para unirse

Otros consejos

Algoritmos generales:

  • Quicksort (y su análisis de complejidad promedio) muestra que aleatorizar su entrada puede ser algo bueno;
  • árboles equilibrados (árboles AVL por ejemplo), una manera clara de equilibrar los costos de búsqueda/inserción;
  • Dijkstra y Ford-Fulkerson algoritmos sobre gráficos (me gusta el hecho de que el segundo tiene muchas aplicaciones);
  • la familia LZ* de algoritmos de compresión (LZW por ejemplo), la compresión de datos me pareció algo mágica hasta que la descubrí (hace mucho tiempo :));
  • el FFT, ubicuo (reutilizado en muchos otros algoritmos);
  • el simplex algoritmo, ubicuo también.

Relacionado numérico:

  • Algoritmo de Euclides para calcular el mcd de dos números enteros:uno de los primeros algoritmos, simple y elegante, potente, tiene muchas generalizaciones;
  • multiplicación rápida de números enteros (Cooley-Tukey Por ejemplo);
  • Iteraciones de Newton para invertir/encontrar una raíz, un metaalgoritmo muy poderoso.

Relacionado con la teoría de números:

  • Asamblea General Anual-algoritmos relacionados (ejemplos):conduce a algoritmos muy simples y elegantes para calcular pi (¡y mucho más!), aunque la teoría es bastante profunda (Gauss introdujo funciones elípticas y formas modulares a partir de ella, por lo que se puede decir que dio origen a la geometría algebraica...);
  • el tamiz de campo numérico (para factorización de números enteros): muy resultado teórico complicado, pero bastante bueno (esto también se aplica a AKS algoritmo, que demostró que PRIMES está en P).

También disfruté estudiando computación cuántica (corto y Deutsch-Josza algoritmos por ejemplo):esto te enseña a pensar fuera de lo común.

Como puedes ver, estoy un poco predispuesto hacia los algoritmos orientados a las matemáticas :)

Algoritmo de caminos más cortos de todos los pares de Floyd-Warshall

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

He aquí por qué es genial:Cuando aprendes por primera vez sobre el problema del camino más corto en tu curso de teoría de grafos, probablemente comiences con el algoritmo de Dijkstra que resuelve soltero-fuente camino más corto.Es bastante complicado al principio, pero luego lo superas y lo entiendes completamente.

Entonces el profesor dice: "Ahora queremos resolver el mismo problema pero por TODO fuentes".Piensas: "¡Oh Dios, este va a ser un problema mucho más difícil! ¡¡¡Será al menos N veces más complicado que el algoritmo de Dijkstra!!!".

Entonces el profesor te da Floyd-Warshall.Y tu mente explota.Luego empiezas a llorar por lo maravillosamente simple que es el algoritmo.Es sólo un bucle triplemente anidado.Sólo utiliza una matriz simple para su estructura de datos.

La parte más reveladora para mí es la siguiente comprensión:digamos que tienes una solución para el problema A.Entonces tienes un "superproblema" B mayor que contiene el problema A.De hecho, la solución al problema B puede ser más sencilla que la solución al problema A.

Ordenación rápida.Me mostró que la recursividad puede ser poderosa y útil.

Esto puede parecer trivial, pero fue una revelación para mí en ese momento.Estaba en mi primera clase de programación (VB6) y el profesor nos acababa de enseñar sobre números aleatorios y me dio las siguientes instrucciones:"Crea una máquina de lotería virtual.Imagine una bola de cristal llena de 100 pelotas de ping pong marcadas del 0 al 99.Elígelos al azar y muestra su número hasta que todos hayan sido seleccionados, sin duplicados."

Todos los demás escribieron su programa así:Elige una bola, pon su número en una "lista ya seleccionada" y luego elige otra bola.Verifique si ya está seleccionada, si es así, elija otra bola, si no, coloque su número en la "lista ya seleccionada", etc.

Por supuesto, al final estaban haciendo cientos de comparaciones para encontrar las pocas bolas que aún no habían sido elegidas.Fue como volver a tirar las bolas al frasco después de seleccionarlas.Mi revelación fue tirar las pelotas después de recogerlas.

Sé que esto suena abrumadoramente obvio, pero este fue el momento en que el "interruptor de programación" se movió en mi cabeza.Este fue el momento en que la programación pasó de intentar aprender un idioma extranjero extraño a intentar resolver un rompecabezas divertido.Y una vez que hice esa conexión mental entre programación y diversión, realmente nada me detuvo.

La codificación de Huffman sería mía. Originalmente había creado mi propia versión tonta minimizando la cantidad de bits para codificar texto de 8 a menos, pero no había pensado en una cantidad variable de bits dependiendo de la frecuencia.Luego encontré la codificación Huffman descrita en un artículo de una revista y me abrió muchas posibilidades nuevas.

Algoritmo de dibujo lineal de Bresenham Me interesó en la representación de gráficos en tiempo real.Esto se puede utilizar para renderizar polígonos rellenos, como triángulos, para cosas como renderizado de modelos 3D.

Análisis de descenso recursivo - Recuerdo que me impresionó mucho cómo un código tan simple podía hacer algo aparentemente tan complejo.

Clasificación rápida en Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Aunque no podía escribir Haskell en ese momento, entendí este código y con él la recursividad y el algoritmo de clasificación rápida.Simplemente hizo clic y ahí estaba...

El algoritmo iterativo de Fibonacci, porque para mí demostró el hecho de que el código más elegante (en este caso, la versión recursiva) no es necesariamente el más eficiente.

Para elaborar: el enfoque "fib(10) = fib(9) + fib(8)" significa que fib(9) se evaluará como fib(8) + fib(7).Por lo tanto, la evaluación de fib(8) (y, por lo tanto, fib7, fib6) se evaluará dos veces.

El método iterativo (curr = prev1 + prev2 en un bucle for) no se organiza de esta manera, ni requiere tanta memoria ya que son solo 3 variables transitorias, en lugar de n fotogramas en la pila de recursividad.

Tiendo a esforzarme por lograr un código simple y elegante cuando programo, pero este es el algoritmo que me ayudó a darme cuenta de que este no es el fin de escribir un buen software y que, en última instancia, los usuarios finales no lo hacen. No importa cómo se ve tu código.

Por alguna razón me gusta el transformada de Schwartzian

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Donde foo($) representa una expresión de cálculo intensivo que toma $ (cada elemento de la lista por turno) y produce el valor correspondiente que se comparará en sí mismo.

minimax Me enseñó que los programas de ajedrez no son inteligentes, simplemente pueden pensar en más movimientos que tú.

No sé si esto califica como un algoritmo o simplemente como un truco clásico.En cualquier caso, me ayudó a empezar a pensar de forma innovadora.

Intercambia 2 números enteros sin usar una variable intermedia (en C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Ordenación rápida:Hasta que llegué a la universidad, nunca me había preguntado si la fuerza bruta Bubble Sort era la forma más eficiente de clasificar.Simplemente parecía intuitivamente obvio.Pero estar expuesto a soluciones no obvias como Quicksort me enseñó a mirar más allá de las soluciones obvias para ver si hay algo mejor disponible.

Para mí, es el algoritmo de clasificación de montón débil porque muestra (1) cuánto puede influir en el rendimiento una estructura de datos elegida sabiamente (y los algoritmos que trabajan en ella) y (2) que se pueden descubrir cosas fascinantes incluso en archivos antiguos y bien conocidos. cosas.(el tipo de montón débil es la mejor variante de todos los tipos de montón, que fue probado ocho años después.)

Este es lento :)

Aprendí mucho sobre C y computadoras en general al comprender Dispositivo Duffs y Intercambios XOR

EDITAR:

@jason z, ese es mi intercambio XOR :) genial, ¿no?

Por alguna razón, Bubble Sort siempre me ha llamado la atención.No porque sea elegante o bueno, solo porque tenía/tiene un nombre ridículo, supongo.

no tengo un favorito - hay muchos hermosos para elegir - pero uno que siempre me ha parecido intrigante es el Fórmula Bailey-Borwein-Plouffe (BBP), que le permite calcular un dígito arbitrario de pi sin conocer los dígitos anteriores.

RSA me introdujo en el mundo de la aritmética modular, que puede utilizarse para resolver a sorprendente número de interesante problemas!

No me ha enseñado mucho, pero el Algoritmo de Johnson-trotter Nunca deja de sorprenderme.

Diagramas de decisión binaria, aunque formalmente no es un algoritmo sino una estructura de datos, conduce a soluciones elegantes y mínimas para varios tipos de problemas lógicos (booleanos).Fueron inventados y desarrollados para minimizar el número de puertas en el diseño de chips y pueden considerarse como uno de los fundamentos de la revolución del silicio.Los algoritmos resultantes son sorprendentemente simples.

Lo que me enseñaron:

  • una representación compacta de cualquier el problema es importante;lo pequeño es hermoso
  • Se puede utilizar un pequeño conjunto de restricciones/reducciones aplicadas de forma recursiva para lograr esto.
  • Para problemas con simetrías, la transformación a una forma canónica debe ser el primer paso a considerar.
  • no se lee toda la literatura.Knuth se enteró de los BDD varios años después de su invención/introducción.(y pasó casi un año investigándolos)

Para mí, el simple intercambio en Kelly & Pohl's Un libro sobre C demostrar la llamada por referencia me sorprendió cuando lo vi por primera vez.Miré eso y los punteros encajaron en su lugar.Literal...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

El Algoritmo de las Torres de Hanoi Es uno de los algoritmos más bellos.Muestra cómo se puede utilizar la recursividad para resolver un problema de una manera mucho más elegante que el método iterativo.

Alternativamente, el algoritmo recursivo para las series de Fibonacci y el cálculo de potencias de un número demuestran la situación inversa en la que el algoritmo recursivo se utiliza por el bien de la recursividad en lugar de proporcionar un buen valor.

El algoritmo iterativo de Fibonacci, porque para mí demostró el hecho de que el código más elegante (en este caso, la versión recursiva) no es necesariamente el más eficiente.

El método iterativo (curr = prev1 + prev2 en un bucle for) no se organiza de esta manera, ni requiere tanta memoria ya que son solo 3 variables transitorias, en lugar de n fotogramas en la pila de recursividad.

Sabes que Fibonacci tiene una solución de forma cerrada que permite el cálculo directo del resultado en un número fijo de pasos, ¿verdad?Es decir, (finorte - (1 - fi)norte) /sqrt(5).Siempre me parece algo notable que esto produzca un número entero, pero así es.

phi es la proporción áurea, por supuesto;(1 + raíz cuadrada (5)) / 2.

Un algoritmo que genera una lista de números primos comparando cada número con la lista actual de números primos, agregándolo si no se encuentra y devolviendo la lista de números primos al final.Alucinante de varias maneras, una de las cuales es la idea de utilizar el resultado parcialmente completado como criterio de búsqueda principal.

Almacenar dos punteros en una sola palabra para una lista doblemente enlazada me enseñó la lección de que, de hecho, se pueden hacer cosas muy malas en C (con lo que un GC conservador tendrá muchos problemas).

Lo más orgulloso que he estado de una solución fue escribir algo muy similar al paquete DisplayTag.Me enseñó mucho sobre diseño, mantenibilidad y reutilización de código.Lo escribí mucho antes de DisplayTag y estaba incluido en un acuerdo NDA, por lo que no pude abrirlo, pero todavía puedo hablar efusivamente sobre eso en entrevistas de trabajo.

Mapa reducido.Dos conceptos simples que encajan para hacer que una gran cantidad de tareas de procesamiento de datos sean más fáciles de paralelizar.

Oh...y es sólo la base de la indexación masivamente paralela:

http://labs.google.com/papers/mapreduce.html

No es mi favorito, pero el Algoritmo de Miller Rabin porque probar la primalidad me mostró que tener razón casi todo el tiempo es suficiente casi todo el tiempo.(es decir.No desconfíe de un algoritmo probabilístico sólo porque tiene una probabilidad de estar equivocado).

@Krisna Kumar

La solución bit a bit es incluso más divertida que la solución recursiva.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top