كتاب استيعاب الخوارزميات، الفصل الخامس، الدرس الأول، جدول التلبِيد

السلام عليكم ورحمة الله وبركاته
هذا الدرس الأول من الفصل الخامس من كتاب (استيعاب الخوارزميات)، المعنون (جدول التبليد)، وهذا الدرس عن نوع هام من بنى المعطيات data structure.

لا تخف، سأخبرك بمعناه، واعلم أن كل ترجمة آخذها هي من عرب آيز أو قاموس الجمعية السورية، والمصدر الأخير أفضله عن الأول فهو الأصل.

لتفهم درس اليوم سنمضي مع صاحبنا عبود وعمله الجديد مع المساعدة ليلى!

عبود صاحب المتجر

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

لا تنس ما درسناه في الفصل الأول، خوارزمية البحث الخطي، فإن بحث في الدفتر فإنه تعقيد الوقت سيكون (س)O. أما إن كان الدفتر مرتبًا ترتيبًا هجائيًا واستعملت خوارزمية البحث الثنائي فإن تعقيد الوقت سيكون (لو س)O.

راجع الفصول!
لأذكرك بفارق السرعة بين (س)O و(لو س)O = هب أنك المحاسب وأنك تقرأ في الثانية عشرة سطور باحثًا عن الغرض الذي طلبه الزبون، فانظر في الصورة الآتية كم ستستغرق كل واحدة:

ترى فارق السرعة، خوارزمية البحث الثنائي أسرع، فشتان بين الثرى والثُّريا!

عبود صاحبنا قد كان معنا في الفصول الأولى من الكتاب أيها القارئ الكريم، وقد درس بجد واجتهاد، وهو يعلم خوارزمية البحث الثنائي، لكنه مرهقة له، هو البشري، ويود لو عنده مساعد يساعده ليحفظ الأسعار عنه.

وفي ذات نهار أتى عبود يحدثني يبثُّ إلي همه ويطلب لو أعرف شخصًا، فحتى باستعمال خوارزمية البحث الثنائي فإن الزبون يشتد غضبه منتظرًا إيايه حتى يجيبه.

وبينما نحن على حالنا إذ مرت حسناء هيفاء يجري ماء النضارة والشباب في محياها، تسير في رشاقةٍ وزهوٍ كأنها غصن بانٍ، ووجنتيها كأنهما انتهبتا من الورد حمرته، وكأن للبدر نورًا من بعض نورها.

فطفق عبود من مكانه يتبعها ولم يهدأ يومه أبدًا، يهيم في كل وادٍ حتى أفلح وصارت مساعدته في متجره براتبٍ عالٍ، وكان اسمها الحسناء ليلى!

كان عبود يقول: تفاحة يا ليلى
فتجيب ليلى: عشرة ريال عبودي
وتمط كلامها عند اسم (عبودي) هكذا عبوددييي!

المساعدة ليلى تقول السعر في (١)O، لأي سلعة مهما كان الدفتر ضخمًا، فهي أسرع من خوارزمية البحث الثنائي، ولهذا أغرم بها فتانا!

ما أسرع ليلى يا صاحبي، ما رأيك لو كان عندنا وظيفة اسمها ليلى تخبرنا بسعر السلعة بسرعة فائقة كليلى مساعدة عبود؟
ارتد قبعة بُنى المعطيات ولنبرمج وظيفتنا المسماة ليلى!

الوظيفة ليلى

تعلمنا في الفصول المتقدم شرحها بنيتا معطيات، كانتا الصفيفة array واللائحة المترابطة linked list (وما ذكرت الكَدسَة stack لأنك لا تستطيع البحث فيها).

قد نضع دفتر الأسعار في صَفِيفَة مثل هذه:

كل عنصر هو عنصرين، الأول اسم السلعة والثاني سعرها، وإن فرزت هذه الصفيفة ستتمكن من تطبيق خوارزمية البحث الثنائي عليها، وستستطيع العثور على سعر السلعة في (لو س)O.

لكننا لا نريد هذا، نريد العثور على سعر السلعة في (١)O، نريد ليلانا يا مبعسس، ليلى حصرًا!

