كيف تعزز أداء خوارزمية البحث العميق (DFS) باستخدام الـ Goroutines في Go

مقدمة: البحث العميق (DFS) وتحديات الأداء

تُعد خوارزمية البحث العميق (Depth First Search أو اختصاراً DFS) إحدى الخوارزميات الشائعة والأساسية في اجتياز الرسوم البيانية (Graph Traversal). تتجلى أهميتها في العديد من التطبيقات الواقعية، مثل بناء خرائط المواقع (Site Mapping). خريطة الموقع هي قائمة منظمة هرمياً بصفحات الويب، توضح البنية الكاملة للموقع بدءاً من العقدة الجذرية.

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

المشكلة: عنق الزجاجة في التنفيذ التسلسلي

إذا قمنا بتطبيق خوارزمية البحث العميق بالطريقة التقليدية، فإن عملية تحميل وتحليل صفحات HTML تستغرق وقتاً طويلاً، مما يعيق عملية الاجتياز بأكملها. على سبيل المثال، إذا استغرق استجابة HTTP الواحدة 300 مللي ثانية في المتوسط، وكان هناك 100 صفحة في الموقع يجب تحليلها، فإن الوقت الإجمالي سيكون 300 * 100 = 30000 مللي ثانية، أي 30 ثانية. خلال هذه الفترة، يظل المعالج خاملاً ينتظر اكتمال كل عملية على حدة.

الحل: قوة التزامن مع الـ Goroutines

لتحسين هذا الأداء، يمكننا إرسال طلبات HTTP متعددة وتحليل صفحات HTML المستلمة بشكل متزامن (Concurrently) أثناء انتظار تحميل الصفحات الأخرى. تُظهر هذه الطريقة المتزامنة تحسناً كبيراً في السرعة، حيث يمكن أن تكون أسرع بسبع مرات من الطريقة التسلسلية المذكورة سابقاً.

قد يثير تطبيق الخيوط (Threads) مخاوف لدى العديد من المطورين بسبب التعقيدات المحتملة. ومع ذلك، توفر لغة Golang مجموعة رائعة من المفاهيم مثل الـ goroutines والقنوات (channels) وأدوات المزامنة (synchronization utilities) التي تجعل هذه المهمة أسهل بكثير.

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

يمكنك العثور على الكود المستخدم في هذا المقال هنا على GitHub.

إعداد شجرة البيانات الثنائية

لغرض التوضيح، سنقوم بإنشاء شجرة بيانات ثنائية بسيطة. هذه الشجرة هي الأساس الذي سنطبق عليه خوارزمية البحث العميق.

تعريف العقدة (Node Definition)

هيكل العقدة (Node struct) هو اللبنة الأساسية لشجرتك الثنائية. تحتوي على بيانات (Data)، ومؤشر للعقدة اليسرى (Left child)، ومؤشر للعقدة اليمنى (Right child). لمحاكاة التأخير في معالجة العقدة، سنقوم بتعيين وقت نوم عشوائي (random sleep time) بالميكروثانية.

type Node struct {
    Data interface{}
    Sleep time.Duration
    Left *Node
    Right *Node
}

دالة إنشاء العقدة (Node Generator Function)

تقوم دالة NewNode() بإرجاع مؤشر إلى عقدة جديدة. يتم تعيين وقت النوم (Sleep) لمدة تتراوح بين 0 و 100 ميكروثانية بشكل عشوائي.

func NewNode(data interface{}) *Node {
    node := new(Node)
    node.Data = data
    node.Left = nil
    node.Right = nil
    rand.Seed(time.Now().UTC().UnixNano())
    duration := int64(rand.Intn(100))
    node.Sleep = time.Duration(duration) * time.Microsecond
    return node
}

الآن بعد أن قمت بإعداد شجرتك، يمكنك البدء في تطبيق خوارزمية البحث العميق ودالة لمعالجة العقدة.

البحث العميق أحادي المسار (Single-Threaded DFS)

لنبدأ بتطبيق خوارزمية البحث العميق بالطريقة التقليدية أحادية المسار، والتي ستوضح لنا التحديات التي نسعى لحلها.

دالة معالجة العقدة (ProcessNode())

دالة ProcessNode() هي الدالة التي سيتم استدعاؤها عندما يتعين معالجة العقدة أثناء الاجتياز. عادةً ما تقوم بطباعة أو تخزين قيمة العقدة. ومع ذلك، لإظهار فوائد الـ goroutines، سيتعين عليك تنفيذ مهمة تتطلب الكثير من العمليات الحسابية وتستغرق حوالي ثانية واحدة. خلال كل تكرار، تنام العقدة لمدة n.Sleep ميكروثانية وتطبع Node <data> ✅ بمجرد اكتمال المهمة.

