مشروع: دايكسترا وشجرة بحث

الفكرة: شبكة 400×400 بأوزان عشوائية (بذرة ثابتة 42): أقصر مسار من الزاوية إلى الزاوية بدايكسترا وكومة صغرى. ثم شجرة بحث ثنائية بـ 200 ألف إدراج، وارتفاعها، وتحريرها كلها.

البرنامج

خوارزميات.م

# خوارزميات وهياكل بيانات: أقصر مسار (Dijkstra بكومة ثنائية) على شبكة 400×400، وشجرة بحث ثنائية بمؤشرات
استورد عشوائي
استورد نظام

ثابت ع_ص = 400
ثابت لا_نهاية = 1000000000

هيكل عنصر_كومة:
    مسافة عدد
    عقدة عدد

# ---- كومة صغرى فوق قائمة ----
داله ادفع(ك قائمة[عنصر_كومة], ع عنصر_كومة) فراغ:
    اضف(ك, ع)
    ف = طول(ك) - 1
    طالما ف > 0:
        اب = (ف - 1) / 2
        اذا ك[اب].مسافة <= ك[ف].مسافة:
            توقف
        مؤقت = ك[اب]
        ك[اب] = ك[ف]
        ك[ف] = مؤقت
        ف = اب

داله اسحب(ك قائمة[عنصر_كومة]) عنصر_كومة:
    اعلى = ك[0]
    اخير = ك[طول(ك) - 1]
    احذف(ك, طول(ك) - 1)
    اذا طول(ك) == 0:
        ارجع اعلى
    ك[0] = اخير
    ف = 0
    ن = طول(ك)
    طالما صواب:
        ي = 2 * ف + 1
        اذا ي >= ن:
            توقف
        اذا ي + 1 < ن و ك[ي + 1].مسافة < ك[ي].مسافة:
            ي += 1
        اذا ك[ف].مسافة <= ك[ي].مسافة:
            توقف
        مؤقت = ك[ف]
        ك[ف] = ك[ي]
        ك[ي] = مؤقت
        ف = ي
    ارجع اعلى

داله اقصر_مسار(وزن قائمة[عدد]) عدد:
    ن = ع_ص * ع_ص
    بعد قائمة[عدد] = []
    خاتمه حرر(بعد)
    لكل ع في مدى(0, ن):
        اضف(بعد, لا_نهاية)
    كومة قائمة[عنصر_كومة] = []
    خاتمه حرر(كومة)
    بعد[0] = وزن[0]
    ادفع(كومة, عنصر_كومة(وزن[0], 0))
    طالما طول(كومة) > 0:
        ا = اسحب(كومة)
        اذا ا.مسافة > بعد[ا.عقدة]:
            تجاوز
        ص = ا.عقدة / ع_ص
        س = ا.عقدة % ع_ص
        جيران مصفوفة[عدد, 4] = [-1, -1, -1, -1]
        اذا ص > 0:
            جيران[0] = ا.عقدة - ع_ص
        اذا ص < ع_ص - 1:
            جيران[1] = ا.عقدة + ع_ص
        اذا س > 0:
            جيران[2] = ا.عقدة - 1
        اذا س < ع_ص - 1:
            جيران[3] = ا.عقدة + 1
        لكل ج في جيران:
            اذا ج < 0:
                تجاوز
            جديد_بعد = ا.مسافة + وزن[ج]
            اذا جديد_بعد < بعد[ج]:
                بعد[ج] = جديد_بعد
                ادفع(كومة, عنصر_كومة(جديد_بعد, ج))
    ارجع بعد[ن - 1]

# ---- شجرة بحث ثنائية ----
هيكل عقدة_شجرة:
    مفتاح عدد
    يسار مؤشر[عقدة_شجرة]
    يمين مؤشر[عقدة_شجرة]

داله ادرج_في(جذر مؤشر[عقدة_شجرة], مفتاح عدد) مؤشر[عقدة_شجرة]:
    اذا جذر == لاشيء:
        ارجع جديد(عقدة_شجرة(مفتاح, لاشيء, لاشيء))
    ع = محتوى(جذر)
    اذا مفتاح < ع.مفتاح:
        محتوى(جذر).يسار = ادرج_في(ع.يسار, مفتاح)
    غير ذلك اذا مفتاح > ع.مفتاح:
        محتوى(جذر).يمين = ادرج_في(ع.يمين, مفتاح)
    ارجع جذر

