دمج الأفكار المبتكرة: استراتيجيات متقدمة لحل المشكلات البرمجية بكفاءة

تُعد المفاضلات جزءًا لا يتجزأ من جميع أنشطتنا، وهذا ينطبق بشكل خاص على عالم البرمجة وتطوير الحلول التقنية. ربما تكون قد سمعت عن ما يسمى بـ "No Free Lunch Theorem" (نظرية لا غداء مجاني) في مجال تعلم الآلة، والتي تنص على أنه لا يوجد حل سحري واحد يناسب جميع نماذج تعلم الآلة. في الواقع، لا يوجد حل سحري لأي شيء على الإطلاق، وهذا ليس مبدأً يخص علوم الحاسوب فحسب، بل هو مبدأ اقتصادي عام.

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

من الشائع أن تجد حلولًا متعددة للمشكلة نفسها، لأن أحدها قد يكون أسرع بينما الآخر أقل تكلفة من حيث التخزين. وبالطبع، هناك عوامل أخرى مثل سهولة التنفيذ والبساطة والأمان. في هذا المقال، سأتناول كيفية دمج العديد من الحلول للحصول على حل يلبي جميع متطلباتك. سأعرض أولاً فكرة مثيرة للاهتمام اقترحها إي. دبليو. ديكسترا (E.W. Dijkstra) لإيجاد الأعداد الأولية، ثم سأعرض فكرة توصلت إليها للحصول على هيكل بيانات يجمع بين قوة المصفوفات والقوائم المتصلة.

المتطلبات الأساسية لفهم المقال

أفترض أن لديك مهارات برمجية أساسية، بالإضافة إلى بعض المعرفة بهياكل البيانات مثل المصفوفات (arrays)، والقوائم المتصلة (linked lists)، والأكوام (heaps). يجب أن يكون لديك أيضًا فهم لتدوين Big-O notation لحساب التعقيد. أخيرًا، سيكون من الجيد أن تكون على دراية بخوارزمية غربال إراتوستينس. إذا لم تكن كذلك، يمكنك مراجعة هذا الرابط (ضع هنا رابطًا لمقال يشرح الغربال). لا توجد معرفة مسبقة أخرى مطلوبة لفهم ما سأناقشه.

خوارزميتان، مشكلة واحدة: البحث عن الأعداد الأولية

المشكلة هي العثور على جميع الأعداد الأولية من 0 (صفر) إلى N. إنها نوع المشكلات التي تتعلمها عندما تبدأ رحلتك في البرمجة. وأريد أن أبدأ بالحل الأبسط.

الخوارزمية البدائية (Naive Algorithm)

في الخوارزمية البدائية، نقوم بالتكرار على جميع الأعداد x من 2 إلى N. ثم نتحقق مما إذا كان العدد x يحتوي على أي قاسم بخلاف نفسه والواحد. بالنسبة للخطوة الأخيرة، يمكننا التحقق من كل عدد d بين 2 و x - 1 لمعرفة ما إذا كان قاسمًا أم لا. هناك مجال للتحسين في الخطوة الأخيرة، لأننا نحتاج فقط إلى التحقق من القواسم التي تقل عن أو تساوي الجذر التربيعي لـ x.

فيما يلي كود زائف (pseudocode) للخوارزمية:

 primes(N): prime_numbers <- [] # empty list for x = 2 to N: is_prime <- true for d = 2 to sqrt(x): if d divides x: is_prime <- false # we found a divisor of x so x is not a prime number if is_prime: prime_numbers.add(x) # if we didn 't find a divisor then x is prime return prime_numbers 

ما هو تعقيد وقت التشغيل (runtime complexity) للخوارزمية السابقة؟ حسنًا، نأخذ كل عدد من 2 إلى N، ولكل منها، نكرر على جميع قواسمه المحتملة. لذلك نقوم بإجراء O(N*sqrt(N)) عملية، حيث sqrt تعني دالة الجذر التربيعي. ماذا عن الذاكرة؟ نحن نخزن فقط الأعداد الأولية التي نجدها. بالنسبة لـ N كبير بما يكفي، يكون عدد الأعداد الأولية صغيرًا نسبيًا مقارنة بـ N. لذلك، دعنا نشير إلى تعقيد الذاكرة (memory complexity) على أنه O(Primes(N))، حيث Primes(N) هو عدد الأعداد الأولية بين 0 و N. لاحظ أن هذا هو الأمثل من حيث الذاكرة لأننا نحتاج على الأقل إلى تخزين جميع الأعداد الأولية.

