고성능 파이썬(2판)

463

11

장

RAM 덜 사용하기

11.9.4

로그로그 카운터

로그로그

LogLog

유형의 카운터(

http

://

bit

.

ly

/

LL

-

type

_

counters

)는 해시 함수의 개별

Bit

를 난수처럼 생각할 수 있다는 깨달음에서 비롯되었다. 즉 해시의 첫 번째

Bit

가

1

일 확률은

50

%이고, 처음 두

Bit

가

01

일 확률은

25

%이며, 처음 세

Bit

가

001

일 확률은

12

.

5

%이다. 이런

확률을 알고

0

이 가장 많은 해시 (즉, 발생할 확률이 가장 낮은 해시값)를 시작 부분에 위치시

킨다면 지금까지 얼마나 많은 원소를 살펴봤는지 추정할 수 있다.

이 방법은 동전 던지기에 비유하면 쉽게 이해가 된다. 동전을

32

번 던지면서 계속 앞면만 얻고

싶다고 하자. 우리가

32Bit

해시 함수를 사용하므로

32

라는 수를 선택했다. 만약 동전을 한 번

뒤집어서 뒷면이 나왔다면, 지금까지 연속으로 앞면이 나온 횟수가

0

번이니

0

이라는 수를 저

장할 것이다. 우리는 동전 던지기의 확률을 이미 알기에 앞면이 연속으로 가장 길게 나왔던 횟

수가

0

이라는 사실에서 이 실험을

2

^

0

=

1

회 실행했다고 추측할 수 있다. 동전을 계속 던지다

보면 뒷면이 나오기 전에 연속으로 앞면이

10

번 나타나는 상황이 나와서

10

이라는 수를 저장

할 것이다. 앞에서와 마찬가지의 논리를 사용하면 우리가 ...