داله ارتفاع(جذر مؤشر[عقدة_شجرة]) عدد:
    اذا جذر == لاشيء:
        ارجع 0
    ي = ارتفاع(محتوى(جذر).يسار)
    م = ارتفاع(محتوى(جذر).يمين)
    اذا ي > م:
        ارجع ي + 1
    ارجع م + 1

داله احص(جذر مؤشر[عقدة_شجرة]) عدد:
    اذا جذر == لاشيء:
        ارجع 0
    ارجع 1 + احص(محتوى(جذر).يسار) + احص(محتوى(جذر).يمين)

داله احرق(جذر مؤشر[عقدة_شجرة]) فراغ:
    # تحرير عميق يدوي: لا تحرير يتبع المؤشرات
    اذا جذر == لاشيء:
        ارجع
    احرق(محتوى(جذر).يسار)
    احرق(محتوى(جذر).يمين)
    حرر(جذر)

عشوائي.بذرة(42)
وزن قائمة[عدد] = []
لكل ع في مدى(0, ع_ص * ع_ص):
    اضف(وزن, عشوائي.صحيح(1, 9))
ت0 = نظام.مؤقت()
اطبع("أقصر مسار: ", اقصر_مسار(وزن))
ت1 = نظام.مؤقت()
جذر مؤشر[عقدة_شجرة] = لاشيء
لكل ع في مدى(0, 200000):
    جذر = ادرج_في(جذر, عشوائي.صحيح(0, 1000000000))
اطبع("عقد الشجرة: ", احص(جذر), " ارتفاعها: ", ارتفاع(جذر))
احرق(جذر)
ت2 = نظام.مؤقت()
اطبع("زمن المسار ", ت1 - ت0 > 0.0, "، زمن الشجرة ", ت2 - ت1 > 0.0)

مخرجات مسجّلة من المجمّعmeem خوارزميات.م · meem 0.10.0+b01b55f

أقصر مسار: 2286عقد الشجرة: 199981 ارتفاعها: 45زمن المسار صواب، زمن الشجرة صواب

بُني أيضاً بـ meem build عند بناء الموقع: ملف ساكن حجمه 48.4 ك.ب، شُغّل وحده وطابق مخرجه المخرج أعلاه.

خطوة خطوة

1. الكومة الصغرى فوق قائمة: ادفع تضيف في الآخر ثم ترفع العنصر حتى يستقر، واسحب تأخذ الأصغر وتُنزل الأخير مكانه. العناصر هياكل عنصر_كومة بالقيمة.
2. دايكسترا: قائمة بعد بالمسافات، وكومة بالمرشحين، والجيران الأربعة في مصفوفة[عدد, 4] ثابتة (-1 للمفقود).
3. الشجرة: عقدة فيها مؤشر[عقدة_شجرة] يساراً ويميناً. جديد(...) يحجز عقدة، ومحتوى(م) يصل إليها، ولاشيء للفارغ.
4. التحرير العميق: حرر لا يتبع المؤشرات، فـ احرق تمشي في الشجرة وتحرّر كل عقدة بيدها.
5. الزمن: يُطبع «صواب» لا الثواني، ليبقى الناتج ثابتاً.

ما كان صعباً

• لا أنواع معمَّمة: الكومة تصلح لـ عنصر_كومة وحده؛ ولنوع آخر تُنسخ الشيفرة (أو تحمل القائمة فهارس إلى قائمة أخرى). الأنواع المعمّمة بعد 1.0.
• التحرير العميق يدوي: لا شيء يحرّر الشجرة إلا احرق.
• تقرير --debug-mem نسب نمو قائمة إلى سطر في المكتبة القياسية (عشوائي.م) لا إلى سطر البرنامج.

ما تعلّمناه

• الأداء بمستوى C: في التقرير 0.27–0.31 ث للملف المبني، مقابل 0.29 ث لنسخة C مبنية بـ gcc -O2، وذروة 8.6 م.ب.
• المؤشرات في ميم بسيطة بلا خطر: جديد ومحتوى وحرر، والفحص عن لاشيء قبل الوصول.