Pengujian benchmark dan analisis cepat dari algoritma permutasi

Saya memutuskan untuk menulis ulasan kecil ini dalam bahasa Inggris, berharap untuk memulai tren baru, yang saya harapkan akan meningkatkan komunikasi antar (Jangan pedulikan! Itu hanya ide globalistis dari kosmopolit muda).

Saya mendorong Anda untuk membalas posting ini dalam bahasa Inggris, bahkan Anda mengalami kesulitan dengan bahasa ini. Saya tidak sedang menulis puisi sekarang dan saya pikir kita dapat menghindari rasa malu tentang kemampuan bahasa Inggris kita. Namun saya akan berbicara tentang beberapa masalah puitis - tentu saja, tentang kombinatorik dan terutama tentang menghasilkan objek. Maksud saya permutasi. Mari kita mulai dengan kata-kata dengan semua dongeng yang biasanya dimulai: suatu ketika di Habrahabr telah (atau pernah, saya tidak tahu, mungkin) menerbitkan sebuah manuskrip menarik tentang menghasilkan superpermutasi. Topik itu menendang beberapa habrausers untuk menulis beberapa kode (lihat komentar) dan saya juga. Dan sebenarnya acara ini membawa saya kembali ke masalah kuno yaitu mempercepat dan menguji algoritma.

Saya tidak cukup ahli dalam bahasa matematika dan formula, jadi saya hanya mencetak tiga algoritma yang berbeda sekarang, diberi kode oleh saya di C89:

1. Algoritma Johnson-Trotter
2. Algoritma Naryana
3. Algoritma diambil dari habrpost ini , dikembangkan oleh Mrrl (A. Astrelin)

Semua algoritma, yang disebutkan di atas, tidak bersifat rekursif.

Algoritma Johnson-Trotter versi saya bukan yang terbaik, saya pikir. Namun demikian saya bergegas menunjukkan kepada Anda hasil yang dihasilkan untuk n = 10.

Waktu dengan output konsol (berarti printf)
1m19.410s asli
pengguna 0m31.899s
sys 0m36.253s

Waktu tanpa output konsol
0m2.241s nyata
pengguna 0m2.236s
sys 0m0.004s

Verstion saya tentang kode Mrrl

Dengan output konsol
1m11.565s nyata
pengguna 0m27.429s
sys 0m32.997s

Tanpa output konsol
0m0.489s nyata
pengguna 0m0.486s
sys 0m0.002s

Algoritma seperti Naryana terakhir memberikan hasil seperti itu

Dengan output konsol
1m10.223s nyata
pengguna 0m8.617s
sys 0m38.165s

Tanpa output konsol
0m0.453s nyata
pengguna 0m0.449s
sys 0m0.004s

Terima kasih sudah membaca. Saya menggunakan situs ini untuk memeriksa ejaan. Tentu saja, Anda memiliki hak mutlak untuk bertanya kepada saya, di mana analisis singkatnya dijanjikan dalam tajuk utama ?! Saat ini saya tidak dapat memberikan jawaban sederhana tentang algoritmo mana ( Jangan panik! Kata ini adalah kata Esperanto yang normal !) Lebih cepat. Mungkin ketiga skrip-kode ini harus disetel, jika memungkinkan, dan diuji dalam sejumlah situasi. Algoritme pertama dan ketiga telah dikodekan oleh saya setelah melihat sekilas pseudocode (kebanyakan membaca deskripsi). Algoritma kedua, jika Jika saya tidak salah, adalah versi ketat dari algoritma yang diterbitkan sebelumnya di Habrahabr.