나는 최대 63 자 길이의 100 개 이상의 문자열을 가지고 있습니다. 디스크 공간이 많고 메모리가 거의 없습니다 (512MB). 혼자 존재 여부를 쿼리하고 추가 메타 데이터를 저장하지 않아도됩니다.문자열의 큰 집합에 존재를 확인하는 효율적인 방법
사실상 솔루션은 BDB btree입니다. 어떤 대안이 있습니까? 저는 leveldb와 Kyoto Cabinet에 대해 알고 있습니다 만, 장점을 확인하기에는 익숙하지 않습니다.
가양 성이 허용되는 경우 가능한 해결책은 bloom filter을 사용하는 것입니다. Bloom 필터는 해시 테이블과 비슷하지만 하나의 해시 값을 사용하여 버킷 테이블을 인덱싱하는 대신 여러 해시를 사용하여 비트 배열을 인덱싱합니다. 이러한 인덱스에 해당하는 비트가 설정됩니다. 그런 다음 문자열이 필터에 있는지 테스트하려면 문자열이 다시 해시되고 해당 색인이 설정된 경우 문자열은 필터의 "in"입니다.
문자열에 대한 정보를 저장하지 않으므로 메모리가 거의 사용되지 않지만 두 문자열 사이에 충돌이 있으면 충돌 해결이 불가능합니다. 즉, 필터에없는 문자열이 필터에있는 문자열과 동일한 색인에 해시 될 수 있기 때문에 오탐 (false positive)이 발생할 수 있습니다. 그러나 위양성이 없어야합니다. 실제로 세트에있는 문자열은 블룸 필터에서 찾을 수 있습니다.
fewPythonimplementations이 있습니다. 당신 자신의 것을 굴리는 것도 어렵지 않습니다. 나는 한 번 정확하게 을 사용하여 quick-and-dirty bloom filter를 코딩하는 것을 회상했다.
디스크가 많다고 했습니까? 한 가지 옵션은 문자열을 중첩 된 서브 디렉토리에 파일 이름으로 저장하는 것입니다. 직접 문자열을 사용할 수 있습니다 중 하나
d/r/e/w/ sears또는 유사한 과정 문자열의 해시를 복용하고 다음으로 "시어스을 받았다"
f0/10/fe/6e/20d12ed895c10b93b2f81c6e이라는 빈 파일을 만듭니다.OS 최적화 된 해시 테이블 기반의 NoSQL 데이터베이스로 생각하십시오.
사이드 혜택 :
이독창성을 위해서는 +1하지만 OS를 사용하여 깊이 중첩 된 파일의 존재 여부를 확인하는 속도가 느려질 수 있습니다. – martineau
사실 이제는 더 생각해 보았습니다. 왜 중첩 된 서브 디렉토리가 있습니까? 대신 각 문자열에 대해 빈 파일을 만들고이 파일을 모두 단일 디렉토리에 저장하십시오. 물론 파일 시스템 문제가있을 수 있습니다 ... – martineau
테스트가 없으면 속도가 느려지는지 확실하지 않습니다. 그것은 실제로 파일 시스템에 따라 꽤 분열 될 수 있습니다. 많은 파일 시스템이 더 작은 디렉토리에서 훨씬 빠르며 대부분의 (모든?) 현대 FS는 디렉토리 조회를 잘 캐시합니다. 그것이 중첩 된 하위 디렉토리에 대한 동기였습니다. –
때때로 가양 성을 견딜 수 있습니까? – senderle
위조 방지 기능을 사용할 수 없습니다. 때때로 가양 성 (false positive)은 잠재적으로 용인 될 수 있습니다. –
그냥'set' 안에 그것들을 모두 저장하고 OS의 가상 메모리 관리자가 필요에 따라 디스크를 페이지하도록합니다. 'pickle'을 사용하여 디스크에 명시 적으로 저장할 수도 있습니다. 데이터베이스를 작성할 필요가 없습니다. – martineau