التحليل المستهلك

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

في علوم الحاسوب ، يُعدّ التحليل المُستهلك طريقةً لتحليل تعقيد خوارزمية معينة ، أو مقدار الموارد اللازمة لتنفيذها ، لا سيما الوقت أو الذاكرة . يكمن الدافع وراء التحليل المُستهلك في أن النظر إلى أسوأ وقت تشغيل قد يكون متشائمًا للغاية. بدلًا من ذلك، يُحسب متوسط ​​أوقات تشغيل العمليات في تسلسل معين على مدار ذلك التسلسل. [ 1 ] : 306 وخلاصةً: "يُعدّ التحليل المُستهلك أداةً مفيدةً تُكمّل تقنيات أخرى مثل تحليل أسوأ حالة وتحليل متوسط ​​الحالة ." [ 2 ] : 14 [ 3 ]

بالنسبة لعملية معينة في خوارزمية ما، قد تتطلب بعض الحالات (مثل معلمات الإدخال أو محتويات بنية البيانات) تكلفة كبيرة من الموارد، بينما قد لا تكون حالات أخرى مكلفة بنفس القدر. يأخذ التحليل المُستهلك في الاعتبار العمليات المكلفة والأقل تكلفة معًا على امتداد سلسلة العمليات بأكملها. وقد يشمل ذلك مراعاة أنواع الإدخال المختلفة، وطول الإدخال، وعوامل أخرى تؤثر على أدائه. [ 2 ]

تاريخ

نشأ التحليل المُستهلك في البداية من طريقة تُسمى التحليل التجميعي، والتي تُعتبر الآن جزءًا من التحليل المُستهلك. وقد قدّم روبرت تارجان هذه التقنية رسميًا لأول مرة في بحثه المنشور عام 1985 بعنوان " التعقيد الحسابي المُستهلك" [ 1 ] ، والذي تناول الحاجة إلى شكل تحليل أكثر فائدة من الطرق الاحتمالية الشائعة الاستخدام. استُخدم الاستهلاك في البداية لأنواع محددة جدًا من الخوارزميات، لا سيما تلك التي تتضمن الأشجار الثنائية وعمليات الاتحاد . ومع ذلك، فقد أصبح الآن واسع الانتشار ويُستخدم عند تحليل العديد من الخوارزميات الأخرى أيضًا. [ 2 ]

طريقة

يتطلب التحليل المُستهلك معرفة سلسلة العمليات الممكنة. وهذا شائعٌ في هياكل البيانات ، التي تحتفظ بحالةٍ بين العمليات. الفكرة الأساسية هي أن عمليةً في أسوأ الحالات يُمكنها تغيير الحالة بطريقةٍ تمنع تكرار أسوأ الحالات لفترةٍ طويلة، وبالتالي "تُستهلك" تكلفتها.

توجد عموماً ثلاث طرق لإجراء تحليل الاستهلاك: الطريقة الإجمالية، والطريقة المحاسبية ، والطريقة المحتملة . جميع هذه الطرق تعطي نتائج صحيحة؛ ويعتمد اختيار الطريقة الأنسب على ما هو ملائم لحالة معينة. [ 4 ]

  • يحدد التحليل الإجمالي الحد الأعلى T ( n ) للتكلفة الإجمالية لتسلسل من n عملية، ثم يحسب التكلفة المستهلكة لتكون T ( n ) / n . [ 4 ]
  • تُعدّ طريقة المحاسبة شكلاً من أشكال التحليل الإجمالي، حيث تُخصّص لكل عملية تكلفة مُستهلكة قد تختلف عن تكلفتها الفعلية. تكون التكلفة المُستهلكة للعمليات المبكرة أعلى من تكلفتها الفعلية، مما يُراكم "رصيدًا" مُدخرًا يُستخدم لتغطية تكاليف العمليات اللاحقة التي تكون تكلفتها المُستهلكة أقل من تكلفتها الفعلية. ولأن الرصيد يبدأ من الصفر، فإن التكلفة الفعلية لسلسلة من العمليات تساوي التكلفة المُستهلكة مطروحًا منها الرصيد المُتراكم. ولأن الرصيد يجب أن يكون غير سالب، فإن التكلفة المُستهلكة تُمثّل حدًا أعلى للتكلفة الفعلية. عادةً ما تُراكم العديد من العمليات قصيرة الأجل هذا الرصيد على دفعات صغيرة، بينما تُقلّله العمليات طويلة الأجل النادرة بشكل كبير. [ 4 ]
  • تُعدّ طريقة الإمكانات شكلاً من أشكال طريقة المحاسبة حيث يتم حساب الرصيد المدخر كدالة (الإمكانات) لحالة بنية البيانات. التكلفة المستهلكة هي التكلفة المباشرة مضافًا إليها التغير في الإمكانات. [ 4 ]

