قم بتنزيل AlgoLab من Google Drive ( AlgoLab (Excel 2007-2013) .xlsm و AlgoLab (Excel 97-2003) .xls files ).ما تحدث عنه البلاشفة منذ فترة طويلة ، وما كنت أسعى إليه منذ سنوات عديدة بوتيرة مختلفة حدث أخيرًا. قبل بضع سنوات ، كتب ماكرو صغيرًا لإنشاء رسوم متحركة gif لوغاريتمية لـ habrastaty. مع مرور الوقت ، نمت أداتي المتواضعة إلى حجم مثير للإعجاب ، وهو ليس من العار الآن أن يكشف للعالم.
لذا نلتقي.
AlgoLab هو تطبيق Excel (أي ملف Excel يحتوي على وحدات ماكرو) يمكنك من خلاله التعرف على خوارزميات الفرز خطوة بخطوة. وأيضا هناك فرصة لإعداد الرسوم المتحركة gif.
أمثلة على الرسوم المتحركة التي تم إنشاؤهافرز شجرة ثنائي
الفرز السباغيتي
نوع النوم
4 أوراق فقط - 2 رئيسي و 2 إعلامي. ها هم:
سيؤدي النقر على الصورة إلى فتح صورة بالحجم الكامل- فرز الورقة. في هذه الورقة ، يمكنك تشكيل مصفوفة بسرعة واختيار خوارزمية الفرز.
- معالجة الورقة. هنا نلاحظ خطوة بخطوة كيف تعمل هذه الخوارزمية أو تلك.
- فرز الورقة. هنا ملخص الخوارزميات.
- ورقة الرسم البياني. هناك أيضًا جدول إصدار مخطط لمقالات حول الفرز.
دعونا نتعرف على هذه الأوراق بمزيد من التفصيل.
فرز الورقة
تم تخصيص الجزء العلوي من الورقة لإنشاء مصفوفة غير مرتبة (بحيث يكون هناك شيء لتغذية الخوارزمية) ، بالإضافة إلى حفظ التصور في شكل صور على جهاز الكمبيوتر الخاص بك:
الصفيف نفسه موجود في السطر الأول. إذا لزم الأمر ، يمكنك تغيير قيم العناصر الفردية يدويًا فيه:
في الجزء العلوي الأيسر ، تحتاج إلى تحديد الخصائص الرئيسية للصفيف المولد:
الحجم ، سواء كانت القيم في الصفيف يجب أن تكون غير متكررة (0 - لا ، 1 - نعم) ، والتي تساوي الحد الأدنى والحد الأقصى للعناصر في الصفيف. تتضمن وحدات ماكرو VBA مقاومة التخريب لبيانات الإدخال ، لذا يمكنك إدخال بعض القيم غير الصحيحة. في هذه الحالة ، سيحدد التطبيق ما يجب أن تكون عليه هذه الخاصية أو تلك.
وأيضًا خيار لتحديد ما إذا كان من الضروري تنفيذ الخوارزمية خطوة بخطوة (= 1) أو ما إذا كان من الممكن تطبيق الفرز على الهيكل وإظهار النتيجة النهائية فقط (= 0). بالطبع ، تم إنشاء تطبيق excel نفسه لمراقبة العملية برمتها في وضع خطوة بخطوة ، لذا فإن القيمة هنا تساوي عادة واحدة. ولكن في بعض الأحيان عند الاختبار ، ألغي هذا الخيار للتحقق فقط مما إذا كانت الخوارزمية الجديدة التي أضيفها إلى AlgoLab.xlsm تعمل على الإطلاق (أي أنني بحاجة أولاً لمعرفة ما إذا كانت المصفوفة المصنفة هي النتيجة النهائية ، دون إضاعة الوقت في عرض التصور )
قليلاً إلى اليمين هي المنطقة التي يمكنك فيها تحديد كيفية فرز العناصر في المصفوفة التي لم يتم فرزها بالضبط.
توليد مجموعة مختلطة عشوائيا؟ أو ربما رتب العناصر بترتيب تنازلي؟ أو جعل المصفوفة مرتبة تقريبًا (وحدد أيضًا معامل الفرز تقريبًا)؟
لتحديد أي من هذه الطرق ، ما عليك سوى النقر على الخلية التي تحتوي على العنصر. نتيجة لذلك ، يتم إعادة إنشاء الصفيف في السطر الأول. ستتحول الخلية المحددة إلى اللون الأزرق.
إلى اليسار هو المنطقة التي ستكون مطلوبة إذا كنت لا تحتاج فقط إلى الإعجاب بالتصوير ، ولكن أيضًا لحفظ العملية بأكملها إطارًا تلو الآخر كصور.
أولاً ، تحتاج إلى تحديد ما إذا كنت تريد تصدير خطوات الفرز بشكل عام إلى الصور (= 0 ، إن لم يكن ، = 1 إذا كانت الإجابة بنعم ، وهذا الخيار هو "مرة واحدة" ، أي أنه تتم إعادة تعيينه إلى صفر بعد اكتمال الفرز). ثانيًا ، تحتاج إلى تحديد تنسيق الصورة (تتوفر 4 خيارات فقط: GIF و JPG و PNG و BMP. الخيار الأخير يعطي أعلى نتيجة جودة ، لذلك أوصي به). ثالثًا ، تحتاج إلى تحديد المسار إلى المجلد الذي تريد حفظ الصور فيه (انقر فوق هذه الخلية وسيتم فتح مربع حوار لتحديد دليل). ثم تأتي الخلية التي يملأها الماكرو نفسه - معرف الجلسة (مطلوب للاسم الفريد للمجلد الفرعي لحفظ إطارات تطبيق الفرز المحدد). وأيضًا من الضروري تحديد منطقة الالتقاط بشكل صحيح (إحداثيات الخلايا العلوية اليمنى والسفلى اليمنى ، ستكون الإطارات هي التي ستقتصر عليها - ألا تنسخ الورقة بأكملها؟)
حسنًا ، ستجد في الجزء الأيمن تمامًا خلية "الفرز" (والتي تعمل كزر لبدء العملية ، عند اختيار الفرز وإنشاء مصفوفة ، ما عليك سوى النقر عليها).
حتى بجوار هذا الزر ، تعيش العديد من الشخصيات الخاصة التي يمكن استخدامها في التصور. لا يلزم لمس هذه الخلايا.
في الجزء السفلي ، أهم شيء هو اختيار الخوارزمية. تحتاج فقط إلى النقر فوق اسم الفرز ، وبعد ذلك ستتحول الخلية التي بها إلى اللون الأزرق.
من بين أكثر من 80 خوارزمية ، ما يقرب من نصفها متاح اليوم. حتى الآن ، فإن الأشكال غير المحققة لها مظهر شاحب مقارنةً بتلك التي تم تنفيذها بالفعل. ما زلت لم أتمكن من القيام ببعض (ولم أبدأ التنفيذ). بعضها قيد التطوير. بعضها مكتوب ومختبر وسيكون متاحًا قريبًا جدًا (على وجه الخصوص ، جميع الفرز تقريبًا عن طريق الإدخالات جاهزة لي ، ومع ذلك ، سأضيفها إلى التطبيق بمجرد إصدار habrastats لهذه الفرز في الأسابيع القادمة ومشاركة AlgoLab.xlsm المحدثة - وماذا أفعل ، لا أريد أن أفسد حلقات جديدة من سلسلتي).
أخطط لتعديل بعض الفرز المنفذة بالفعل. التصور لا يرضيني في كل مكان.
ولكن في هذا المجال ، عند اختيار خوارزمية ، يتم تحميل معلومات تلخيصية عنها. يتم أخذ المعلومات من ورقة "الفرز" ، ويتم سحبها تلقائيًا باستخدام ماكرو. بالمناسبة ، إذا قمت بتغيير النص في هذه المنطقة ، فسيتم تغييره أيضًا في الورقة الأصلية.
فرز ، كما ترون الكثير. من أجل عدم الخلط في كل هذا الروعة ، يتم تقسيمها إلى فئات ، اعتمادًا على الطريقة الأساسية لتنظيم البيانات المستخدمة. ما هي هذه الفصول؟
- فرز عشوائي. يتم خلط عناصر المصفوفة بشكل عشوائي ويستمر هذا حتى يتم ترتيب البنية فجأة.
- أنواع التبادل. يتم تنظيم مقارنة (وتبادل) إجمالية بين عناصر المصفوفة.
- إدراجات فرز. يتم تحديد العناصر ويتم إدراج كل منها في مكانها.
- فرز حسب الاختيار. في المصفوفة الفرعية ، يتم تحديد الحد الأقصى للعنصر ، والذي يتم إدراجه في نهاية المصفوفة الفرعية. ثم ، إلى الجزء غير المصنف المتبقي ، يتم تكرار نفس الإجراء.
- دمج الأنواع. تم البحث عن المصفوفات الفرعية التي يتم توصيلها ببعضها البعض.
- فرز حسب التوزيع. تنقسم العناصر إلى فئات حتى يؤدي ذلك إلى النتيجة المرجوة.
- الفرز الهجين. يتم الجمع بين طرق التبادل والإدراج والاختيار والدمج والتوزيع.
- الفرز الموازي. خوارزميات حيث يتم توفير معالجة موازية لأجزاء مختلفة من الصفيف.
- شبكات الفرز. يتم تمرير المصفوفة من خلال شبكة الفرز ؛ عند الإخراج ، يتم ترتيبها.
- تصنيفات أخرى. خوارزميات زائفة ، وفرز هزلي وباهظ ببساطة.
في المباريات القادمة ، سيتم إبراز الفروق الدقيقة التفصيلية لكل فئة. حسنًا ، ننتقل إلى الورقة التالية.
ورقة العملية
في الواقع ، عند إنشاء مصفوفة ، واختيار خوارزمية والنقر على زر "فرز" ، يطرح الماكرو إلى هذه الورقة. وهنا يحدث سر تنظيم البيانات.
خلال العملية بأكملها أعلاه ، سترافقك هذه النافذة الرائعة:
نظرًا لأن وضع العرض خطوة بخطوة ، من أجل المتابعة إلى الخطوة التالية ، من الضروري
الضغط على زر "خطوة جديدة" بداخله . ليس من السهل جدًا القيام بذلك باستخدام الماوس ، لذلك يكون تركيز إدخال النافذة دائمًا على هذا الزر. أي ، للمتابعة إلى الخطوات التالية ، ما عليك سوى أن تكون كسولًا للضغط على Enter لوحة المفاتيح (لن تكون هناك إيماءات أخرى مطلوبة).
يعرض
الزر "إنهاء" العملية من طريقة عرض خطوة بخطوة. ستكمل الخوارزمية عملها بصمت وتعرض النتيجة النهائية فقط. لن ترى المرحلة النهائية من عملية الفرز.
زر "إحباط" يوقف عمل وحدات الماكرو تمامًا في هذه الخطوة.
يتيح لك
زر "لقطة" حفظ لقطة شاشة لهذه الخطوة المحددة. ستجد بعد ذلك الصورة في المجلد المحدد في الإعدادات في ورقة الفرز.
فرز الورقة
يتم تخزين طاولة ضخمة مع جميع أنواع المعرفة حول الأنواع هنا. كما تتذكر ، يتم سحب المعلومات من هنا عند اختيار الفرز في ورقة الفرز. أتوب ، في حين أن جودة الملء هي نفسها ، لم يكن هناك ما يكفي من المثابرة لتقديم أقصى قدر ممكن من البيانات الصحيحة. نأمل اللحاق بالركب في المستقبل القريب جدا.
ورقة الرسم البياني
في هذه الورقة يمكنك التعرف على خيالي حول تواريخ أقرب إصدارات هابراتاتيك عن الأنواع.
سأتحدث عن الخوارزميات في هذا الترتيب.
التبادل - الإضافات - التحديد - الدمج - التوزيع -
← هجين ← موازية ← شبكة ← عشوائية
يتم سرد الطبقات العامة ، ولكن بشكل عام ، سيتم تخصيص العديد من الأوبئة التي تطيع مثل هذا المخطط العام لكل فئة.
- وصف فئة التصنيف. الفروق الدقيقة التمهيدية الأساسية الكامنة في جميع أنواع الطبقات ، وأنواع الطبقة الأساسية. عادة ، ستحتوي هذه المقالات التمهيدية على معلومات معروفة إلى حد ما. لكن مع ذلك ، سأحاول ألا أشعر بالملل.
- بعض أنواع الفصل غير المعروفة. هنا سوف أسعدك بمواد جديدة ، لا توجد معلومات عنها باللغة الروسية. ولن تجد شيئا حتى في اللغة الإنجليزية. لن تكون المقالات المنفصلة حول فرز التبادلات فقط ، لأنه لم يكن هناك وقت طويل لقصص مثيرة للاهتمام.
- مقارنة عملية لأنواع الصف فيما بينها. لكل مجموعة من الخوارزميات سيكون هناك مقال نهائي مخصص لاختبار الفرز على مجموعات بيانات مختلفة. هنا أعدك بالكثير من الاكتشافات المذهلة!
مقارنة الفرز العملي
كان من المخطط أن يقارن فقط تنفيذ الثعبان الخوارزميات. ومع ذلك ، بعد أن رأيت النتائج الأولى على مثال فرز جنوم ، توصلت إلى استنتاج مفاده أنهم سيعطون فكرة خاطئة عن السرعة النسبية.
لدى Python نظامها الخاص للوصول إلى ذاكرة المتغيرات (خاصة إذا تم تعيين هذه المتغيرات لبعضها البعض) ، وهذا هو السبب في أن الخوارزميات المحسنة يمكن أن تعمل بشكل أبطأ.
وضع مماثل مع شاكر / فقاعة. على عكس التوقعات ، يعمل فرز الفقاعات بشكل أسرع من فرز الشاكر (على الرغم من أن شاكر فرز هو نوع فقاعة محسنة).
من أجل التحكم ، اختبرت الفرز في PHP أيضًا (أعمل بشكل رئيسي بهذه اللغة ، لذلك كان الاختبار البديل أسرع وأسهل في إنشائه). هناك بالفعل الوضع "طبيعي" - يعمل "gnome" الأمثل في جميع مجموعات البيانات بشكل أسرع من المعتاد.
ومع ذلك ، تتمتع PHP أيضًا بسمعة كونها "ناقصة" وأداة بطيئة ، لذلك قررت أنها ليست مناسبة أيضًا للاستنتاجات العالمية. لتقليل اللوم المحتمل [في اختيار اللغة الخطأ لاختبار السرعة الحقيقية] ، قررت تقليل الاختبارات الرئيسية أيضًا في Java. ومع ذلك ، واجهت نقصًا في معرفتي لهذه اللغة. للأسف ، لم تنمو معًا.
وبالتالي ، سيتم الاختبار
بثلاث لغات على الفور:
- بيثون بادئ ذي بدء ، هذه اللغة هي الأنسب لوصف الخوارزمية. نظرًا لوجود وظائف صحيحة تعمل ، فسنقيس الوقت المناسب لها. لكن النتائج ستكون مشكوك فيها إلى حد ما.
- PHP في البداية ، لن أستخدم هذه اللغة بأي شكل من الأشكال في سلسلة من المقالات. ولكن بما أنني كتبت بيئة عليها لاختبار الفرز والتطبيقات نفسها على PL هذه ، فلماذا لا. النتائج العملية التي يمكن من خلالها الحكم على الفعالية النسبية للخوارزميات هي أكثر ملاءمة مقارنة بـ Python.
جافا بناءً على النتائج في Java ، سنستخلص النتائج الرئيسية.
بالطبع ، سيتم مشاركة جميع الخيارات بجميع اللغات.
التعليمات
أتوقع بالفعل بعض الأسئلة من الجمهور ، وسوف أجيب على الفور.
لماذا يتم تنفيذ برنامج تصور الخوارزميات في Excel؟
لذلك في وقت ما كان الأمر أسرع وأسهل (بالنسبة لي). اتضح أن المساحة الشبكية لجداول البيانات هي حل جاهز ومريح للغاية لتصور العمل مع المصفوفات.
حسنًا ، دعنا نلقي نظرة على كل هذه الأنواع. ما هي الخطوة التالية؟
استنادًا إلى AlgoLab سأقوم بعمل تصورات للأشجار والرسوم البيانية. مفرش طاولة أولام ، نملة لانغتون ، هذا كل شيء. لا تزال هناك فراغات لعام 2048 (يلعب AI باستخدام أسلوب minimax و Monte Carlo - تحتاج إلى الانتهاء منه). الأشغال هي الكثير من الأراضي.
المراجع
قم بتنزيل AlgoLab من Google Drive ( AlgoLab (Excel 2007-2013) .xlsm و AlgoLab (Excel 97-2003) .xls files ).سلسلة مقالات