Tests de référence et analyse rapide des algorithmes de permutations

J'ai décidé d'écrire cette petite critique en anglais, dans l'espoir de lancer une nouvelle tendance qui, je l'espère, améliorera l'intercommunication (ça ne fait rien! C'est juste l'idée globaliste d'un jeune kosmopolit).

Je vous invite à répondre à ce message en anglais, même si vous avez des difficultés avec cette langue. Je n'écris pas un poème en ce moment et je pense que nous pouvons éviter l'embarras de nos compétences en anglais. Mais je vais parler de quelques questions poétiques - bien sûr, sur la combinatoire et surtout sur la génération d'objets. Je veux dire des permutations. Commençons par les mots avec ceux que tous les contes de fées sont généralement commencés: il était une fois sur Habrahabr avait été (ou a été, je ne sais pas, était peut-être) publié un manuscrit intéressant sur la génération de superpermutations. Ce sujet a incité certains utilisateurs à écrire du code (voir les commentaires) et moi aussi. Et en fait, cet événement m'a conduit à nouveau à un ancien problème d'accélération et de test des algorithmes.

Je ne suis pas assez habile en langage mathématique et en formules, donc j'imprime maintenant trois algorithmes différents, codés par moi en C89:

1. Algorithme de Johnson-Trotter
2. Algorithme de Naryana
3. Algorithme tiré de ce habrpost , développé par Mrrl (A. Astrelin)

Tous les algorithmes mentionnés ci-dessus ne sont pas récursifs.

Ma version de l'algorithme Johnson-Trotter n'est pas la meilleure, je pense. Néanmoins, je me dépêche de vous montrer les résultats qu'elle produit pour n = 10.

Temps avec sortie console (signifie printf)
réel 1m19.410s
utilisateur 0m31.899s
sys 0m36.253s

Temps sans sortie console
réel 0m2.241s
utilisateur 0m2.236s
sys 0m0.004s

Ma version du code Mrrl

Avec sortie console
réel 1m11.565s
utilisateur 0m27.429s
sys 0m32.997s

Sans sortie console
réel 0m0.489s
utilisateur 0m0.486s
sys 0m0.002s

Le dernier algorithme de type Naryana donne un tel résultat

Avec sortie console
réel 1m10.223s
utilisateur 0m8.617s
sys 0m38.165s

Sans sortie console
réel 0m0.453s
utilisateur 0m0.449s
sys 0m0.004s

Merci d'avoir lu. J'ai utilisé ce site pour la vérification orthographique. Bien sûr, vous avez le droit absolu de me demander, où la rapide analyse promise dans le titre?! En ce moment, je ne peux pas donner une réponse simple à propos de quel algoritmo ( pas de panique! Ce mot est un mot espéranto normal !) Est plus rapide. Peut-être que ces trois scripts de code devraient être ajustés, si cela est possible, et testés dans un certain nombre de situations. Le premier et le troisième algorithmes ont été codés par moi après un bref aperçu du pseudocode (lecture de la description principalement). Le deuxième algorithme, si je ne me trompe pas, est une version stricte de l'algorithme publiée précédemment sur Habrahabr.