수백만 개의 문자열이 있다고 가정합니다. 각 문자열은 int 값을가집니다. 이 값을 입력 문자열로 검색하고 싶지만 많은 공간을 차지하기 때문에이 문자열을 모두 저장하고 싶지 않습니다. 메모리에 모든 문자열 또는 적어도 많은 문자열을 저장해야하기 때문에 해시 테이블을 사용할 수 없습니다. 그래서 내 경우에 대한 좋은 데이터 구조는 무엇입니까 (나는 어떤 문자열을 추가하거나 삭제할 필요가 없습니다. 이미 데이터를 준비하고 읽기만 허용됩니다)문자열을 저장하는 메모리 효율적인 방법
해시 테이블을 사용하지 않는 이유는 아닙니다. 현재 귀하의 질문에 제한된 정보를 기반으로 유효한 소리. 잘 구현하면 상당히 효율적입니다. 또한 필요에 따라 허용되는 경우 중복 문자열을 저장하는 메모리를 낭비하지 않아도되므로 중복 문자열이 가능하면 메모리 소비를 줄이는 이점이 있습니다.
조회 수행 방법에 대해 창의적이라면 해시 테이블에 각 문자열의 압축 된 형식을 저장할 수도 있습니다. 문자열은 일반적으로 얼마나 걸립니까?
평균 길이는 10 자입니다. 적어도 해시 테이블의 항목 버킷 하나를 사용하여 문자열을 저장할 수는 없습니다. 그래서 나는이 접근법을 발전시키는 방법이 존재한다고 생각합니다. – Neir0
당신은 문자열 키 위해 설계된 버전을 빠르고 컴팩트 둘 수 있도록 설계하고, 가지고있는 Judy tree,보고 할 수 있습니다. 해당 구현은 sourceforge에서 사용할 수 있습니다.
단어 목록을 사전 처리 할 수있는 경우 CMPH과 같은 완벽한 해시를 살펴보세요. (gperf 다른이지만 작은 데이터 세트에 대해 최적화 같다.)을 CMPH 워드 프로세서에서
:
완벽 해시 함수가 충돌없이 m 정수 숫자 세트에 해당 키의 정적 세트를 매핑 여기서 m은 n보다 크거나 같습니다. m이 n과 같으면이 함수는 minimal이라고합니다.
은 ...
CMPH 도서관은 사용하기 쉬운, 생산 품질, 빠른 API의 최신 및보다 효율적인 알고리즘을 캡슐화합니다. 이 라이브러리는 주 메모리에 들어 가지 않는 큰 항목을 처리하도록 설계되었습니다. 그것은 1 억 개 이상의 키가있는 세트에 대해 최소한의 완벽한 해시 함수를 생성하는 데 성공적으로 사용되었습니다 ...
어떤 프로그래밍 언어를 사용합니까? 또한 동일한 문자열이 많이 있습니까? –
@ jdv-Jan de Vaan 모든 문자열이 고유하지는 않습니다. 나는 특정 질문 언어를 생각하지 않지만 나는 C#을 선호한다고 생각하지 않는다. – Neir0
당신이해야 할 일이 불분명합니다. 그 번호를 추출하고 다른 파일에 저장하면됩니까? 또는 이들과 함께 계산을 수행해야합니까? 입력 순서가 보존되지 않았습니까? –