اختبار المعيار والتحليل السريع لخوارزميات التباديل

قررت أن أكتب هذا الاستعراض الصغير باللغة الإنجليزية ، آملًا أن أبدأ اتجاهًا جديدًا ، وأتوقع أن يحسن الاتصال الداخلي (لا تمانع! إنها مجرد فكرة عالمية عن kosmopolit الشاب).

أحثك على الرد على هذا المنشور باللغة الإنجليزية ، حتى لو كنت تواجه بعض الصعوبات في هذه اللغة. أنا لا أكتب قصيدة الآن وأعتقد أننا يمكن أن نتجنب الإحراج من مهاراتنا في اللغة الإنجليزية. ومع ذلك سأتحدث عن بعض القضايا الشعرية - بالطبع ، عن التوافقية وخاصة حول توليد الأشياء. أعني التباديل. دعنا نبدأ بالكلمات مع تلك القصص الخيالية التي عادة ما تبدأ: ذات مرة على Habrahabr قد تم (أو تم ، لا أعرف ، ربما كان) نشر مخطوطة مثيرة حول توليد supermutations. أثار هذا الموضوع بعض الرفاقين لكتابة بعض الرموز (انظر التعليقات) وأنا أيضًا. وفي الواقع ، قادني هذا الحدث مرة أخرى إلى مشكلة قديمة تتمثل في تسريع واختبار الخوارزميات.

أنا لست ماهرًا بدرجة كافية في اللغة الرياضية والصيغ ، لذلك أنا فقط أطبع ثلاثة خوارزميات مختلفة الآن ، مشفرة من قبلي في C89:

1. خوارزمية جونسون تروتر
2. خوارزمية ناريانا
3. خوارزمية مأخوذة من هذا habrpost ، التي وضعتها Mrrl (A. Astrelin)

جميع الخوارزميات ، المذكورة أعلاه ، ليست متكررة.

أعتقد أن إصدار خوارزمية جونسون تروتر ليست الأفضل. ومع ذلك فأنا أستعجل لتظهر لك resut التي تنتجها لـ n = 10.

الوقت مع إخراج وحدة التحكم (يعني printf)
1m19.410s الحقيقي
مستخدم 0m31.899s
تميز الكلية 0m36.253s

الوقت دون الإخراج وحدة التحكم
0m2.241s الحقيقي
مستخدم 0m2.236s
تميز الكلية 0m0.004s

بلدي verstion من رمز Mrrl

مع الإخراج وحدة التحكم
1m11.565s الحقيقي
مستخدم 0m27.429s
تميز الكلية 0m32.997s

بدون إخراج وحدة التحكم
0m0.489s الحقيقي
المستخدم 0m0.486s
تميز الكلية 0m0.002s

آخر Naryana مثل الخوارزمية يعطي مثل هذه النتيجة

مع الإخراج وحدة التحكم
1m10.223s الحقيقي
مستخدم 0m8.617s
تميز الكلية 0m38.165s

بدون إخراج وحدة التحكم
0m0.453s الحقيقي
المستخدم 0m0.449s
تميز الكلية 0m0.004s

شكرا للقراءة. لقد استخدمت هذا الموقع لفحص الهجاء. بالطبع ، لديك الحق المطلق في أن تسألني ، أين التحليل السريع الموعود في العنوان ؟! في هذه اللحظة ، لا يمكنني تقديم إجابة بسيطة حول الخوارزمية ( لا داعي للذعر! هذه الكلمة هي كلمة إسبرانتو طبيعية !) أسرع. ربما يجب ضبط هذه النصوص البرمجية الثلاثة ، إذا كان ذلك ممكنًا ، واختبارها في عدد من المواقف. تم ترميز الخوارزميات الأولى والثالثة من قبلي بعد إلقاء نظرة سريعة على الرمز الكاذب (وصف القراءة في الغالب). الخوارزمية الثانية ، إذا لم أكن مخطئًا ، فهي عبارة عن نسخة صارمة من الخوارزمية التي تم نشرها مسبقًا على Habrahabr.