أمثلة

مصفوفة ديناميكية

تحليل استهلاكي لعملية الدفع لمصفوفة ديناميكية

لنفترض وجود مصفوفة ديناميكية يزداد حجمها مع إضافة المزيد من العناصر إليها، كما هو الحال ArrayListفي لغتي جافا std::vectorوسي++. إذا بدأنا بمصفوفة ديناميكية بحجم 4، فيمكننا إضافة 4 عناصر إليها، وستستغرق كل عملية وقتًا ثابتًا . لكن إضافة عنصر خامس إلى تلك المصفوفة سيستغرق وقتًا أطول، إذ سيتعين على المصفوفة إنشاء مصفوفة جديدة بحجم مُصغّر، ونسخ العناصر القديمة إلى المصفوفة الجديدة، ثم إضافة العنصر الجديد. وبالمثل، ستستغرق عمليات الإضافة القليلة التالية وقتًا ثابتًا، ثم تتطلب عملية الإضافة اللاحقة تصغيرًا بطيئًا آخر لحجم المصفوفة.

بشكل عام، بالنسبة لعدد عشوائين{\displaystyle n}بالنسبة لعمليات الدفع إلى مصفوفة بأي حجم ابتدائي، يتم جمع أوقات الخطوات التي تُوسّع المصفوفة في سلسلة هندسية إلىيا(ن){\displaystyle O(n)}بينما تُضاف الأوقات الثابتة لكل دفعة متبقية أيضًا إلىيا(ن){\displaystyle O(n)}وبالتالي، فإن متوسط ​​الوقت لكل عملية دفع هويا(ن)/ن=يا(1){\displaystyle O(n)/n=O(1)}يمكن صياغة هذا المنطق وتعميمه ليشمل هياكل بيانات أكثر تعقيدًا باستخدام التحليل المُستهلك. [ 4 ]

طابور

يظهر هنا تطبيق بايثون لقائمة انتظار ، وهي بنية بيانات FIFO :

class Queue : """تمثل مجموعة FIFO (الأول في الأول خارج).""" # تهيئة قائمة الانتظار بقائمتين فارغتين def __init__ ( self ): self.input = [] # تخزين العناصر التي تمت إضافتها إلى قائمة الانتظار self.output = [ ] # تخزين العناصر التي تمت إزالتها من قائمة الانتظارdef enqueue ( self , element ): " " " أضف عنصرًا إلى نهاية قائمة الانتظار.""" self.input.append ( element ) # أضف العنصر إلى قائمة الإدخالدالة dequeue ( self ): """إزالة العنصر الموجود في بداية قائمة الانتظار وإعادته.""" إذا لم تكن قائمة الإخراج فارغة : # إذا كانت قائمة الإخراج فارغة # انقل جميع العناصر من قائمة الإدخال إلى قائمة الإخراج ، مع عكس الترتيب بينما قائمة الإدخال غير فارغة : # طالما أن قائمة الإدخال غير فارغة self.output.append ( self.input.pop ( ) ) # اسحب العنصر الأخير من قائمة الإدخال وأضفه إلى قائمة الإخراجreturn self.output.pop ( ) # إزالة العنصر الأخير من قائمة الإخراج وإرجاعه

