큰 목록을 계산하는 방법

Question

해시의 다양한 스키마에 대한 충돌을 계산해야한다고 가정합니다. 입력 시퀀스의 요소 수는 1e10^8 이상입니다. 분석적으로 계산하는 방법을 모르기 때문에 무차별 대항력을 사용하십시오.

이 해시 목록을 RAM에 보관하지 않는 것이 분명합니다. 내 필요에 맞는 코드를 작성하는 가장 좋은 방법은 무엇입니까? 데이터베이스에 덤프해야합니까? 어떤 라이브러리가 선호됩니까?

감사합니다.

Answer 1

각 파일의 해시 접두사로 이름이 지정된 파일 집합을 유지하는 것이 좋습니다 (예 : 접두어 길이 6을 사용하는 경우 ffa23b.txt 파일에 해시가 포함될 수 있음) ffa23b11d4334, ffa23b712f3, 등). 해시를 읽을 때마다 해시의 처음 N 자에 해당하는 이름으로 파일에 추가합니다.

을 사용하여 모든 해시를 메모리에 저장하지 않고도 많은 양의 해시를 신속하게 배제 할 수 있습니다. 그렇게하면 블룸 필터에 대한 검사에서 이전에 실제로 보았을 수도 있다고 말하면 주어진 접두사 파일을 검색하는 것만으로 돌아갈 수 있습니다.

Answer 2

짧은 대답 : 약간의 기가 바이트 RAM이있는 경우 Python 사전을 사용하면 구현이 가장 쉽고 (실행 속도가 빠릅니다).

>>> mydict = {} 
>>> for i in some_iterator: 
     mydict[i] = '' 

을 그리고 키 매핑에있는 경우 다음 확인하십시오 : 당신은 이런 식으로 뭔가를 할 수

>>> 0 in mydict 
True 

>>> 123456789 in mydict 
False 

긴 대답 : 당신은 (GDBM 같은 영구적 인 키 - 값 저장소를 사용할 수 있습니다 그것은 Berkeley DB처럼 보일 것입니다.) 또 다른 종류의 데이터베이스입니다 - 그러나이 접근법은 way입니다. 단지 파이썬 사전을 사용하는 것보다 느립니다. 반면에이 방법을 사용하면 지속성을 얻을 수 있습니다 (필요한 경우).

GDBM은 하나의 파일에 유지되는 사전 (키 - 값 저장소)으로 이해할 수 있습니다. 다음과 같이 사용할 수 있습니다 : 그런 다음 파일 my.db이 생성됩니다

>>> import gdbm 
>>> kv = gdbm.open('my.db', 'cf') 

( Python GDBM documentation를 보는 것을 cf 방법을 이해하기).

하지만 키와 값으로 만 문자열을 지원하는 것으로, 몇 가지 제한 사항이 있습니다 :

>>> for i in some_iterator: 
     kv[str(i)] = '' 

: 그리고 당신은 모든 키가 더미 값을 갖는으로 GDBM 데이터베이스를 채울 수 있습니다

>>> kv[0] = 0 
Traceback (most recent call last) 
[...] 
TypeError: gdbm mappings have string indices only 

>>> kv['0'] = 0 
Traceback (most recent call last) 
[...] 
TypeError: gdbm mappings have string elements only 

>>> kv['0'] = '0' 

해당 키가 매핑에 있는지 확인하십시오.

>>> '0' in kv 
True 

>>> '123456789' in kv 
False