Entonces, ¿qué emocionantes algoritmos has "descubierto" recientemente?

Question

Me gusta leer sobre algoritmos nuevos e inteligentes. Y me gusta pensar de forma original, por lo que todo tipo de algoritmos de todos los campos de computación son bienvenidos.

De vez en cuando leo trabajos de investigación para estar al día con la investigación actual y ampliar mi horizonte. También me gusta aprender nuevos trucos. Desafortunadamente, tiendo a concentrarme solo en mi campo de interés, así que echo de menos muchas cosas útiles.

No nos limitemos a publicar cosas convencionales. En cambio, escribe sobre algo especial que te hizo pensar: "¡Guau! ¡Ahora eso es una solución inteligente!".

Answer 1

No es algo completamente nuevo o emocionante, pero me gusta el Levenshtein Distance.

El Levenshtein Distancia se refiere a menudo como la distancia de edición entre dos cadenas y es básicamente una medida que nos indica la diferencia entre dos cadenas contando el número mínimo de operaciones para convertir una cadena a la otra.

Estoy usando este algoritmo para sugerir una clasificación de un número de cadenas para que coincida con el orden de una fuente externa de cadenas (posiblemente diferentes).

Answer 2

Comenzaré con algo que todos puedan usar: tipo introspectivo. http://en.wikipedia.org/wiki/Introsort

Un nuevo tipo de algoritmo que combina lo mejor de la ordenación rápida, de inserción y de pila. Para ser exactos, no es un algoritmo nuevo en sí mismo, sino una combinación inteligente de muy.

Obtiene la velocidad de ordenación rápida hasta el punto en que la ordenación rápida se ejecuta en el caso O (n²) degenerado. Eso se detecta casi sin costo. La partición restante se ordena usando heap o merge-sort. Esto no solo evita el caso degenerado sino que crea un límite superior claramente definido para el uso de la pila también.

La ordenación de inserción se lleva a cabo, como de costumbre, para todas las particiones pequeñas que sobran del pase de clasificación rápida.

Para mí fue un descubrimiento nuevo porque paré para usar la ordenación rápida para mis aplicaciones.

Trabajo mucho en dispositivos integrados y tengo que preocuparme por el uso de la pila. El uso de la ordenación rápida siempre fue un poco arriesgado debido a la remota posibilidad de que se ejecute de forma desordenada en la pila. Incluso si usted sabe que con los datos actuales todo estará bien, nunca se sabe si alguien más tarde cortará el código en un proyecto diferente y lo usará para datos que nunca se mencionó.

Gracias a la clase introspectiva ahora tengo control total sobre el uso de la pila y obtengo un aumento en el rendimiento también.

Answer 3

Aquí hay una implementación del Viterbi algorithm que "descubrí" recientemente. El propósito aquí es decidir la distribución óptima de los tipos de cuadros en la codificación de video. Viterbi en sí es un poco difícil de entender a veces, así que creo que el mejor método es a través del ejemplo real.

En este ejemplo, Max-B consecutivos B-frames es 2. Todas las rutas deben terminar con un P-frame.

La longitud de ruta de 1 nos da P como nuestra mejor ruta, ya que todas las rutas deben terminar en un P-frame, no hay otra opción.

La longitud de la ruta de acceso de 2 nos da BP y _P. "_" es la mejor ruta de longitud 1. Esto nos da BP y PP. Ahora, calculamos los costos reales. Digamos, por el bien de este ejemplo, que BP es lo mejor.

La longitud de la ruta de 3 nos da BBP y _B P y __P. "__" es la mejor ruta de longitud 2. Esto nos da BBP y PBP y BPP. Ahora, calculamos los costos reales. Digamos, por el bien de este ejemplo, que BBP es lo mejor.

La longitud de ruta de 4 nos da _BBP y __BP y ___P. "___" es la mejor ruta de longitud 3. Esto nos da PBBP y BPBP y BBPP. Ahora, calculamos los costos reales. Digamos, por el bien de este ejemplo, que BPBP es el mejor.

La longitud de ruta de 4 nos da __BBP y ___BP y ____P. "____" es la mejor ruta de longitud 4. Esto nos da BPBBP y BBPBP y BPBPP.

Ahora, espere un minuto, todas las rutas coinciden en que el primer fotograma es B. Entonces, el primer fotograma es B.

El proceso se repite hasta que coincidan en qué cuadro es el primer cuadro P, y luego comienza la codificación.

Este algoritmo se puede adaptar a una gran variedad de problemas en muchos campos; también es el mismo algoritmo al que me refería en this post.

Answer 4

Recientemente he redescubierto una variante binaria del antiguo algoritmo de la calculadora Marchant para las raíces cuadradas enteras. No multiplica o divide, solo suma, resta y cambios. Lo siento, he perdido la referencia:

def assert 
    raise "Assertion failed !" if $DEBUG and not yield 
end 

def sqrt(v) 
    value = v.abs 
    residue = value 
    root = 0 
    onebit = 1 
    onebit <<= 8 while (onebit < residue) 
    onebit >>= 2 while (onebit > residue) 
    while (onebit > 0) 
     x = root + onebit 
     if (residue >= x) then 
      residue -= x 
      root = x + onebit 
     end 
     root >>= 1 
     onebit >>= 2 
    end 
    assert {value == (root**2+residue)} 
    assert {value < ((root+1)**2)} 
    return [root,residue] 
end 

$DEBUG = true 

a = sqrt(4141290379431273280) 
puts a.inspect 

Doblemente lo siento, se olvidó de decir que este es Ruby, para los que no conocen.

Answer 5

Me quedé impresionado cuando supe del Burrows-Wheeler block sorting algorithm para la compresión de datos (como se usa en bzip2). ¡Lo sorprendente es que el paso de clasificación es reversible!

Answer 6

Siempre pensé que las funciones magic square-root en Quake eran muy ingeniosas. Es muy rápido, ya que evita cualquiera de las operaciones más lentas como brecha etc.

float SquareRootFloat(float num) { 
    long i; 
    float x, y; 
    const float f = 1.5F; 

    x = num * 0.5F; 
    y = num; 
    i = * (long *) &y; 
    i = 0x5f3759df - (i >> 1); 
    y = * (float *) &i; 
    y = y * (f - (x * y * y)); 
    y = y * (f - (x * y * y)); 
    return num * y; 
} 

También tiene una relacionada magic inverse square-root.

Answer 7

Encontré esta prueba muy útil de que a^n = b^n + c^n pero solo para n = 2.
¡Lamentablemente este comentario es demasiado pequeño para contenerlo!

Answer 8

bioinformática está llena de casos de experimentos que generan cargas de datos en formas extrañas que requieren algoritmos imaginativos para procesar.

an introduction to bioinformatics algorithms es una gran lectura para este tipo de cosas

Answer 9

No es tan llamativo como los otros, pero fue práctico:

((m+n) + (m-n))/2 === m (for any two real numbers m and n)

que estaba usando una lógica consulta de funciones agregadas de SQL contar calificaciones de un artículo. Las calificaciones son +1 y -1. Necesitaba saber la cantidad de calificaciones positivas (m) dadas solo la cantidad total de calificaciones y su suma.

El uso de esta lógica realmente aceleró la consulta y me permitió devolver resultados para artículos con 0 valoraciones.

(no elegir +1 y -1; heredé eso.)

Answer 10

Dynamic programming toma todo su poder con optimal control problems. Muy refrescante.