حسنًا حسنًا، لأجل هذا الغرض أتت وظيفة التلبِيد hash function.

وظيفة التلبِيد hash function

وظيفة التلبِيد: تأخذ مدخلًا وتُرجِعُ قيمةً ثابتة الحجم.
تلبيد يا معبسس؟ ما معناه!

ذُكِرَ في (جمهرة اللغة): ”واللِّبَد: كل ما لصق وتراكبَ بعضُه على بعض، ومنه قوله عز وجل ﴿كَادُوا يَكُونُونَ عَلَيْهِ لِبَدًا﴾، سورة الجن، أي متراكِب بعضُهم على بعض من الازدحام“. وذُكِرَ في (لسان العرب): ”ولَبَدَ الشيءُ بالشيءِ يَلْبُد إذا ركب بعضُه بعضًا“، وذُكِرَ أيضًا: ”وتَلَبَّد الشعَر والصوف والوَبَر والتَبَدَ: تداخلَ ولَزِقَ“.

وكما ترى، فهو يعني تراكب وتلاصق وتداخل الشيء بالشيء كأنه يلتحم ويصير شيئًا واحدًا.
وهذا عمل وظيفة التلبِيد، إذ تأخذ مدخلًا، مثل اسم السلعة ولتكُن التفاحة، وتُرجِعُ قيمةً ثابتة الحجم، وهي سعر السلعة، فكأنها أخذت مدخلًا ولبدته فصيرته شيئًا واحدًا ملتحمًا.

انظر هذه الصورة، ندخل لها نصًا string وتُرجِع لنا عددًا:

هل ترى نمطًا يتكرر في المخرجات إن أدخلت نصًا ما؟
لوظيفة التلبِيد شرائط عليها اتباعها، وهي:
١. على الخرج أن يكون قيمة ثابتة، فلا تدخل مثلًا تفاحة وتُرِجع في المرة الأولى الرقم ٣ ثم في المرة الثانية الرقم ٦.
٢. عليها إرجاع قيمة مختلفة لكل مدخل مختلف، لا أن ترجع الرقم ١ لكل كلمة تمررها للوظيفة.

ما نفع هذا يا معبسس؟
ويحك أنسيت الوظيفة ليلى؟
بوظيفة التلبِيد سنبرمج الوظيفة ليلى، فآهٍ من ليلى وحبها!

عودة إلى الوظيفة ليلى

لنشرع بصفيفة فارغة:

ستخزن فيها أسعار السلع في متجر عبود، لنخلص عبود من ليلى البشرية التي سلبت عقل فتانا وماله!
سنضيف سعر التفاحة بتمرير اسم تفاحة إلى وظيفة التلبِيد:

وكما ترى أرجعت لنا الرقم ٣
ويحك يا معبسس، أتقول سعر التفاحة بثلاثة ريال؟!!
لا تقاطعني واكمل القراءة!
ما هذه القيمة المُرجعة إلا الدليل index الذي سنخزن فيه سعر التفاحة وليس هو سعرها!

لنضيف الحليب إلى الصفيفة:

أعادت لنا الوظيفة الرقم صِفر، إذن سنخزن الحليب في الدليل صِفر في الصفيفة. واصل إدخال الأسعار حتى تمتلئ الصفيفة.

ستسأل ليلى قائلًا: يا ليلى، ما سعر الرمان؟
سترجع لك أربعة، وهو الدليل المخزن فيه سعر الرمان:

الوظيفة تخبرك أين يُخزَّن سعر السلعة، فلن تبحث في كل الدفتر لتعثر على سعر السلعة، وهذا لأجل أن:
١. الوظيفة تُرجِع قيمة ثابتة، وهو الدليل المخزن فيه السعر، فتعثر على مكان تخزين سعر السلعة فتذهب إليه فتعثر عليه.
٢. تُرجِع الوظيفة دومًا قيمة مختلفة لكل مدخل مختلف، فلما تدخل الرمان سترجع لك أربعة (الدليل حيث سعر الرمان)، وإن أدخلت الحليب ستُرجِع لك صِفرًا، فكل مدخل له مكان خاص في الصفيفة.
٣. الوظيفة تعلم حجم الصفيفة لهذا تُرجِع لك دليلًا صالحًا valid index، فإن كانت الصفيفة تحوي خمسة عناصر فإن الوظيفة لن تُرجِع الدليل مئة ١٠٠، لأنه دليل فاسد.

