트리와 사전의 합리적인 크기

Question

현재 요청마다 재 처리하는 대신 즉각적인 데이터 액세스가 가능하도록 매우 복잡한 트리 구조를 구현 중입니다.

트리의 크기가 너무 커지거나 이론적이거나 실용적인 제한이 있는지, 또는 사전이 너무 복잡해져 정확하게/빠르게 작동하지 않는 지점이 있는지 궁금합니다.

일반적인 대답은 좋지만 C# 관련 정보가 훨씬 더 좋을 것입니다!

Answer 1

.NET에서 트리 또는 사전의 최대 값은 2^31 - 1 (오버 헤드의 경우는 적지 만)입니다.

실용적인면에서 오래 전에 메모리가 부족한 것 같습니다.

트리가 균형을 유지하면 검색은 대략 그대로 유지됩니다. O (로그 N).

사전은 사용 된 기본 알고리즘에 더 민감합니다. 예를 들어 특성이 다른 해싱 스키마가 많습니다.

Answer 2

많은 양으로 고려하십시오. 수백 또는 수천은 괜찮을 것이지만, 수백만 달러는 전문적인 것을 찾는 가치가있을 수 있습니다.

스토리지 기술과 재조정에 따라 트리가 커질수록 속도가 느려집니다.

사전은 상당히 일관성이 있어야하지만 저장할 가능성이있는 데이터의 양 (아마도 x2는 안전함)에 적합한 크기로 사전을 구성해야합니다.

Answer 3

는 this question보기 - 그것은 처음에는에 대답 중 하나입니다 그래서 :

문제는 약 90 만 항목 사전을 구축 성능 저하이었다. 나는 10 분에서 0.34 초까지 시간을 줄였습니다.

사전은 해시 함수만큼 좋으며, 고유 해시를 빠르게 생성 할 수 있다면 번개처럼 실행됩니다. 이 도움이

희망,

편집 :

비교 클래스는 중요하지 않습니다, .NET 문자열이 매우 강력한 해시 함수를 가지고 - 때문에 - 사전에 우수한 성능을 가지고있다. 그 녀석 문제는 문자열 쌍 대신에 단일 문자열을 사용했다면 "사라 졌을"것입니다.