고성능 파이썬 Chapter 11 - RAM 덜 사용하기

들어가며

해당 챕터는 다양한 자료구조를 통해 메모리를 적게 사용하는 방법을 알려준다. 특히 문자열을 저장하고, count 하는 방식에 대해서 알려준다.  특히 정확도를 약간 희생해서 RAM 사용량을 줄였다는 점에서 count 알고리즘이 흥미로웠다. 해당 알고리즘을 어떤 때 사용해야 하는지도 관심 있게 보면 좋을 것 같다.

---

이 장에서 배울 내용

- RAM을 덜 사용해야 하는 이유.

- 원시 타입의 수를 많이 저장하는 데 numpy와 array가 더 좋은 이유

- 많은 텍스트 정보를 RAM에 효율적으로 저장하는 방법

- 1바이트로 1076(대략적으로!)을 세는 방법

- 블룸(Bloom) 필터의 정의와 이 필터가 필요한 이유

---

 

list 대신 numpy, array를 사용하여 RAM 사용량 줄이기

 

RAM에 많은 텍스트를 효율적으로 저장하기

단순히 문자열을 저장하려면 list를 이용하거나, set을 이용하여 저장할 수 있다. 
하지만, 이런 방식은 후술할 TRIE와 DWAG에 비하여 메모리 사용량이 높고, 경우에 따라 검색 시간도 늦어질 수 있다.

만약 list를 사용해야 한다면 정렬을 하여 이진탐색을 하는 것을 추천한다. 

set은 hash table을 이용하기 때문에 검색 시간이 매우 빠르다. 하지만 list보다 약간 더 많은 메모리를 사용한다.

 

TRIE : 문자열이 공통 접두사를 공유하는 형태이다. (자동 완성 등에서 사용된다.)

DAWG : TRIE와 비교하여 공통 접미사도 공유한다.

문자열에서 겹치는 부분이 많을수록 TRIE, DAWG에서 더 많이 데이터가 압축 될 것이다. 

geocoding 예제와 함께 Trie 를 이용한 서비스를 확인하자. 영국 우편번호 데이터베이스를 저장하는데 30MB만을 사용한다고 한다.

 

DictVectorizer와 FeatureHasher를 이용해서 token 단위로 나눈 문자열을 희소 행렬로 표현할 수 있다. 

 

정확도를 희생해서 수를 대략적으로 세는 방법

morris counter - RAM이 제한된 환경에서 객체 갯수 세기, 대용량 스트림 데이터 이해, 이미지 및 음성 인식기 AI 등의 환경에서 사용될 수 있다고 한다.

gpt에 물어본 음성인식에서의 적용 예

 

morriscounter.py

log scale로 줄어드는 확률값에 의거하여 count를 하는 방식이다.

 

K-minimum-value (KMV)를 이용하면 hash 함수의 특징을 이용하여 유일한 값을 count할 수 있다.

 

kminvalues.py

 

 

bloomfilter.py

블룸필터는 이전에 이 원소를 본 적이 있는지에 대한 질문에 답변하기 위해 생겼다. 여러 hash 알고리즘을 이용해 원소를 hash-table에 저장하고, 이전에 이 값이 나왔다면, 모든 hash table에 저장되었을 것이고, 그렇지 않다면 저장되지 않았을 것을 기반으로 작성되었다. 

해당 방법은 false-positive의 가능성은 0이고, false-positive일 가능성의 비율은 hash function을 이용하여 조절할 수 있다. 

 

ll.py

LogLog counter는 해시의 개별 bit을 난수처럼 생각해서 output에 계속 0이다가 처음으로 1이 나오게 한다면, 얼마나 많은 값을 hash 화 했는지 카운트 하는 방식으로 추정할 수 있는 방법이다.