غربال إراتوستينس (The Sieve of Eratosthenes)

ربما تعلم بالفعل أن هناك خوارزمية أفضل للعثور على جميع الأعداد الأولية في نطاق معين: غربال إراتوستينس. دعنا نلقي نظرة عليها.

الفكرة هي الحفاظ على مصفوفة بطول N حيث يكون كل إدخال إما false أو true. إذا كان الموضع i في المصفوفة صحيحًا (true)، فإننا نقول إن i هو عدد أولي، وإلا فإن i ليس أوليًا. نبدأ بجميع المواضع بقيمة true، ثم لكل موضع، بدءًا من i = 2، نجعل كل مضاعف لـ i خاطئًا (false). ننتهي بمصفوفة يمثل فيها كل موضع بقيمة true عددًا أوليًا.

الكود مع بعض التحسينات معروض أدناه:

 primes(N): prime_numbers <- [] # empty list sieve <- a boolean list with length equal to N and all its elements set to true for i = 2 to sqrt(N): # we only need to analyze the numbers less than or equal to sqrt(N) if sieve[i]: # if sieve[i] is true then i is prime prime_numbers.add(i) for j = i*i to N: # we can start the inner loop in i*i sieve[j] <- false j <- j + i return prime_numbers 

يمكن إثبات أن الخوارزمية الموصوفة أعلاه تقوم بإجراء O(N log(N)) عملية، وهو أفضل من النهج البدائي. بل يمكن تحسينها لتصبح O(N)! لكننا نحتاج إلى تخزين مصفوفة تحتوي على جميع الأعداد N، وبالتالي، ننتهي بخوارزمية أكثر تكلفة من حيث الذاكرة. هنا لدينا المفاضلة: الوقت مقابل الذاكرة.

ديكسترا وخط الإنتاج: دمج الذكاء والكفاءة

هل يمكننا تصميم خوارزمية أسرع من الفكرة البدائية ولكنها أقل تكلفة من حيث الذاكرة من غربال إراتوستينس؟

في الستينيات، كتب إي. دبليو. ديكسترا (E.W. Dijkstra) في إحدى مخطوطاته [PDF] خوارزمية تجمع بين الأفكار البدائية وأفكار الغربال. ولكن قبل أن نتحدث عنها، دعنا نحلل الاختلافات بين الخوارزميتين السابقتين. عند تطبيق الخوارزمية البدائية، نركز على تحليل ما إذا كان كل عدد أوليًا أم لا. عند تطبيق الغربال، نقوم بتحليل جميع مضاعفات كل عدد أولي.

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

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

إذا كنا نحلل العدد 6، فإننا قد خزننا الأعداد الأولية 2 و 3 و 5، جنبًا إلى جنب مع أصغر مضاعفاتها التي لم يتم تحليلها بعد وهي: 6 للعدد 2، و 6 أيضًا للعدد 3، و 10 للعدد 5. ثم، عند تحليل عدد جديد، نأخذ أصغر مضاعف مخزن حتى تلك اللحظة، وإذا كان هذا المضاعف أكبر من العدد الجديد، فقد وجدنا عددًا أوليًا جديدًا. وإلا، فإن لدينا عددًا مركبًا ونحتاج إلى تحديث مضاعفات الأعداد الأولية المخزنة التي يكون العدد الجديد هو أصغر مضاعف لها.

نبدأ بتخزين العدد الأولي 2 مع أصغر مضاعف له وهو 4. ثم عند تحليل العدد 3، نجد أن 4 > 3، لذا فإن 3 عدد أولي. نخزن 3 جنبًا إلى جنب مع أصغر مضاعف له لم يتم تحليله بعد (6). عند تحليل العدد 4، نجد أن 4 مخزن كمضاعف للعدد 2، ثم نقوم بتحديث مضاعف 2 الذي سيصبح الآن 6. عند تحليل العدد 5، نجد أن 6 > 5، لذا فإن 5 عدد أولي ونخزنه جنبًا إلى جنب مع 10، وهكذا…