عملية الإضافة إلى قائمة الانتظار تقوم فقط بدفع عنصر إلى مصفوفة الإدخال؛ هذه العملية لا تعتمد على أطوال الإدخال أو الإخراج، وبالتالي تعمل في وقت ثابت.

لكن عملية إزالة عنصر من الطابور أكثر تعقيدًا. إذا كانت مصفوفة الإخراج تحتوي بالفعل على بعض العناصر، فإن عملية إزالة العنصر من الطابور تعمل في وقت ثابت؛ وإلا، فإنها تستغرق وقتًا أطول .يا(ن){\displaystyle O(n)}يستغرق الأمر وقتًا لإضافة جميع العناصر من مصفوفة الإدخال إلى مصفوفة الإخراج، حيث n هو الطول الحالي لمصفوفة الإدخال. بعد نسخ n عنصرًا من الإدخال، يمكننا إجراء n عملية إزالة من قائمة الانتظار، تستغرق كل منها وقتًا ثابتًا، قبل أن تصبح مصفوفة الإخراج فارغة مرة أخرى. وبالتالي، يمكننا إجراء سلسلة من n عملية إزالة من قائمة الانتظار في وقت أقل من 1000 ثانية.يا(ن){\displaystyle O(n)}الوقت ، مما يعني أن الوقت المستهلك لكل عملية إخراج من قائمة الانتظار هويا(1){\displaystyle O(1)}. [ 5 ]​

بدلاً من ذلك، يمكننا تحميل تكلفة نسخ أي عنصر من مصفوفة الإدخال إلى مصفوفة الإخراج على عملية الإضافة السابقة لهذا العنصر. يؤدي نظام التحميل هذا إلى مضاعفة الوقت المستهلك للإضافة، ولكنه يقلل الوقت المستهلك للإخراج إلى ⁠يا(1){\displaystyle O(1)}⁠ .

الاستخدام الشائع

مراجع

  1. 1 2 تارجان، روبرت إندري (أبريل 1985). "التعقيد الحسابي المُستهلك" (ملف PDF) . مجلة SIAM للطرق الجبرية والمنفصلة . 6 (2): 306-318 . doi : 10.1137/0606031 . مؤرشف (ملف PDF) من الأصل في 26 فبراير 2015. تم الاطلاع عليه في 9 يونيو 2024 .
  2. 1 2 3 ريبيكا فيبرينك (2007)، شرح التحليل المستهلك (ملف PDF) ، مؤرشف من النسخة الأصلية (ملف PDF) في 20 أكتوبر 2013 ، تم استرجاعه في 3 مايو 2011
  3. ↑ "المحاضرة 18: الخوارزميات المُستهلكة" . CS312 - هياكل البيانات والبرمجة الوظيفية . جامعة كورنيل. 2006. [التحليل المُستهلك] يختلف عما يُعرف عادةً بتحليل الحالة المتوسطة، لأن التحليل المُستهلك لا يفترض أي شيء عن توزيع قيم البيانات، بينما يفترض تحليل الحالة المتوسطة أن البيانات ليست "سيئة" (على سبيل المثال، بعض خوارزميات الفرز تعمل بشكل جيد "في المتوسط" على جميع ترتيبات الإدخال ولكنها سيئة للغاية على ترتيبات إدخال معينة). أي أن التحليل المُستهلك هو تحليل أسوأ حالة، ولكن لتسلسل من العمليات، وليس للعمليات الفردية.
  4. 1 2 3 4 5 كوزين، ديكستر (ربيع 2011). "محاضرة CS 3110 رقم 20: التحليل المُستهلك" . جامعة كورنيل . تم الاطلاع عليه بتاريخ 14 مارس 2015 .
  5. ↑ غروسمان، دان. "CSE332: تجريدات البيانات" (ملف PDF) . cs.washington.edu . تم الاطلاع عليه بتاريخ 14 مارس 2015 .

الأدب