決まったメモリ
なぜ大切か 「それぞれのものがどれだけよく起こるかを数える」は、ものの数に限りがなく、メモリに限りがあるまでは辞書です。保証された範囲を持つ近似の数は、払えない正確な数よりずっと価値があることがよくあります。
API のゲートウェイが、重いユーザーに印を付けます。すべてのリクエストを見て、ユーザーはいくらでもいることがあり、それぞれのゲートウェイのプロセスはこの仕事のために決まった分のメモリをもらいます。印は人が見るためのきっかけにすぎないので、少しの数えすぎは構いません。数え足りないと重いユーザーを隠しかねないので、それはだめです。
スケッチ:ストリームの決まった大きさのまとめで、知られた誤差の範囲で、問いに近似で答えます。例えば count-min スケッチは、カウンターの行をいくつか持ち、それぞれの項目を行ごとにひとつのカウンターへハッシュします。そのカウンターの最小は、決して真の数を下回りません。
import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width # same on every runadd(item)(項目は文字列)と estimate(item)(整数)を持つ class ApproxCounter を書いてください。
制限。最大 10,000 の違うユーザーからの 30,000 のイベントのあと、カウンターが持てるのは最大 3,500 の項目です(カウンターへの kept())。推定は決して真の数を下回ってはならず、少なくとも 95% のユーザー(一度も見ていないユーザーも含む)について、最大で真の数足す 300(イベントの 1%)でなければなりません。結果は、どの実行でもどの端末でも繰り返せなければなりません。hash()(実行ごとに変わる)も乱数も使わないでください。決まったシードの zlib.crc32 や hashlib は構いません。
この演習はまもなく開きます
その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。
このブラウザは learn.floati.life の Cookie をブロックしているため、ここで修了したレッスンを順番どおりに開けません。このサイトの Cookie を許可して再読み込みしてください。