पाठ्यक्रम 148 में से पाठ 77 · अजीब सीमाएँ
अजीब सीमाएँ

तय memory

यह क्यों मायने रखता है "गिनो कि हर चीज़ कितनी बार होती है" एक dictionary है, जब तक चीज़ों की संख्या असीमित न हो और memory न हो। एक गारंटीशुदा सीमा वाली अनुमानित गिनती अक्सर उस ठीक गिनती से कहीं ज़्यादा क़ीमती है जिसका ख़र्च आप नहीं उठा सकते।

एक API gateway भारी उपयोगकर्ताओं को चिह्नित करता है। यह हर request देखता है, कितने भी उपयोगकर्ता हो सकते हैं, और हर gateway process को इस काम के लिए memory का एक तय टुकड़ा मिलता है। Flag बस एक इंसान को देखने का संकेत है, इसलिए थोड़ी ज़्यादा गिनती ठीक है; एक कम गिनती एक भारी उपयोगकर्ता को छिपा सकती है, इसलिए वह नहीं।

Sketch: एक stream का एक तय-आकार सार जो एक जानी त्रुटि सीमा के साथ सवालों के अनुमानित जवाब देता है। एक count-min sketch, उदाहरण के लिए, counters की कुछ rows रखता है और हर item को हर row में एक counter पर hash करता है; उन counters में सबसे छोटा कभी सच्ची गिनती से नीचे नहीं होता।

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
आपकी बारी

add(item) (items strings हैं) और estimate(item) (एक पूर्ण संख्या) के साथ class ApproxCounter लिखें।

सीमाएँ। 10,000 तक अलग उपयोगकर्ताओं के 30,000 events के बाद, counter ज़्यादा से ज़्यादा 3,500 items रख सकता है (counter पर kept())। अनुमान कभी सच्ची गिनती से नीचे नहीं होने चाहिए, और कम से कम 95% उपयोगकर्ताओं के लिए (कभी न देखे उपयोगकर्ताओं समेत) ज़्यादा से ज़्यादा सच्ची गिनती और 300 (events का 1%) होने चाहिए। नतीजे हर run और device पर दोहराने लायक होने चाहिए: hash() (यह हर run पर बदलता है) या बेतरतीब संख्याएँ इस्तेमाल न करें; तय seeds के साथ zlib.crc32 या hashlib ठीक हैं।

इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें

यह अभ्यास जल्द खुलेगा

इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।