func (n *Node) ProcessNode() {
    var hello []int
    for i := 0; i < 10000; i++ {
        time.Sleep(n.Sleep)
        hello = append(hello, i)
    }
    fmt.Printf("Node %v ✅\n", n.Data)
}

دالة البحث العميق التكرارية (DFS Recursive Function)

هذه هي دالة البحث العميق أحادية المسار المنفذة باستخدام التكرار (recursion) – قد تبدو مألوفة لأولئك الذين كتبوها من قبل.

func (n *Node) DFS() {
    if n == nil {
        return
    }
    n.Left.DFS()
    n.ProcessNode()
    n.Right.DFS()
}

تطبيق الدالة الرئيسية (Implementing the main() Function)

في الدالة الرئيسية (main())، سنقوم بإنشاء شجرة ثنائية كاملة تتكون من 7 عقد. لمعرفة مقدار الوقت الذي انقضى، سنبدأ مؤقت start ثم نبدأ عملية البحث العميق (DFS) من الجذر. بمجرد اكتمالها، تقوم الدالة main() بطباعة الوقت المنقضي.

var wg sync.WaitGroup

func main() {
    root := NewNode(1)
    root.Left = NewNode(2)
    root.Right = NewNode(3)
    root.Left.Left = NewNode(4)
    root.Left.Right = NewNode(5)
    root.Right.Left = NewNode(6)
    root.Right.Right = NewNode(7)

    start := time.Now()
    root.DFS()
    fmt.Printf("\nTime elapsed: %v\n\n", time.Since(start))
}

الناتج (Output)

استغرقت عملية البحث العميق 8.75s للاكتمال. في معظم الوقت، كان المعالج خاملاً بينما كانت كل عقدة تتم معالجتها. كما منعت العقد الأخرى من المعالجة أثناء اكتمال وقت نومها. في العالم الحقيقي، يحدث هذا الموقف أثناء عمليات الإدخال/الإخراج (I/O) أو استدعاءات HTTP الخارجية.

Node 4 ✅
Node 2 ✅
Node 5 ✅
Node 1 ✅
Node 6 ✅
Node 3 ✅
Node 7 ✅

Time elapsed: 8.75086767 s

تعزيز أداء البحث العميق باستخدام الـ Goroutines

الآن، لننتقل إلى الجزء المثير: كيفية تسريع خوارزمية البحث العميق باستخدام قوة الـ goroutines في Go. ستلاحظ أن التغييرات المطلوبة بسيطة جداً مقارنة بلغات البرمجة الأخرى.

مقدمة للـ Goroutines والتزامن

يتضمن تحويل دوال المعالجة والبحث العميق إلى دوال متزامنة تغييرات طفيفة:

• استدعاء الدالة التكرارية باستخدام الأمر go.
• الحفاظ على waitGroup الذي يتتبع الدوال قيد المعالجة، حتى لا يخرج البرنامج قبل اكتمال جميع الـ goroutines.

دالة البحث العميق المتوازي (DFSParallel())

• wg.Add(1): قبل الدخول في التكرار، أضف الـ goroutine الذي سيبدأ إلى الـ waitGroup. يمكنك أيضاً تشغيل wg.Add(3) ثم بدء الـ goroutines الثلاثة وسيقوم بالمهمة. ومع ذلك، هذه الطريقة أكثر جمالية وتوضح بوضوح ما سيحدث.
• defer wg.Done(): تقلل عداد الـ waitGroup بمقدار 1 عندما تعود الدالة. هذا يشير إلى أن الـ goroutine قد اكتمل.
• go: يبدأ الدالة في goroutine جديدة.

func (n *Node) DFSParallel() {
    defer wg.Done()
    if n == nil {
        return
    }
    wg.Add(1)
    go n.Left.DFSParallel()
    wg.Add(1)
    go n.ProcessNodeParallel()
    wg.Add(1)
    go n.Right.DFSParallel()
}

دالة معالجة العقدة المتوازية (ProcessNodeParallel())

لا يوجد الكثير لتفعله هنا، فقط أضف defer wg.Done() بعد بدء الدالة. ستخبر هذه التعليمة الـ waitGroup بأن هذا الـ goroutine قد انتهى.

func (n *Node) ProcessNodeParallel() {
    defer wg.Done()
    var hello []int
    for i := 0; i < 10000; i++ {
        time.Sleep(n.Sleep)
        hello = append(hello, i)
    }
    fmt.Printf("Node %v ✅\n", n.Data)
}