الكود معروض أدناه:

 primes(N): primes_pool <- Heap( ( 4 , 2 ) ) # a heap that contains a tuple with a prime number ( 2 ) and its least multiple that hasn 't been analyzed yet (4). prime_numbers <- [2] # a list that contains the number 2 for i = 3 to N: tuple <- getMin(primes_pool) # get the tuple with the minimum multiple, the prime number attached to it is irrelevant mult <- tuple.first # the multiple is stored in the first position of the tuple if mult > i: prime_numbers.add(i) # i is prime! primes_pool.insert( (i*i, i) ) # we insert i along with their least multiple, but it can be inserted i*i instead and the algorithm remains correct continue # otherwise i isn't prime and then... for t such that t is in primes_pool and t.first is equal to mult: t.first <- t.first + t.second # we update every tuple in the pool that has i as it's least multiple return prime_numbers 

الطريقة السابقة تخزن فقط الأعداد الأولية وعددًا آخر لكل من هذه الأعداد الأولية. لذلك لدينا تعقيد ذاكرة O(Primes(N)) وهو نفس الفكرة البدائية. إذا قمنا بتخزين الأعداد الأولية جنبًا إلى جنب مع مضاعفاتها في هيكل مثل الكومة (heap)، نحصل على تعقيد زمني O(N*log N) وهو نفس الغربال. وهكذا حصلنا على ما أردناه! الحيلة هنا هي أننا لا نحتاج إلى تحديد كل مضاعف للعدد الأولي المعطى، بل فقط أصغر مضاعف.

يجب أن أقول إن هذه ليست فكرة عملية بالمعنى الذي لا يكون فيه تعقيد الذاكرة لغربال إراتوستينس سيئًا للغاية، وهي خوارزمية سهلة التنفيذ للغاية. وجهة نظري هي أنه في بعض الأحيان، إذا كان لديك عدة أفكار، كل منها لا يمكن تطبيقه بسبب بعض العيوب، فقد تكون فكرة جيدة دمج نقاط قوتها. هذا يمنحك حلاً هجينًا لمشكلتك. علمني Dijkstra's Factory of Primes هذه الطريقة في التفكير، على الرغم من أنني لم أطبق هذه الخوارزمية في سيناريو واقعي.

دمج المصفوفات مع القوائم المتصلة: هيكلة بيانات هجينة لتحقيق التوازن

المصفوفات (Arrays) هي هياكل بسيطة تسمح لنا بالحصول على عنصر بواسطة فهرسه في وقت ثابت (O(1)). لكننا نحتاج إلى O(N) عملية لإدراج أو إزالة عنصر من/إلى المصفوفة في أسوأ الحالات، حيث N هو طول المصفوفة. من ناحية أخرى، القوائم المتصلة (Linked Lists) هي هياكل تتكون من عقد. كل عقدة لديها مرجع إلى العقدة التالية، وفي حالة القوائم المتصلة المزدوجة (doubly-linked lists)، تحتوي كل عقدة أيضًا على مرجع إلى العقدة السابقة. في هذه الحالة، نحتاج إلى O(N) عملية للوصول إلى عقدة في أسوأ الحالات، ولكن عمليات الإدراج والإزالة يمكن إجراؤها في وقت ثابت (O(1)).

أعتقد أنه من الطبيعي التفكير في "هيكل بيانات مثالي" يسمح لنا بإجراء العمليات الثلاث (الوصول، الإدراج، الحذف) في وقت ثابت. للأسف، مثل هذا الهيكل غير موجود، لكنني وجدت نقطة وسط بين القطبين المتعارضين.

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

بالنظر إلى المشكلة من هذه الزاوية، تبدو فكرة إيجاد نقطة وسط في عدد المراجع طبيعية. ماذا يحدث إذا احتفظنا بمرجع لـ sqrt(N) عقدة من القائمة المتصلة بدلاً من الإشارة إلى العنصر الأول والأخير فقط؟ هذا يسمح لنا بالحصول على قائمة بطول sqrt(N) بحيث تكون المسافة بين كل من هذه العقد في القائمة الفعلية هي sqrt(N). وبذلك، يمكننا إجراء كل عملية (الفهرسة، الإدراج، الحذف) في O(sqrt(N)).

إذا كنت ترغب في رؤية المزيد من التفاصيل حول هذا الهيكل وتطبيق Lisp له، يمكنك ذلك هنا (ضع هنا رابطًا للمزيد من التفاصيل). لقد كتبت أيضًا منشورًا عنه في مدونتي الشخصية (ضع هنا رابطًا للمدونة).

الخاتمة: دروس في التصميم الهجين

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

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

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

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