Kann jemand potenziell effizientere Algorithmen finden, um die folgende Aufgabe zu erfüllen?:
Geben Sie für jede gegebene Permutation der ganzen Zahlen 0 bis 7 den Index zurück, der die Permutation lexikographisch beschreibt (indexiert von 0, nicht 1).
Zum Beispiel
factorial(7)-1 ) zurückgeben. Mein aktueller Code sieht so aus:
%Vor%Ich frage mich, ob es irgendeine Möglichkeit gibt, die Anzahl der Operationen zu reduzieren, indem ich diese innere Schleife entferne, oder wenn ich bedingte Verzweigungen auf irgendeine Weise reduzieren kann (außer dem Abrollen - mein aktueller Code ist eigentlich eine abgerollte Version der obigen ), oder wenn es clevere, bitweise Hacks oder schmutzige C-Tricks gibt, um zu helfen.
Ich habe bereits versucht,
zu ersetzen %Vor%mit
%Vor%und ich habe es auch versucht
%Vor%Beide Ersetzungen haben tatsächlich zu schlechteren Leistungen geführt.
Und bevor irgendjemand es sagt - JA ist das ein riesiger Leistungsengpass: derzeit sind etwa 61% der Programmlaufzeit in dieser Funktion verbraucht, und NEIN, ich möchte keine Tabelle mit vorberechneten Werten haben.
>Abgesehen von diesen sind irgendwelche Vorschläge willkommen.
Ich weiß nicht, ob das hilft, aber hier ist eine andere Lösung:
%Vor%Ich konnte die innere Schleife nicht loswerden, also ist die Komplexität im schlechtesten Fall o (n log (n)), aber im besten Fall o (n), im Gegensatz zu deiner Lösung, die o ist (n log (n) ) in allen Fällen.
Alternativ können Sie die innere Schleife durch die folgenden ersetzen, um einige ungünstigste Fälle auf Kosten einer weiteren Verifizierung in der inneren Schleife zu entfernen:
%Vor%Erläuterung :
(oder besser gesagt: "Wie ich mit diesem Code endete", ich denke es ist nicht so anders als deins, aber es kann dir vielleicht Ideen einbringen) (Für weniger Verwirrung habe ich stattdessen Buchstaben und Ziffern und nur vier Zeichen verwendet)
%Vor%Erste "Reflexion" :
Ein Entropie-Standpunkt. abcd haben die geringste "Entropie". Wenn ein Charakter an einem Ort ist, der "nicht sein sollte", erzeugt er Entropie, und je früher die Entropie ist, desto größer wird sie.
Für bcad zum Beispiel ist lexikographischer Index 8 = (( 1 * 3 + 1 ) * 2 + 0 ) * 1 + 0 und kann so berechnet werden:
%Vor%Beachten Sie, dass die letzte Operation immer nichts bewirkt, deshalb "i
Erstes Problem (pb1):
Für adcb zum Beispiel funktioniert die erste Logik nicht (es führt zu einem lexikographischen Index von ((0 * 3 + 2) * 2+ 0) * 1 = 4), weil cd = 0, aber es erzeugt Entropie c vor b setzen. Ich habe x deswegen hinzugefügt, es stellt die erste Ziffer dar, die noch nicht platziert wurde. Mit x kann diff nicht negativ sein. Für adcb ist lexikographischer Index 5 = (( 0 * 3 + 2 ) * 2 + 1 ) * 1 + 0 und kann berechnet werden auf diese Weise:
%Vor%Zweites Problem (pb2):
Für cbda zum Beispiel ist lexikographischer Index 15 = ((2 * 3 + 1) * 2 + 1) * 1 + 0, aber die erste Reflexion ergibt: ((2 * 3 + 0) * 2 + 1 ) * 1 + 0 = 13 und die Lösung von pb1 ergibt ((2 * 3 + 1) * 2 + 3) * 1 + 0 = 17. Die Lösung für pb1 funktioniert nicht, weil die beiden letzten Zeichen d sind und a, also d - ein "means" 1 anstelle von 3. Ich musste die Zeichen zählen, die vor dem Zeichen vor dem Zeichen stehen, aber nach x, also musste ich eine innere Schleife hinzufügen.
Alles zusammenfügen :
Dann erkannte ich, dass pb1 nur ein spezieller Fall von pb2 war, und dass, wenn du x entfernst und du einfach diff = A [i] nimmst, enden wir mit der unnested Version deiner Lösung (mit factorial wenig berechnet durch wenig, und mein Diff entspricht Ihrem x).Im Grunde ist mein "Beitrag" (denke ich), eine Variable x hinzuzufügen, die es vermeiden kann, die innere Schleife zu machen, wenn Diff gleich 0 oder 1 ist, auf Kosten der Überprüfung, ob Sie x und tun inkrementieren müssen wenn ja.
Ich habe auch überprüft, ob du x in der inneren Schleife inkrementieren musst (if (A [j] == x + 1)), denn wenn du zum Beispiel badce nimmst, wird x am Ende sein, weil a nach b kommt , und du wirst die innere Schleife noch einmal betreten und auf c treffen. Wenn du x in der inneren Schleife kontrollierst, hast du bei d keine andere Wahl, als die innere Schleife zu machen, aber x wird auf c aktualisiert, und wenn du auf c triffst, wirst du nicht in die innere Schleife eintreten. Sie können diese Überprüfung entfernen, ohne das Programm zu unterbrechen.
Mit der alternativen Version und dem Check in der inneren Schleife macht es 4 verschiedene Versionen. Die Alternative mit der Kontrolle ist diejenige, in die man weniger die innere Schleife einträgt, also in Bezug auf "theoretische Komplexität" ist es die beste, aber in Bezug auf die Leistung / Anzahl der Operationen, weiß ich nicht.
Hoffe, das alles hilft (da die Frage ziemlich alt ist und ich nicht alle Antworten im Detail gelesen habe). Wenn nicht, hatte ich immer noch Spaß dabei. Entschuldigung für die lange Post. Außerdem bin ich neu bei Stack Overflow (als Mitglied) und nicht als Muttersprachler, also sei bitte nett und zögere nicht, mich wissen zu lassen, ob ich etwas falsch gemacht habe.
Sagen Sie, für eine M-stellige Sequenz-Permutation können Sie aus Ihrem Code die lexikographische SN-Formel erhalten, die ungefähr so aussieht: Am-1 * (m-1)! + Am-2 * (m-2)! + ... + A0 * (0)! , wobei Aj zwischen 0 und j liegt. Sie können SN von A0 * (0) !, dann A1 * (1) !, ..., dann Am-1 * (m-1)! Berechnen und diese addieren (nehmen wir an, dass Ihr Integer-Typ nicht überläuft), Sie müssen die Faktorien nicht rekursiv und wiederholt berechnen. Die SN-Nummer ist ein Bereich von 0 bis M! -1 (weil Summe (n * n !, n in 0,1, ... n) = (n + 1)! - 1)
Wenn Sie faktoriell nicht rekursiv berechnen, kann ich an nichts denken, was eine große Verbesserung bringen könnte.
Es tut mir leid, dass ich den Code etwas verspätet gepostet habe. Ich habe nur etwas recherchiert und folgendes gefunden: Ссылка Nach diesem Autor kann die Multiplikation von ganzen Zahlen 40 mal schneller sein als die Division durch ganze Zahlen. Floating-Zahlen sind nicht so dramatisch, aber hier ist reine Ganzzahl.
%Vor%Das ist der ganze Profiling-Code, ich habe nur den Test in Linux ausgeführt, Code wurde mit G ++ 8.4 kompiliert, mit '-std = c ++ 11 -O3' Compiler-Optionen. Um fair zu sein, habe ich Ihren Code leicht umgeschrieben, die N vorberechnen! und gebe es in die Funktion, aber es scheint, das hilft nicht viel.
Das Leistungsprofil für N = 9 (362.880 Permutationen) lautet:
Das Leistungsprofil für N = 10 (3.628.800 Permutationen) lautet:
Die erste Zahl ist Ihre ursprüngliche Funktion, die zweite ist die neu geschriebene Funktion, die N! Eingereicht, die letzte Nummer ist mein Ergebnis. Die Permutationsgenerierungsfunktion ist sehr primitiv und läuft langsam, aber solange alle Permutationen als Testdatensatz generiert werden, ist das in Ordnung. Diese Tests werden übrigens auf einem Quad-Core-Desktop mit 3,1 GHz und 4 GB ausgeführt, auf dem Ubuntu 14.04 läuft.
BEARBEITEN: Ich habe einen Faktor vergessen, den die erste Funktion möglicherweise benötigt, um den lexi_numbers Vektor zu erweitern, also lege ich einen leeren Anruf vor dem Timing ab. Danach sind die Zeiten 333, 334, 275.
BEARBEITEN: Ein anderer Faktor, der die Leistung beeinflussen könnte, verwende ich long integer in meinem Code, wenn ich diese 2 'long' zu 2 'int' ändere, wird die Laufzeit: 334, 333, 264.
%Vor%Tags und Links c c++ permutation mathematical-optimization lexicographic