المنهج الدراسي الدرس 77 من 148 · حدود فردية
حدود فردية

ذاكرة ثابتة

لماذا هذا مهم "عد عدد مرات حدوث كل شيء" هو قاموس، حتى يصبح عدد الأشياء غير محدود والذاكرة محدودة. العد التقريبي بحد مضمون غالبا ما يكون ذا قيمة أكبر بكثير من العد الدقيق الذي لا يمكنك تحمله.

يقوم

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

Sketch: ملخص بحجم ثابت لتدفق بيانات يجيب على الأسئلة بشكل تقريبي، مع حد خطأ معروف. على سبيل المثال، يحتفظ count-min sketch ببضع صفوف من العدادات ويقوم بعمل hash لكل عنصر إلى عداد واحد في كل صف؛ وأصغر تلك العدادات لا يقل أبدا عن العدد الحقيقي.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
دورك

اكتب class ApproxCounter باستخدام add(item) (العناصر هي strings) و estimate(item) (عدد صحيح).

Limits. بعد 30,000 حدث من ما يصل إلى 10,000 مستخدم مختلف، قد يحمل العداد 3,500 عنصراً كحد أقصى (kept() على العداد). يجب ألا تكون التقديرات أبداً أقل من العدد الحقيقي، ولـ 95% على الأقل من المستخدمين (بما في ذلك المستخدمين الذين لم يسبق رؤيتهم) يجب أن تكون كحد أقصى العدد الحقيقي زائد 300 (1% من الأحداث). يجب أن تكون النتائج قابلة للتكرار في كل تشغيل وجهاز: لا تستخدم hash() (فهو يتغير في كل تشغيل) أو أرقاماً عشوائية؛ zlib.crc32 أو hashlib ببذور ثابتة هي خيارات جيدة.

هل لاحظت مشكلة في هذا الدرس؟ أبلغ عنها · اسأل عن هذا الدرس

سيفتح هذا التمرين قريبا

أنهِ الدرس السابق ليفتح هذا الدرس. الدورة كاملة مجانية، ولا تحتاج إلى حساب، ويمكنك قراءة هذا الدرس الآن.