قياس الزمن والذاكرة فعليًّا
قبل النظرية: نقيس بالساعة والبايت، ونرى كيف ينمو الزمن مع البيانات. ⏱ نحو 30 دقيقة.
- تميّز بين الكفاءة الزمنية والمساحية والمقايضة بينهما.
- تقيس زمن التنفيذ بـ
perf_counterوtimeit. - تلاحظ نمط نمو الزمن حين يتضاعف حجم المدخل.
- تقيس الذاكرة بـ
getsizeofوtracemalloc، وتعرف حدود القياس التجريبي.
١ما الكفاءة؟
كفاءة الخوارزمية تعني: كم موردًا تستهلك لتحل المسألة؟ والموردان الأهم:
| المورد | السؤال | يسمى تحليله |
|---|---|---|
| الزمن | كم تستغرق حتى تنتهي؟ | التعقيد الزمني Time Complexity |
| الذاكرة | كم مساحة تحتاج أثناء العمل؟ | التعقيد المساحي Space Complexity |
وبينهما مقايضة كثيرًا: نوفّر الزمن باستهلاك ذاكرة أكثر (مثل حفظ النتائج لنعيد استخدامها)، أو العكس.
٢قياس الزمن بساعة
الدالة time.perf_counter() ساعة دقيقة جدًّا. نأخذ الوقت قبل العمل وبعده، والفرق زمن التنفيذ:
import time start = time.perf_counter()total = 0for i in range(1_000_000): total += iend = time.perf_counter() print("المجموع:", total)print("الزمن بالملّي ثانية:", round((end - start) * 1000, 1))
٣قياس أدق: timeit
القياس مرة واحدة يتأثر بأي برنامج آخر يعمل في الجهاز. المكتبة timeit تكرر التنفيذ وتعطي زمنًا أدق. نقارن طريقتين لمعرفة هل الرقم موجود:
import timeit setup = "data_list = list(range(100000)); data_set = set(data_list)"t_list = timeit.timeit("99999 in data_list", setup=setup, number=200)t_set = timeit.timeit("99999 in data_set", setup=setup, number=200) print("القائمة:", round(t_list * 1000, 2), "ms")print("المجموعة:", round(t_set * 1000, 4), "ms")print("المجموعة أسرع بنحو", round(t_list / t_set), "مرة")
٤كيف ينمو الزمن مع حجم المدخل؟
الأهم من زمن حجم واحد: ماذا يحدث حين يتضاعف المدخل؟ نقيس خوارزميتين: الأولى تمر على القائمة مرة واحدة، والثانية تقارن كل عنصر بكل عنصر:
import time def once(a): # مرور واحد s = 0 for x in a: s += x return s def pairs(a): # كل عنصر مع كل عنصر c = 0 for x in a: for y in a: if x < y: c += 1 return c def measure(f, n): a = list(range(n)) t = time.perf_counter() f(a) return time.perf_counter() - t for n in [500, 1000, 2000]: print(n, "| مرور واحد:", round(measure(once, n) * 1000, 2), "ms | كل زوج:", round(measure(pairs, n) * 1000, 1), "ms")
لاحظ النمط لا الأرقام: حين يتضاعف n يتضاعف زمن «المرور الواحد» تقريبًا، ويتضاعف زمن «كل زوج» نحو أربع مرات. هذا النمط هو ما يصفه ترميز O الكبير في الدرس القادم.
٥قياس الذاكرة
sys.getsizeof تعطي حجم الكائن بالبايت. قارن قائمة مليون رقم بـ range الذي لا يخزّن الأرقام بل يولّدها عند الحاجة:
import sys numbers = list(range(1_000_000))lazy = range(1_000_000)squares_gen = (x * x for x in range(1_000_000)) print("القائمة:", sys.getsizeof(numbers) // 1024, "KB")print("range:", sys.getsizeof(lazy), "بايت")print("المولّد:", sys.getsizeof(squares_gen), "بايت")
وللقياس الأدق لكل ما يحجزه البرنامج نستخدم tracemalloc:
import tracemalloc tracemalloc.start()data = [i * 2 for i in range(100_000)]current, peak = tracemalloc.get_traced_memory()tracemalloc.stop()print("أقصى ذاكرة:", peak // 1024, "KB")
٦حدود القياس التجريبي
| المشكلة | مثال |
|---|---|
| يعتمد على الجهاز | حاسوب المعمل أسرع من جوالك، فالأرقام لا تُقارن بين جهازين. |
| يتأثر بالبرامج الأخرى | تحديث يعمل في الخلفية يبطئ القياس. |
| يحتاج كتابة الكود أولًا | لا تقيس فكرة قبل تنفيذها. |
| لا يغطي كل المدخلات | جربت 1000 عنصر، فماذا عن مليار؟ |
لذلك نحتاج طريقة نظرية مستقلة عن الجهاز: نعدّ عدد العمليات كدالة في حجم المدخل n. وهذا موضوع الوحدة القادمة.
توقّع وتحقّق
الدالة الأدق لقياس فترة زمنية قصيرة:
مضاعفة n في خوارزمية «كل زوج» تضاعف الزمن نحو:
n² ← (2n)² = 4n².أيها يحجز ذاكرة أقل لمليون رقم؟
لماذا نحتاج التحليل النظري؟
الخلاصة
- الكفاءة: الزمن والذاكرة، وبينهما مقايضة.
perf_counterقبل العمل وبعده، وtimeitللتكرار والدقة.- المهم نمط النمو: هل يتضاعف الزمن أم يتضاعف أربع مرات؟
getsizeofحجم كائن، وtracemallocكل ما يحجزه البرنامج.- القياس يعتمد على الجهاز؛ لذلك نعدّ العمليات نظريًّا.
تحدٍّ برمجي: عدّ العمليات بدل الساعة
متوسطبدل قياس الزمن، عدّ عمليات المقارنة في دالة «كل زوج» لأحجام مختلفة، ولاحظ النسبة حين يتضاعف n.
- دالة
count_pairs(n)تُرجع عدد مرات تنفيذ المقارنةx < yلقائمة من n عنصرًا. - اطبع لكل n من 10 و 20 و
40: nثم العدد. - اطبع في الأخير نسبة العدد عند 40 إلى العدد عند 20: النسبة: 4.0
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
def count_pairs(n): a = list(range(n)) count = 0 # أكمل return count
💡 تلميح 1
count += 1💡 تلميح 2
n × nحاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
def count_pairs(n): a = list(range(n)) count = 0 for x in a: for y in a: count += 1 return count for n in [10, 20, 40]: print(n, count_pairs(n))print("النسبة:", count_pairs(40) / count_pairs(20))