해시 테이블과 트리 (접두사 트리) 중에서 어떻게 선택합니까?

https://stackoverflow.com/questions/245878

05-07-2019
|

문제

해시 테이블이나 접두사 트리 중에서 선택해야한다면 다른 하나를 선택하게하는 차별 요인은 무엇입니까? 내 자신의 순진한 관점에서 트리를 사용하는 것은 배열로 저장되지 않지만 런타임 (가장 긴 키가 가장 긴 영어 단어라고 가정함에 따라)이 기본적으로 O가 될 수 있기 때문에 여분의 오버 헤드가있는 것처럼 보입니다. (1) (상한과 관련하여). 아마도 가장 긴 영어 단어는 50 자입니까?

해시 테이블이 즉시 조회됩니다 인덱스를 얻으면. 그러나 인덱스를 얻기 위해 키를 해싱하는 것은 쉽게 50 단계가 걸릴 수있는 것처럼 보입니다.

누군가 나에게 이것에 대한 경험이 많은 관점을 제공 할 수 있습니까? 감사!

해결책

시도의 장점 :

기본 사항 :

예측 가능한 o (k) k) 키 크기 인 조회 시간
조회가 없으면 k 시간 미만이 걸릴 수 있습니다.
순서 대상 트래버스를 지원합니다
해시 기능이 필요하지 않습니다
삭제는 간단합니다

새로운 운영 :

키의 접두사를 신속하게 찾아 주어진 접두사 등으로 모든 항목을 열거 할 수 있습니다.

연결된 구조의 장점 :

일반적인 접두사가 많이있는 경우 필요한 공간이 공유됩니다.
불변의 시도는 구조를 공유 할 수 있습니다. 트리를 제자리에 업데이트하는 대신 하나의 지점을 따라 다른 곳에서만 다른 곳에서 구식 트리를 가리키는 새로운 것을 만들 수 있습니다. 동시성, 여러 동시 버전의 테이블 등에 유용 할 수 있습니다.
불변의 트리는 압축 가능합니다. 즉, 그것은 구조를 공유 할 수 있습니다 접미사 또한 해시 소싱에 의해.

해시블의 장점 :

모두가 해시블을 알고 있습니까? 귀하의 시스템은 이미 대부분의 목적을 위해 시도하는 것보다 빠른 잘 최적화 된 구현을 가지고 있습니다.
키에는 특별한 구조가 필요하지 않습니다.
명백한 연결된 트리 구조보다 공간 효율적인 (아래의 의견을 참조하십시오)

다른 팁

그것은 모두 해결하려는 문제에 달려 있습니다. 삽입 및 조회 만 있으면 해시 테이블을 사용하십시오. 접두사 관련 쿼리와 같은 더 복잡한 문제를 해결 해야하는 경우 트리가 더 나은 솔루션 일 수 있습니다.

모든 사람은 해시 테이블과 그 용도를 알고 있지만 정확히 일정하게 조회하는 것은 아닙니다. 해시 테이블이 얼마나 큰지, 해시 함수의 계산 복잡성에 달려 있습니다.

효율적인 조회를위한 거대한 해시 테이블을 만드는 것은 작은 대기 시간/확장 성이 중요한 대부분의 산업 시나리오에서 우아한 솔루션이 아닙니다 (예 : 고주파수 거래). 캐시 미스를 줄이기 위해 메모리에서 차지하는 공간에 최적화하려면 데이터 구조에 신경을 써야합니다.

Trie가 요구 사항에 더 적합한 아주 좋은 예는 메시징 미들웨어입니다. 당신은 주제 (실제로 문자열)를 기반으로 메시지를 걸러 내려는 경우, 당신은 확실히 해시 테이블을 만드는 것을 원하지 않는 경우,이 경우에는 다양한 카테고리 (JMS 용어 - 주제 또는 교환)로 메시지의 백만 가입자와 게시자가 있습니다. 백만 주제가있는 백만 구독의 경우. 더 나은 접근 방식은 TRIE에 주제를 저장하는 것입니다. 따라서 주제 일치를 기반으로 필터링이 수행되면 복잡성은 주제/구독/게시자의 수와 무관합니다 (문자열 길이에만 의존). 이 데이터 구조로 창의력을 발휘하여 공간 요구 사항을 최적화하므로 캐시 미스가 더 낮습니다.

