سرفصل‌ها درس 77 از 148 · محدودیت‌های عجیبی
محدودیت‌های عجیبی

حافظه ثابت

چرا اهمیت دارد: «شمارش اینکه هر چیز چند بار اتفاق می‌افتد» یک فرهنگ لغت است، تا زمانی که تعداد موارد نامحدود باشد و حافظه محدود. یک شمارش تقریبی با حد تضمین‌شده اغلب بسیار ارزشمندتر از یک شمارش دقیق است که توان آن را ندارید.

یک دروازهٔ API کاربران پرمصرف را علامت‌گذاری می‌کند. این دروازه همهٔ درخواست‌ها را می‌بیند، می‌تواند هر تعداد کاربر داشته باشد و هر فرآیند دروازه برای این کار یک برش ثابت حافظه دریافت می‌کند. این پرچم فقط یک هشدار برای بررسی توسط انسان است، بنابراین کمی بیش‌شماری اشکالی ندارد؛ اما کم‌شماری می‌تواند یک کاربر پرمصرف را پنهان کند و به همین دلیل قابل قبول نیست.

اسکیچ: خلاصه‌ای با اندازه ثابت از یک جریان که به صورت تقریبی به سؤالات پاسخ می‌دهد و دارای یک حد خطای شناخته‌شده است. برای مثال، یک اسکیچ count-min، چند سطر از شمارنده‌ها را نگه می‌دارد و هر آیتم را به یک شمارنده در هر سطر هش می‌کند؛ کوچکترین عدد از آن شمارنده‌ها هرگز کمتر از تعداد واقعی نخواهد بود.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
نوبت شما

نوشتن class ApproxCounter با add(item) (مقادیر رشته‌ای هستند) و estimate(item) (یک عدد صحیح).

محدودیت‌ها. پس از ۳۰٬۰۰۰ رویداد از حداکثر ۱۰٬۰۰۰ کاربر مختلف، شمارنده می‌تواند حداکثر ۳٬۵۰۰ آیتم را در خود نگه دارد (kept() روی شمارنده). برآوردها هرگز نباید کمتر از شمارش واقعی باشند، و برای حداقل ۹۵٪ از کاربران (از جمله کاربرانی که هرگز دیده نشده‌اند) باید حداکثر برابر با شمارش واقعی به‌علاوهٔ ۳۰۰ (۱٪ از رویدادها) باشند. نتایج باید در هر اجرا و دستگاه قابل تکرار باشند: از hash() (در هر اجرا تغییر می‌کند) یا اعداد تصادفی؛ zlib.crc32 یا hashlib با بذرهای ثابت مشکلی ندارد.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.