이 상황에 적합한 데이터 구조는 무엇입니까?
-
19-09-2019 - |
문제
필요한 기능 만
- 삽입
- 조회
구체적으로, 쌍을 삭제하거나 키/값/쌍을 반복 할 필요가 없습니다.
키는 정수 튜플이고 값은 포인터입니다 (참조, 무엇이든). 나는 (많은) 물체 위에 퍼져있는 2 백만 쌍 만 저장하고 있습니다.
현재 어느 쪽이든 사용하는 것을 고려하고 있습니다
- 해시 테이블
- KD-Tree
- B- 트리
나는 해시 테이블에 기대고있다 ( O(1)
삽입/조회 시간),하지만 내 기대를 확인하고 싶었습니다.
위의 또는 다른 구조 중 어떤 구조를 추천 하시겠습니까? 해시 테이블을 권장하는 경우 각 객체에 대해 별도의 테이블을 만들거나 단일 테이블을 만들고 키 튜플의 일부로 객체의 ID를 사용해야합니까?
해결책
귀하에게 중요한 모든 작업이 O (1)이므로 해시 가능이 가장 좋은 선택이 될 것입니다 (따라서 여러 해시블 생성에 대해 걱정할 필요가 없습니다).
다른 팁
나는 해시 테이블의 열렬한 팬입니다. 쉽고 거의 모든 주요 언어에 사용할 수있는 구현이 있기 때문입니다. O (1) 삽입/조회는 특히 좋은 기능입니다.
메모리를 저장하려면 단일 테이블을 사용해야합니다. 해시 테이블은 비효율적 인 메모리가 비효율적이며 단일 테이블을 사용하면이를 최소화하는 데 도움이됩니다.
해시 테이블은 여기에 유용 할 것이며 둘 이상의 테이블을 가질 이유가 없습니다.
대부분의 나무에는 O (n ln n) 조회 시간이 있지만 해시블은 O (1) 조회 시간이 있으므로 사용하고 싶은 것입니다. 또한 매우 일반적이며 구현은 종종 부팅하기에 최적화됩니다.
제휴하지 않습니다 StackOverflow