Benchmark-Tests und schnelle Analyse von Permutationsalgorithmen

Ich beschloss, diese kleine Rezension auf Englisch zu schreiben, in der Hoffnung, einen neuen Trend zu beginnen, von dem ich erwarte, dass er die Interkommunikation verbessern wird (Macht nichts! Es ist nur eine globalistische Idee eines jungen Kosmopoliten).

Ich fordere Sie auf, diesen Beitrag auf Englisch zu beantworten, auch wenn Sie einige Schwierigkeiten mit dieser Sprache haben. Ich schreibe gerade kein Gedicht und ich denke, wir können eine Verlegenheit über unsere Englischkenntnisse vermeiden. Ich werde jedoch über einige poetische Themen sprechen - Natürlich über Kombinatorik und insbesondere über das Erzeugen von Objekten. Ich meine Permutationen. Beginnen wir mit den Worten, mit denen alle Märchen normalerweise begonnen werden: Es war einmal auf Habrahabr ein interessantes Manuskript über die Erzeugung von Superpermutationen veröffentlicht worden (oder wurde, ich weiß nicht, vielleicht wurde es veröffentlicht). Dieses Thema hat einige Habrauser dazu gebracht, Code zu schreiben (siehe Kommentare), und ich auch. Und tatsächlich führte mich dieses Ereignis erneut zu einem alten Problem der Beschleunigung und des Testens von Algorithmen.

Ich bin nicht gut genug in mathematischen Sprachen und Formeln, daher drucke ich jetzt nur drei verschiedene Algorithmen, die ich in C89 codiert habe:

1. Johnson-Trotter-Algorithmus
2. Naryana-Algorithmus
3. Algorithmus aus diesem Habrpost , entwickelt von Mrrl (A. Astrelin)

Alle oben genannten Algorithmen sind nicht rekursiv.

Meine Version des Johnson-Trotter-Algorithmus ist meiner Meinung nach nicht die beste. Trotzdem beeile ich mich, Ihnen die Ergebnisse zu zeigen, die es für n = 10 erzeugt.

Zeit mit Konsolenausgabe (bedeutet printf)
echte 1m19.410s
Benutzer 0m31.899s
sys 0m36.253s

Zeit ohne Konsolenausgabe
echte 0m2.241s
Benutzer 0m2.236s
sys 0m0.004s

Mein Verstion von Mrrl-Code

Mit Konsolenausgabe
echte 1m11.565s
Benutzer 0m27.429s
sys 0m32.997s

Ohne Konsolenausgabe
echte 0m0.489s
Benutzer 0m0.486s
sys 0m0.002s

Der letzte Naryana-ähnliche Algorithmus liefert ein solches Ergebnis

Mit Konsolenausgabe
echte 1m10.223s
Benutzer 0m8.617s
sys 0m38.165s

Ohne Konsolenausgabe
echte 0m0.453s
Benutzer 0m0.449s
sys 0m0.004s

Danke fürs Lesen. Ich habe diese Seite zur Rechtschreibprüfung verwendet. Natürlich haben Sie das absolute Recht, mich zu fragen, wo die schnelle Analyse in der Überschrift versprochen hat ?! Im Moment kann ich keine einfache Antwort geben, welches Algoritmo ( Keine Panik! Dieses Wort ist ein normales Esperanto-Wort !) Schneller ist. Vielleicht sollten diese drei Codeskripte, wenn es möglich ist, optimiert und in einer Reihe von Situationen getestet werden. Der erste und dritte Algorithmus wurde von mir nach einem kurzen Blick auf den Pseudocode codiert (meistens Beschreibung lesen). Der zweite Algorithmus ist, wenn ich mich nicht irre, eine strenge Version des Algorithmus, der früher auf Habrahabr veröffentlicht wurde.