تهانينا، أتممنا الوظيفة ليلى!

جدول التلبِيد

وها قد أنشأنا في الفقرة السابقة وظيفة ليلى بإدماج وظيفة التلبِيد مع الصفيفة، وبفعلنا هذا قد حصلنا على بنية معطيات data structures اسمها جدول التلبِيد Hash Table!
جدول التلبيد: بنى معطيات تخزن المعطيات بإسناد قيمة value إلى مفتاح key. وله أسماء أخرى مثل الصفيفة المترابطة Associated Arrays والقاموس Dictionary وغيرهما (hash maps, maps).

لما شرحنا الصفيفة واللائحة المترابطة في الفصل الثاني قلنا إن جلب عنصر من الصفيفة سريع بل لحظي، وجدول التلبِيد يستعمل صفيفة لهذا هو سريع جدًا.

أغلب لغات البرمجة تضمن جدول التلبِيد فيها، فلا حاجة لك ببرمجته، مثلًا لغة بايثون تستعمله باسم القاموس dictionary.

سننشئ جدول تلبيد باستعمال الوظيفة dict في بايثون:

>>> book = dict()

أصبح الآن المتغير (دفتر book) جدول تلبيِد
لنضيف إليه الأسعار:

>>> book["apple"] = 10

لنعرض محتواه:

>>> print(book)

اطبع سعر التفاحة وانظر السرعة:

>>> print(book["apple"])

كما ترى، فجدول التلبِيد المسمى دفترًا book فيه أسماء السلع وهي المفتاح key، أما أسعارها فهي القيم values.

إن كنت تتساءل ما حل بعبود ومتجره فقد فلس بسبب ليلى، رفع لها الراتب وخرج معها كل يوم حتى باع المتجر ولما خطبها رفضته وتزوجت قيسًا، منافس متجر عبود في الجهة المقابلة من الشارع.

تمرين

على وظيفة التلبِيد أن تُرجِع نفس القيمة لنفس المدخل، فإن لم تفعل فلن تستطيع أن تعثر على مدخلك في جدول التلبِيد!
فأي من هذه الوظائف سترجع قيمة ثابتة؟
الأولى:
f(x) = 1

ترجع ١ كل مرة
الثانية:
(x)f(x) = rand

ترجع قيمة عشوائية كل مرة
الثالثة:
()f(x) = next_empty_slot

ستُرجِع دليل الخانة الفارغة التالي في جدول التلبِيد
الرابعة:
f(x) = len(x)

ستستعمل طول المدخل على أنه الدليل index

اختر واحدة وشاركني حله في خانة التعليقات لأرى صحة حلك!

وتمرين أخير:
برمج بنفسك جدول التلبيد!

سنرى في المقال الآتي إن شاء اللّٰه كيفية برمجته باستعمال لغة بايثون ولغة C

الخاتمة

ها قد وصلنا إلى نهاية المقال، وهو مقدمة لمقال آتٍ به أختم الفصل الخامس، وها أنا أخط بقلمي الخطوط الأخيرة لهذا المقال الشائق، وأرجو إني قد وفِّقت في الشرح.

وفي نهاية الأمر لا يسعني سوى أن أشكرك على حسن قراءتك لهذا المقال، وأني لبشر أصيب وأخطِئ، فإن وفِّقت في طرح الموضوع فمن اللّٰه عز وجل وإن أخفقت فمن نفسي والشيطان.

أرجو منك تقييم كفاءة المعلومات من أجل تزويدي بالملاحظات والنقد البناء في خانة التعليقات أو عبر حساب الموقع، والسلام عليكم ورحمة اللّٰه تعالى وبركاته.