나무 사용 :

자동 완료 기능이 필요한 경우
'a'또는 'ax'로 시작하여 모든 단어를 찾으십시오.
접미사 트리는 특별한 형태의 나무입니다. 접미사 나무에는 해시가 다룰 수없는 전체 장점 목록이 있습니다.

해시 가능 구현은 기본에 비해 공간 효율적입니다 트리 구현. 그러나 문자열의 경우 대부분의 실제 응용 분야에서 순서가 필요합니다. 그러나 해시 테이블은 어휘 학적 순서를 완전히 방해합니다. 이제 응용 프로그램이 설명 순서 (부분 검색, 주어진 접두사가있는 모든 문자열, 정렬 된 순서의 모든 단어)에 따라 작업을 수행하는 경우 Tries를 사용해야합니다. 조회 만 있으면 해시 테이블을 사용해야합니다 (아마도 최소 조회 시간을 제공합니다).

추신: 이것 외에는 3 차 검색 트리 (TST) 훌륭한 선택이 될 것입니다. 조회 시간은 해시 가능보다 많지만 다른 모든 작업에서는 시간 효율적입니다. 또한 시도보다 공간 효율성이 높습니다.

내가 명심해야한다고 생각하는 사람은 명시 적으로 언급 한 사람이없는 것이 있습니다. 해시 테이블과 다양한 종류의 시도는 일반적으로 O(k) 운영, 어디에 k 문자열의 길이는 비트 (또는 숯에서 동일)입니다.

이것은 당신이 좋은 해시 기능이 있다고 가정합니다. "농장"과 "농장 동물"을 동일한 값으로 해시에 원하지 않는다면 해시 함수는 키의 모든 비트를 사용해야하므로 "농장 동물"은 "농장 동물"을 사용해야합니다. "Farm"(롤링 해시 시나리오에 있지 않으면 시도와도 비슷한 운영 절약 시나리오가 있습니다). 그리고 바닐라를 시도하면 "농장 동물"을 삽입하는 것이 "농장"보다 약 2 배가 걸리는 이유가 분명합니다. 장기적으로는 압축 시도도 마찬가지입니다.

트리의 삽입 및 조회는 입력 문자열 O (S)의 Lengh와 선형입니다.

해시는 조회 ANS 삽입을위한 O (1)를 제공하지만 먼저 입력 문자열을 기반으로 해시를 계산해야합니다.

결론, 무증상 시간 복잡성은 두 경우 모두 선형입니다.

Trie는 데이터 관점에서 더 많은 오버 헤드를 가지고 있지만 압축 된 트리를 선택하여 해시 테이블과 넥타이를 타고 다시 할 수 있습니다.

넥타이를 깨뜨리려면 스스로 에게이 질문을합니다. 전체 단어 만 찾아야합니까? 아니면 접두사와 일치하는 모든 단어를 반환해야합니까? (예측 텍스트 입력 시스템에서와 같이). 첫 번째 경우에는 해시로 가십시오. 더 간단하고 깨끗한 코드입니다. 테스트하고 유지하기가 더 쉽습니다. 접두사 또는 sufixes가 중요한 경우보다 타원 된 사용 사례를 보려면 트리를 찾으십시오.

그리고 만약 당신이 재미를 위해 그것을한다면, 트리를 구현하면 일요일 오후를 잘 활용할 것입니다.

일부 (일반적으로 임베디드, 실시간) 응용 프로그램은 처리 시간이 데이터와 무관해야합니다. 이 경우 해시 테이블은 알려진 실행 시간을 보장 할 수 있으며 데이터에 따라 트리가 다양합니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow