في هذه الصفحة
هنالك الكثير ممن يظنون أن هياكل البيانات والخوارزميات لا يتم استعمالهم بشكل كبير إلا في الـ Problem Solving وخصوصًا على مواقع الـ Competitive Programming والتي من أمثلتها: LeetCode, CodeForces, HackerRank ولا أكذبكم القول فقد كنت من ضمن هؤلاء الفئة في فترة ما.
ولكن الآن وبعد تعرضي لمشاكل متنوعة تختلف بطبيعة المشروع الذي أعمل عليه، تغير تفكيري كثيرًا فأصبح اختيار نوع هياكل البيانات المستخدم بمثابة شيء رئيسيي في تحسين الأداء وفي كيفية التغلب على المشاكل. في كثير من الأحيان يكون الاعتماد بشكل أساسي على نوعين إلى ثلاثة فقط وهم الـ List والـ Map والـ Set ، هذا بالتأكيد إن لم تكن المشكلة التي أحاول حلها تتطلب نوع آخر كالـ Graph, Queue, Stack وغيرهم.
من فترة قريبة كنت أحاول حل مشكلة ما في أحد المشاريع التي أعمل عليها ولإنني أعتدت على الـ Functional Programming Style والتي تمكنك من كتابة كود مقروء قابل للصيانة بشكل جيد، استعملت الـ Java Streams.
ما هي المشكلة التي نحاول حلها ؟
كان من المفترض أن أقوم بعملية Synchronisation للبيانات التي تتواجد بين نظامين مختلفين، وكان لابد من البحث في List تحتوي أكثر من ٦٠ ألف عنصر وأريد أن أتأكد هل هم متواجدون في الـ List الآخرى أم لا.
ما هو الحل السريع الذي قد يخطر في البال ؟
حتمًا سيكون استعمال الـ Built-in Functions التي توفرها اللغة وبما أن اللغة التي أستعملها في هذا المشروع هي لغة الـ Java فاللغة تتيح لك البحث في الـ List من خلال Contains Function وهي المسئولة عن ابلاغك بتواجد العنصر من عدمه.
var systemTwoEmployees = systemTwoService.getAllEmployees();
var systemOneEmployees = systemOneService.getAllEmployees()
.stream()
.filter(e -> !systemTwoEmployees.contains(e.getEmail()))
.collect(Collectors.toList());ما المشكلة في هذا الحل ؟
المشكلة بكل تأكيد هو عدم معرفتك وإلمامك بطبيعة تلك الـ Function أو بمعنى أدق بالـ BigO Annotation، فإذا قمت بالبحث في الـ Documentation ستجد بأن تلك الـ Function تخبرك بتواجد العنصر من عدمه عن طريق أنها تقوم بفحص كل عنصر موجود في الـ List وتقارنه بالذي تبحث عنه. وهذا سيتطلب BigO(N^2) ، هذا لإنها تتبع الـ Linear Search.
ولإني كنت مهتم بتحسين الأداء قدر المستطاع للعملية ككل، خصوصًا أنه Http Call ولا بد من الرد بـ Response .. فهنا نرى جمال دراسة هياكل البيانات والخورازميات.
كيفية تحسين الأداء ؟
في الغالب الخوارزمية التي درسناها كلنا في الجامعة ولا بد أنها حضرت في ذهنك أثناء قراءة هذا، هي أننا يمكننا استبدال طريقة البحث بأخرى كالـ Binary Search ولكن لاستعمال الـ Binary Search فلا بد من عمل ترتيب للعناصر أولًا .. وهذا سيجعل الـ BigO الكلية هي حاصل جمع ترتيب العناصر وعملية البحث مما يعني BigO(NLogN) + BigO(LogN) , فستصبح النتيجة النهائية هي BigO(NLogN) كأسوء تقدير ..
بدلًا من اعادة صنع العجلة، بحثت عن كيفية تحقيق ذلك باستعمال Built in functions في اللغة تدعم الـ Binary Search، وبالفعل تحسن الأداء كثيرًأ عما سبق.
مقارنة الحلين ؟
نظرًا للطريقة الأولى كان الوقت التي تأخذه المهمة لاتمام عملها هي ٦ ثواني، وبعد استبدالها بالـ Binary Search أصبح الآن ٥٠ مللي ثانية وهو بالطبع أفضل بكثير.
كيف كان اختيارنا خاطئًا منذ البداية في اختيار هياكل البيانات ؟
رغم تحسين الأداء الذي لاحظناه، كان هنالك خطأ في الأساس لاختيار هياكل البيانات ، فماذا سيكون رأيك لو استبدلنا الـ List بالـ HashSet أو Set بمعنى آخر ؟ فالـ HashSet هي مبنية على الـ HashMap أو ما يعرف بالـ Dictionary ،، ومن مميزات هذا النوع من هياكل البيانات أنه سريع الاستجابة لعمليات البحث .. حيث تصل الـ Big(O) فيه بنسبة كبيرة إلى BigO(1) .. وسيكون استعمال Function Contains هنا هو الحل الأمثل لذلك.
كيف أصبح الأداء النهائي بعد تغيير هياكل البيانات ؟
أصبحت المهمة تأخذ ٩ مللي ثانية فقط وتقوم بالرد بسرعة.
Set<String> systemTwoEmployeeEmails = systemTwoService.getAllEmployees()
.stream()
.map(e -> e.getEmail())
.collect(Collectors.toSet());
List<Employees> systemOneEmployees = systemOneService.getAllEmployees()
.stream()
.filter(e -> !systemTwoEmployeeEmails.contains(e.getEmail()))
.collect(Collectors.toList());