استدعاء DFSParallel() في الدالة الرئيسية (main())

• GOMAXPROCS: تخبر مترجم Go بتشغيل الخيوط (threads) على جميع النوى المنطقية المتاحة في الكمبيوتر. سيساعدك هذا على معالجة عقد متعددة أيضاً. يوضح نمط التصميم المتزامن الذي تم تنفيذه هنا فائدة وجود نوى متعددة في الكمبيوتر. لا يستطيع البرنامج معالجة العقد الأخرى أثناء نوم إحداها فحسب، بل يمكنه أيضاً معالجة عقد متعددة في نفس الوقت.
• يمكنك بدء DFSParallel() كـ goroutine كما كان من قبل وإضافته إلى مجموعة الانتظار (wait group).
• wg.Wait(): تنتظر حتى تكتمل جميع الـ goroutines. تنتظر حتى يصبح عدد الـ goroutines صفراً ثم تحرك التحكم إلى الأمام.

...
    // Go will use maximum number of processors available to process goroutines
    processors := runtime.GOMAXPROCS(runtime.NumCPU())
    fmt.Printf("\nTime elapsed: %v\n\n", time.Since(start))

    // Starts the timer
    start = time.Now()

    // Adds one goroutine the WaitGroup
    wg.Add(1)

    // Start the DFS Goroutine
    go root.DFSParallel()

    // Waits for all goroutines to complete
    wg.Wait()

    fmt.Printf("\nProcessors: %v Time elapsed: %v\n", processors, time.Since(start))
}

الناتج (Output)

كما هو متوقع، تكتمل خوارزمية البحث العميق في 1.3 ثانية فقط مقارنة بـ 8.7 ثوانٍ في التنفيذ السابق. هذا يوضح التحسن الهائل الذي يمكن تحقيقه من خلال التزامن.

Node 7 ✅
Node 4 ✅
Node 2 ✅
Node 6 ✅
Node 5 ✅
Node 1 ✅
Node 3 ✅

Processors : 8 Time elapsed: 1.295332809 s

شرح ومقارنة الأداء

لفهم سبب هذا التحسن الكبير، دعنا نقارن بين طريقة عمل التنفيذ التقليدي والتنفيذ المتزامن.

التطبيق التقليدي (Normal Implementation)

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

التطبيق المتزامن (Concurrent Implementation)

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

الخلاصة

إن النتائج التي توصلنا إليها مذهلة حقاً؛ لم يتطلب الأمر سوى بضعة مفاهيم و5-6 أسطر إضافية من الكود لجعل هذا البرنامج أسرع بسبع مرات. يمكن أن تثبت هذه التقنية أنها دفعة كبيرة لبرنامج Go الخاص بك إذا تمكنت من تحديد الدوال التي يمكن تشغيلها بشكل مستقل في نفس الوقت. إذا كانت دوالك تتطلب المزامنة، فيمكنك استخدام القنوات (channels) لإنجاز هذه المهمة بكفاءة.

يمكنك العثور على الكود المستخدم في هذا المقال هنا على GitHub.

الخلاصة التقنية

يُبرز هذا المقال ببراعة قوة لغة Go في معالجة المهام المتزامنة، خاصةً من خلال مفهوم الـ goroutines و WaitGroup. بينما تُعد خوارزمية البحث العميق (DFS) أساسية في علوم الحاسوب، فإن تطبيقها التقليدي أحادي المسار غالباً ما يواجه تحديات كبيرة في الأداء عند التعامل مع عمليات الإدخال/الإخراج الكثيفة أو المهام التي تتطلب وقتاً طويلاً. يُظهر الحل المتزامن باستخدام الـ goroutines كيف يمكن تحويل هذه العوائق إلى فرص لتحسين الكفاءة بشكل جذري.

إن سهولة استخدام الـ goroutines، التي تُعد خيوطاً خفيفة الوزن تُدار بواسطة وقت تشغيل Go، جنباً إلى جنب مع آليات المزامنة مثل WaitGroup، تجعل البرمجة المتزامنة في Go أكثر بساطة وأماناً مقارنة بنماذج الخيوط التقليدية في لغات أخرى. هذا النهج لا يقلل فقط من وقت التنفيذ الإجمالي بشكل كبير، بل يستغل أيضاً القدرات الكاملة للمعالجات متعددة النوى، مما يفتح آفاقاً جديدة لتطوير تطبيقات عالية الأداء والاستجابة. يُعد تحديد المهام القابلة للتوازي أمراً حاسماً لاستغلال هذه القوة، وعند الحاجة إلى اتصال بين الـ goroutines، توفر القنوات حلاً أنيقاً وآمناً.