يا جماعة الخير، السلام عليكم ورحمة الله.
خليني أحكيلكم قصة صارت معي قبل كم سنة، قصة “ولّعت معي” وخلتني ما أنام ليلتين. كنا شغالين على تطبيق توصيل، زي تطبيقات طلب التكاسي والأكل المنتشرة اليوم. الأمور كانت ماشية تمام، والتطبيق في مراحله الأخيرة قبل الإطلاق الكبير. في يوم من الأيام، واحنا بنعمل الاختبارات النهائية، لاحظنا شغلة غريبة ومقلقة جدًا: كل ما يجي مستخدم يطلب سيارة، التطبيق “بجمّد” أو “بعلّق” لشوية ثواني طويلة، وأحيانًا كان ينهار تمامًا. الشاشة تعرض “جاري البحث عن أقرب سائق…” والمستخدم المسكين يستنى ويستنى… وما في إشي بصير.
كانت فضيحة! تخيلوا نطلق التطبيق بهيك مشكلة. المدير التقني (CTO) صار يلف حوالين حاله، والضغط علينا زاد. أول شي فكرنا فيه: “أكيد السيرفر ضعيف، لازم نزيد الموارد”. بس أنا، أبو عمر، بطبعي شكّاك وما بحب أرمي مصاري على الهاردوير قبل ما أتأكد من السوفتوير. قلتلهم: “يا جماعة، اهدوا شوي، خلوني آخذ نظرة على الكود”.
وبالفعل، غصت في الكود المسؤول عن إيجاد أقرب سائق… وهنا كانت الصدمة. الكود كان بسيط لدرجة السذاجة. كان عبارة عن حلقة `for` بتلف على كل السائقين المتاحين في النظام (وقتها كانوا حوالي 5000 سائق في قاعدة بيانات الاختبار)، وفي كل لفة، تحسب المسافة بين السائق وموقع المستخدم، وتحتفظ بأقرب واحد. منطقي، صح؟ بس يا زلمة، شو هالكارثة! هاي الطريقة اسمها “البحث الشامل” أو Brute Force، وهي وصفة أكيدة للدمار مع ازدياد عدد المستخدمين والسائقين. وقتها تذكرت أيام الجامعة ومادة الخوارزميات، ولمع في بالي اسم غريب: “شجرة كيه-دي” (k-d tree). قلت لحالي، والله يا أبو عمر شكلك رح ترجع لأيام الدراسة… وهذا اللي صار.
ما هو الجحيم الذي كنا فيه؟ (البحث الشامل – Brute Force)
قبل ما نحكي عن الحل، خلينا نفهم المشكلة بشكل أعمق. الطريقة اللي كانت مكتوبة، واللي للأسف كثير من المبرمجين بيكتبوها في البداية، هي البحث الشامل. الفكرة بسيطة:
- عندك موقع المستخدم (نقطة أ).
- عندك قائمة بمواقع كل السائقين المتاحين (نقطة ب1, ب2, ب3, … ب5000).
- بتمر على كل سائق في القائمة، واحد واحد.
- بتحسب المسافة بين (أ) و (ب).
- بتقارن هاي المسافة مع أصغر مسافة لقيتها لحد الآن، وإذا كانت أصغر، بتحدّثها.
- بعد ما تخلص اللفة على كل السائقين، بتكون لقيت أقرب واحد.
بالكود، ممكن تكون إشي زي هيك (مثال بسيط بلغة Python):
import math
def find_nearest_driver_brute_force(user_location, drivers_locations):
best_driver = None
min_distance = float('inf') # نبدأ بمسافة لانهائية
for driver in drivers_locations:
# حساب المسافة الإقليدية (مبسطة)
distance = math.sqrt(
(user_location['lat'] - driver['lat'])**2 +
(user_location['lon'] - driver['lon'])**2
)
if distance < min_distance:
min_distance = distance
best_driver = driver
return best_driver, min_distance
# مثال على الاستخدام
# drivers = قائمة ضخمة فيها 5000 سائق أو أكثر
# user = {'lat': 31.5, 'lon': 34.4}
# find_nearest_driver_brute_force(user, drivers)
لماذا هذه الطريقة كارثية؟
المشكلة في التعقيد الزمني (Time Complexity). هاي الخوارزمية تعقيدها O(N)، حيث N هو عدد السائقين. يعني لو عندك 10 آلاف سائق، الكود رح يعمل 10 آلاف عملية حساب ومقارنة لكل طلب واحد! طيب لو عندك 1000 مستخدم بيطلبوا بنفس اللحظة؟ هاد معناه 1000 × 10000 = 10 ملايين عملية حسابية في لحظة واحدة! ما في سيرفر رح يستحمل، ورح “يشرّب زيت” زي ما بنحكي عنا.
المنقذ الذي هبط من السماء: شجرة كيه-دي (k-d tree)
هنا يأتي دور هياكل البيانات الذكية. شجرة k-d (اختصار لـ k-dimensional tree) هي هيكل بيانات مصمم خصيصًا لتنظيم النقاط في فضاء متعدد الأبعاد (k dimensions). في حالتنا، الفضاء ثنائي الأبعاد (k=2)، والأبعاد هي خط العرض (latitude) وخط الطول (longitude).
ما هي هذه الشجرة العجيبة؟
فكر فيها كأنها نسخة مطورة من شجرة البحث الثنائية (Binary Search Tree) اللي بنعرفها. في شجرة البحث الثنائية العادية، كل عقدة (node) بتقسم البيانات لنصفين: كل اللي أصغر منها بروح على اليسار، وكل اللي أكبر منها بروح على اليمين، بناءً على قيمة واحدة.
شجرة k-d بتعمل نفس المبدأ، لكنها أكثر ذكاءً. بدل ما تقسم بناءً على قيمة واحدة دائمًا، هي تتناوب بين الأبعاد في كل مستوى من مستويات الشجرة.
تخيل عندك خريطة مليئة بالنقاط (السائقين). شجرة k-d بتقسم هاي الخريطة بشكل متكرر إلى نصفين، مرة بخط عمودي (بناءً على خط الطول)، ومرة بخط أفقي (بناءً on خط العرض)، وهكذا.
كيف نبني الشجرة؟ (شوية تركيز يا جماعة)
بناء الشجرة هو الخطوة الأولى، ويتم مرة واحدة (أو بشكل دوري). العملية كالتالي:
- المستوى 0 (الجذر – Root):
- نختار البُعد الأول (مثلاً، خط الطول lon).
- نجد النقطة الوسيطة (median) بناءً على هذا البُعد. هاي النقطة بتصير جذر الشجرة.
- كل النقاط اللي خط طولها أصغر من الوسيط بتروح على الشجرة الفرعية اليسرى.
- كل النقاط اللي خط طولها أكبر بتروح على الشجرة الفرعية اليمنى.
- المستوى 1:
- الآن نغير البُعد. نختار البُعد الثاني (خط العرض lat).
- لكل شجرة فرعية (اليسرى واليمنى)، نكرر العملية: نجد الوسيط بناءً على خط العرض، ونقسم النقاط إلى يسار ويمين.
- المستويات التالية:
- نستمر في التكرار، وفي كل مستوى نغير البُعد (lon, lat, lon, lat, …).
النتيجة النهائية هي شجرة متوازنة تقسم الفضاء بطريقة فعالة جدًا.
البحث عن أقرب جار (Nearest Neighbor Search): السحر الحقيقي!
بناء الشجرة جميل، لكن القوة الحقيقية تظهر في عملية البحث. عندما يأتي طلب مستخدم جديد، لا نحتاج للبحث في كل النقاط. الخوارزمية ذكية جدًا:
- النزول في الشجرة: نبدأ من الجذر وننزل لأسفل، تمامًا كما لو كنا نريد إضافة نقطة المستخدم إلى الشجرة. في كل مستوى، نقارن بُعد المستخدم (مثلاً، خط الطول) مع بُعد العقدة الحالية ونقرر الذهاب يمينًا أو يسارًا.
- الوصول للورقة (Leaf): عندما نصل إلى عقدة ورقية (leaf node)، نفترض أن هذه النقطة هي “أفضل تخمين حالي” لأقرب سائق. نحسب المسافة ونحفظها.
- العودة للأعلى (Backtracking) – هنا السحر: الآن نبدأ بالرجوع إلى الأعلى في الشجرة، عقدة تلو الأخرى. وعند كل عقدة نمر بها، نسأل سؤالًا جوهريًا:
هل يمكن أن يوجد في “الجانب الآخر” من هذه العقدة (الجانب الذي لم نزره) نقطة أقرب من أفضل تخمين لدينا حاليًا؟
- التقليم (Pruning): نتحقق من هذا عن طريق مقارنة “أفضل مسافة حالية” مع المسافة إلى “خط التقسيم” الخاص بالعقدة. إذا كانت أفضل مسافة لدينا أصغر من المسافة إلى خط التقسيم، فهذا يعني أنه من المستحيل رياضيًا أن نجد نقطة أقرب في ذلك الفرع بأكمله! وبالتالي، يمكننا تجاهل (تقليم) هذا الفرع بالكامل وعدم البحث فيه.
هذه القدرة على “تقليم” فروع ضخمة من الشجرة هي ما يجعل البحث سريعًا جدًا. بدلًا من مقارنة N نقطة، نحن نقارن عددًا قليلًا جدًا من النقاط، غالبًا ما يكون قريبًا من O(log N) في الحالات المتوسطة. وهذا فرق هائل!
النتائج على أرض الواقع: من ثوانٍ إلى أجزاء من الثانية
بعد ليلتين من العمل المتواصل (مع كثير من القهوة)، استبدلنا كود البحث الشامل الغبي بتنفيذ يعتمد على شجرة k-d. النتائج كانت مذهلة بكل معنى الكلمة:
- زمن بناء الشجرة لـ 5000 سائق: حوالي 50-100 ميلي ثانية.
- زمن البحث عن أقرب سائق: أقل من 1 ميلي ثانية!
تحول زمن الاستجابة من 3-5 ثوانٍ (كانت ستصبح دقائق مع زيادة الحمل) إلى أجزاء من الثانية لا يشعر بها المستخدم. التطبيق أصبح صاروخًا. المشكلة اختفت تمامًا. يومها، المدير التقني عزمني على كنافة نابلسية على حسابه، وكان يستاهلها والله!
نصائح من أبو عمر: متى وكيف تستخدم شجرة k-d؟
من خبرتي، هذه الخوارزمية سلاح قوي، لكن يجب أن تعرف متى وكيف تستخدمه.
نصيحة 1: ليست لكل الحالات (لعنة الأبعاد)
شجرة k-d ممتازة في الأبعاد المنخفضة (2D, 3D, وحتى 10-20 بُعدًا). لكن أداءها يتدهور بسرعة كلما زاد عدد الأبعاد (ظاهرة تسمى “لعنة الأبعاد” – Curse of Dimensionality). إذا كنت تعمل مع بيانات عالية الأبعاد جدًا (مثل تمثيل الكلمات Word Embeddings التي قد تصل لمئات الأبعاد)، فإن k-d tree تصبح غير فعالة، وهناك بدائل أفضل مثل (Annoy, HNSW).
نصيحة 2: الأشجار الثابتة مقابل الديناميكية
بناء الشجرة من الصفر عملية مكلفة نسبيًا. إذا كانت نقاط البيانات (السائقون) تتغير مواقعها باستمرار، فأنت أمام تحدٍ. الحلول الممكنة:
- إعادة البناء الدورية: أسهل حل. قم بإعادة بناء الشجرة كلها كل فترة (مثلاً، كل 15 أو 30 ثانية). هذا ما فعلناه وكان حلاً عمليًا جدًا.
- الأشجار الديناميكية: هناك أنواع متقدمة من أشجار k-d تسمح بإضافة وحذف وتحديث النقاط بكفاءة، لكنها أكثر تعقيدًا في التنفيذ.
نصيحة 3: لا تخترع العجلة!
قصتي كانت في زمن لم تكن فيه المكتبات الجاهزة منتشرة بكثرة. اليوم، لا يوجد أي مبرر لتنفيذ شجرة k-d من الصفر في بيئة الإنتاج إلا لأغراض تعليمية. معظم لغات البرمجة لديها مكتبات قوية ومُختبرة للقيام بذلك.
في Python على سبيل المثال، مكتبة SciPy توفر تنفيذًا رائعًا:
from scipy.spatial import KDTree
import numpy as np
# قائمة بمواقع السائقين (خطوط العرض والطول)
# يجب أن تكون على شكل مصفوفة NumPy
drivers_locations = np.array([
[31.9, 35.9],
[32.0, 35.8],
[31.8, 35.7],
# ... آلاف السائقين
])
# 1. بناء الشجرة (سريع جدًا)
tree = KDTree(drivers_locations)
# 2. البحث عن أقرب سائق
user_location = [31.95, 35.85]
# k=1 يعني أننا نريد أقرب جار واحد فقط
distance, index = tree.query(user_location, k=1)
print(f"أقرب سائق هو السائق رقم {index} في القائمة الأصلية.")
print(f"المسافة إليه هي: {distance}")
print(f"موقعه: {drivers_locations[index]}")
كما ترى، بثلاثة أسطر من الكود، يمكنك الحصول على كل قوة شجرة k-d بدون أي عناء.
الخلاصة: فكر كمهندس، وليس ككاتب كود فقط 👨💻
الدرس الأكبر من هذه القصة ليس فقط عن شجرة k-d، بل عن طريقة التفكير. الحل السهل والمباشر (البحث الشامل) غالبًا ما يكون فخًا يؤدي إلى مشاكل أداء كارثية على المدى الطويل.
قبل أن تفكر في زيادة موارد السيرفر أو شراء عتاد أغلى، خذ خطوة للوراء وافحص خوارزمياتك. هل تستخدم هيكل البيانات المناسب للمشكلة؟ هل هناك طريقة أذكى لحل المسألة؟
إن فهم الخوارزميات وهياكل البيانات الأساسية ليس مجرد مادة نظرية في الجامعة، بل هو السلاح السري الذي يميز المبرمج المحترف عن الهاوي. هو ما يسمح لك ببناء أنظمة سريعة وفعالة وقابلة للتوسع.
فيا صديقي المبرمج، خلي عندك فضول دائمًا، واقرأ، وجرّب. لأن حل مشكلتك القادمة قد يكون مختبئًا في خوارزمية ذكية تنتظر منك أن تكتشفها. ويعطيكم العافية!
