매우 큰 데이터 세트로 작업하고 있습니다. 필자는 본질적으로 수백만 개의 레코드로 작업하고 값을 데이터 세트에 저장합니다.효율성 : 어떤 데이터 구조를 사용해야합니까?
값을 저장할 때마다 먼저 값이 데이터 구조에 없는지 확인해야합니다. 값이 데이터 구조에 있으면 레코드를 업데이트 (또는 제거/추가)하여 개수를 업데이트해야합니다.
데이터 집합 내에 반복이 있으며, 나쁜 데이터 구조를 사용하고 O (n) 속도를 얻고 싶지 않습니다.이 작업을 밤새 실행할 수 있기를 원합니다. 그것을 끝내는 아침!
어떤 조언이 필요합니까?
다른 사람은, 해시 테이블이 아마이 정답, 하지만 해시 테이블이 정말 공간이 효율적이지, 그래서 당신이 지점에 도착하면 어디있을 수 있습니다 말했듯이 기억을 다 써 버리면 정렬 된 키 배열과 병렬 정렬 된 값 배열을 고려해야합니다. 기본적으로 전체 키 목록에 액세스 할 수 있다면이 배열을 만들어 정렬 할 수 있습니다. 그런 다음 값의 병렬 배열을 만듭니다. 매번 어떤 것을 저장할 필요가있을 때마다, 키 배열에서 인덱스를 찾기 위해 바이너리 검색 (O (log N))을 수행 한 다음 값 배열에서 해당 인덱스를 업데이트하십시오. 이것은 해시 테이블보다 속도가 빠르지 만 사실상 공간 오버 헤드는 없습니다.
hash table이 목록 또는 일부 특정 구조와 결합 된 것처럼 보입니다. 저에게, 그것은 database 같이 소리가 난다.
를 사용하여 해시 테이블
이진 트리를 사용해 볼 수 있습니다. log_2 (1,000,000)는 약 20입니다. 모든 키를 미리 알지 못하는 경우 더 좋을 수 있습니다.
플랫폼 및 언어는 무엇입니까? 균형 잡힌 나무와 같은 일부 솔루션은 작성하기가 어색하지만 라이브러리에 있으면 훌륭하게 작동 할 수 있습니다. –