Welche spannenden Algorithmen haben Sie in letzter Zeit "entdeckt"?

Question

Ich lese gerne über neue und clevere Algorithmen. Und ich mag es, über den Tellerrand hinauszuschauen, daher sind alle Arten von Algorithmen aus allen Bereichen der Berechnung willkommen.

Von Zeit zu Zeit lese ich Forschungsberichte, um auf dem neuesten Stand der Forschung zu bleiben und meinen Horizont zu erweitern. Ich lerne auch gerne neue Tricks. Leider neige ich dazu, mich nur auf mein Interessengebiet zu konzentrieren, so dass ich viel Nützliches verpasse.

Lassen Sie uns einfach keine Mainstream-Sachen posten. Schreiben Sie stattdessen über etwas Besonderes, das Sie zum Nachdenken gebracht hat: "Wow - jetzt das ist eine clevere Lösung!".

Answer 1

Ich beginne mit etwas, das jeder gebrauchen kann: die Selbsteinschätzung. http://en.wikipedia.org/wiki/Introsort

Ein neuer Sortieralgorithmus, der das Beste aus Quick-, Insertion- und Heap-Sort kombiniert. Um genau zu sein, ist es kein neuer Algorithmus an sich, sondern ein sehr clevere Kombination.

Sie erhalten die Geschwindigkeit der Schnellsortierung bis zu dem Punkt, an dem die Schnellsortierung in den degenerierten O(n²)-Fall übergeht. Dieser wird fast ohne Kosten erkannt. Die verbleibende Partition wird mit Heap- oder Merge-Sort sortiert. Dadurch wird nicht nur der entartete Fall vermieden, sondern auch eine klar definierte Obergrenze für den Stack-Verbrauch geschaffen.

Die Einfügesortierung kümmert sich - wie üblich - um alle kleinen Partitionen, die vom Schnellsortierdurchgang übrig geblieben sind.

Für mich war das eine neue Entdeckung, denn ich habe aufgehört, Quick-Sort für meine Bewerbungen zu verwenden.

Ich arbeite viel mit eingebetteten Geräten und muss mich um die Stack-Nutzung kümmern. Die Verwendung von quick-sort war immer ein bisschen riskant, weil die geringe Chance besteht, dass es auf dem Stack Amok läuft. Selbst wenn man weiß, dass mit den aktuellen Daten alles in Ordnung ist, weiß man nie, ob jemand später den Code in ein anderes Projekt kopiert und für Daten verwendet, für die er nicht gedacht war.

Dank introspective sort habe ich jetzt die volle Kontrolle über die Stack-Nutzung und erhalte auch einen Leistungsschub.

Answer 2

Es ist nicht etwas völlig Neues oder Aufregendes, aber ich mag die Levenshtein-Abstand .

Die Levenshtein-Distanz wird oft als die Abstand bearbeiten zwischen zwei Zeichenketten und ist im Grunde eine Metrik, die den Unterschied zwischen zwei Zeichenketten misst, indem sie die Mindestanzahl von Operationen zur Umwandlung einer Zeichenkette in die andere zählt.

Ich verwende diesen Algorithmus, um eine Sortierung einer Reihe von Zeichenfolgen vorzuschlagen, die mit der Reihenfolge einer externen Quelle von (möglicherweise unterschiedlichen) Zeichenfolgen übereinstimmt.

Answer 3

Vor kurzem habe ich eine binäre Variante des alten Marchant-Rechenalgorithmus für ganzzahlige Quadratwurzeln wiederentdeckt. Keine Multiplikationen oder Divisionen, nur Addition, Subtraktion und Verschiebungen. Tut mir leid, ich habe den Verweis verloren:

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

Entschuldigung, ich habe vergessen zu sagen, dass dies Ruby ist, für diejenigen, die es nicht kennen.

Answer 4

Ich dachte immer, die magische Quadrat-Wurzel Funktionen in Quake waren sehr clever. Sie ist sehr schnell, weil sie alle langsameren Operationen wie Dividieren usw. vermeidet.

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;
}

Er hat auch eine verwandte magische inverse Quadrat-Wurzel .

Answer 5

Hier ist eine Implementierung des Viterbi-Algorithmus die ich vor kurzem "entdeckt" habe. Hier geht es darum, die optimale Verteilung der Bildtypen bei der Videokodierung zu bestimmen. Viterbi selbst ist manchmal ein bisschen schwer zu verstehen, daher denke ich, dass die beste Methode ein konkretes Beispiel ist.

In diesem Beispiel beträgt die maximale Anzahl aufeinanderfolgender B-Frames 2. Alle Pfade müssen mit einem P-Frame enden.

Eine Pfadlänge von 1 ergibt P als unseren besten Weg, da alle Wege auf einem P-Frame enden müssen, gibt es keine andere Wahl.

Eine Pfadlänge von 2 ergibt BP y _P . "_" ist der beste Weg der Länge 1. Dies gibt uns BP y PP . Jetzt berechnen wir die tatsächlichen Kosten. Nehmen wir für dieses Beispiel an, dass BP am besten ist.

Eine Pfadlänge von 3 ergibt BBP y _B P und __P . "__" ist der beste Weg der Länge 2. Dies gibt uns BBP y PBP y BPP . Jetzt berechnen wir die tatsächlichen Kosten. Nehmen wir für dieses Beispiel an, dass BBP am besten ist.

Eine Pfadlänge von 4 ergibt _BBP y __BP y ___P . "___" ist der beste Weg der Länge 3. Daraus ergeben sich PBBP, BPBP und BBPP. Nun berechnen wir die tatsächlichen Kosten. Nehmen wir für dieses Beispiel an, dass BPBP der beste Weg ist.

Eine Pfadlänge von 4 ergibt __BBP y ___BP y ____P . "____" ist der beste Weg der Länge 4. Dies gibt uns BPBBP y BBPBP y BPBPP .

Moment mal - alle Pfade stimmen darin überein, dass das erste Bild ein B ! Der erste Frame ist also ein B .

Der Vorgang wird so lange wiederholt, bis sie sich einig sind, welcher Frame der erste P-Frame ist, und dann beginnt die Codierung.

Dieser Algorithmus kann an eine Vielzahl von Problemen in vielen Bereichen angepasst werden; es ist auch derselbe Algorithmus, auf den ich in diese Stelle .