강의 계획 레슨 148개 중 77번째 · 이상한 제약
이상한 제약

고정 메모리

왜 중요한가 "각각이 얼마나 자주 일어나는지 세라"는 딕셔너리예요. 것들의 수는 한이 없고 메모리는 그렇지 않기 전까지는요. 보장된 한계가 있는 근사 개수는 감당할 수 없는 정확한 개수보다 흔히 훨씬 가치가 있어요.

API 게이트웨이가 많이 쓰는 사용자를 표시해요. 모든 요청을 보고, 사용자는 몇 명이든 될 수 있고, 각 게이트웨이 프로세스는 이 일에 고정된 메모리 조각을 받아요. 표시는 사람이 보도록 하는 신호일 뿐이니, 작은 과다 계산은 괜찮아요. 과소 계산은 많이 쓰는 사용자를 숨길 수 있으니, 안 돼요.

스케치: 알려진 오차 한계와 함께 질문에 근사로 답하는 스트림의 고정 크기 요약. 예를 들어 count-min 스케치는 카운터 행 몇 개를 지니고 각 항목을 행마다 카운터 하나로 해시해요. 그 카운터 중 가장 작은 것은 결코 참 개수 아래가 아니에요.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
내 차례

add(item)(항목은 문자열)과 estimate(item)(정수)이 있는 class ApproxCounter를 쓰세요.

제약. 최대 10,000명의 서로 다른 사용자에게서 온 이벤트 30,000개 뒤, 카운터는 최대 3,500개 항목을 지닐 수 있어요(카운터에 kept()). 추정치는 결코 참 개수 아래이면 안 되고, 사용자의 적어도 95%(본 적 없는 사용자 포함)에 대해 최대 참 개수 더하기 300(이벤트의 1%)이어야 해요. 결과는 모든 실행과 기기에서 되풀이할 수 있어야 해요: hash()(실행마다 바뀌어요)나 무작위 숫자를 쓰지 마세요. 고정 시드의 zlib.crc32나 hashlib는 괜찮아요.

이 레슨에서 문제를 발견했나요? 알려 주세요 · 이 레슨에 대해 묻기

이 연습은 곧 열려요

앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.