tries
1.0.0
이 클래스는 트리 기반 컨테이너를 구성하는 기초를 제공합니다.
기본 형식에서 Ttrie 클래스는 16, 32 및 64 비트 기반 데이터 요소를 저장하는 데 사용될 수 있습니다.
이 구조는 고정 된 깊이 트리 구현을 제공하여 노드를 찾고 제거 및 추가 할 수 있도록 동일 시간을 동일하게 만듭니다.
구조의 순서는 O (d)입니다. 여기서 D는 트리의 깊이인데, 이는 16, 32 또는 64 비트 값을 저장하도록 구성되어 있는지에 따라 다릅니다. 16 비트 D = 4의 경우 32 비트 d = 8, 64 비트 d = 16의 경우
노드 크기를 작게 유지하려면 노드 당 16 개의 분기 만 사용되며 표시기 플래그와 내부 포인터 인덱스는 16 비트 단어와 64 비트 정수로 인코딩됩니다.
지점에 대한 포인터는 동적으로 관리되므로 새 지점을 추가해야 할 때 포인터 배열에 포인터 만 할당되므로 사전에 할당 된 포인터 배열의 하위 레벨 분기에 대한 폐기물을 최소화합니다. 그러나 둔화 될 것입니다.
Leafs는 마지막 분기 노드에 의해 개별 노드가 아닌 곳에서 할당됩니다.
마지막으로, 잎 노드는 ttrie의 파생 클래스에 의해 동적으로 제어 될 수있어 ttrie를 기본으로 사용하여 사전을 쉽게 구현할 수 있습니다.
Mac에 Lazarus (Freepascal) 할당으로 할당 된 메모리를 저장하는 일부 테스트를 수행하면 저장된 물체의 크기에 비례하여 약 40%의 저장 효율을 렌더링합니다.
이 클래스는 또한 제거 된 많은 제거가 발행되었을 때 저장을 유지하는 데 사용되는 팩 방법을 제공합니다.
Tintegerhashtrie와 Tstringhashtrie는 Thashtrie Generic Class의 후손으로 제공됩니다. Thashtrie에는 두 가지 운영 모드가 있습니다.
Hash 테이블은 물론 더 나은 성능을 제공하지만 Hashtrie는 적은 수의 요소를 저장할 때 더 효율적인 메모리 발자국을 가지고 있습니다.
델파이의 tdictionary <> 및 c# 사전 <> 클래스에 대해 tstringhashtrie를 테스트했습니다.
TStringhashtrie는 C# 및 Delphi 구현을 모두 이겼습니다. 루트 노드에 사용 된 해시 테이블은 차이가 더 큽니다.
큰 부하의 메모리 풋 프린트는 30% -40% 더 우수합니다. 해시 테이블 루트 노드가 아닌 순수한 해시 트리를 사용하는 소수의 요소의 경우 메모리가 크게 줄어 듭니다.
Delphi 2007에서 컴파일 된 테스트는 구조에 삽입하기 전에 문자열이 UTF16에서 ANSI로 변환 할 필요가 없기 때문에 더 나은 결과를 얻었습니다.
TStringhashtrie는 UTF8 양식의 유니 코드를 지원합니다.
