[algorithm] 해시 테이블과 Trie (접두사 트리) 중에서 어떻게 선택합니까?
따라서 해시 테이블이나 접두사 트리 중에서 선택 해야하는 경우 하나를 선택하도록 유도하는 구별 요소는 무엇입니까? 내 자신의 순진한 관점에서 trie를 사용하면 배열로 저장되지 않기 때문에 약간의 오버 헤드가있는 것처럼 보이지만 런타임 측면에서 (가장 긴 키가 가장 긴 영어 단어라고 가정) 본질적으로 O 일 수 있습니다 (1) (상한과 관련하여). 아마도 가장 긴 영어 단어는 50 자일까요?
인덱스를 얻으면 해시 테이블을 즉시 찾을 수 있습니다 . 그러나 인덱스를 얻기 위해 키를 해싱하면 약 50 단계를 쉽게 수행 할 수있는 것처럼 보입니다.
누군가 나에게 이것에 대해 더 경험있는 관점을 제공 할 수 있습니까? 감사!
답변
시도의 장점 :
기본 사항 :
- k가 키의 크기 인 예측 가능한 O (k) 조회 시간
- 조회가없는 경우 k 시간 미만이 소요될 수 있습니다.
- 주문 된 순회 지원
- 해시 함수 불필요
- 삭제는 간단합니다
새로운 작업 :
- 키의 접두사를 빠르게 찾고 주어진 접두사 등으로 모든 항목을 열거 할 수 있습니다.
연결된 구조의 장점 :
- 공통 접두사가 많은 경우 필요한 접두사가 공유됩니다.
- 불변의 시도는 구조를 공유 할 수 있습니다. 제자리를 업데이트하는 대신, 하나의 지점을 따라 다른 지점을 다른 곳에서 다른 새로운 지점을 만들 수 있습니다. 이것은 동시성, 테이블의 여러 동시 버전 등에 유용 할 수 있습니다.
- 불변의 trie는 압축 가능합니다. 즉, 해시 구성을 통해 접미사 에 대한 구조도 공유 할 수 있습니다 .
해시 테이블의 장점 :
- 누구나 해시 테이블을 알고 있습니다. 시스템은 이미 대부분의 목적을 위해 시도하는 것보다 빠르게 잘 최적화 된 구현을 가지고 있습니다.
- 키에는 특별한 구조가 필요하지 않습니다.
- 명백한 링크 된 trie 구조보다 공간 효율적입니다 ( 아래 주석 참조 ).
답변
그것은 당신이 해결하려는 문제에 달려 있습니다. 삽입 및 조회 만하면 해시 테이블을 사용할 수 있습니다. 접두사 관련 쿼리와 같은보다 복잡한 문제를 해결해야하는 경우 trie가 더 나은 솔루션 일 수 있습니다.
답변
모든 사람은 해시 테이블과 그 용도를 알고 있지만 정확히 일정한 조회 시간이 아니며 해시 테이블의 크기, 해시 함수의 계산 복잡성에 따라 다릅니다.
효율적인 조회를 위해 거대한 해시 테이블을 생성하는 것은 약간의 대기 시간 / 확장 성 문제 (예 : 고주파수 거래)가 필요한 대부분의 산업 시나리오에서 훌륭한 솔루션이 아닙니다. 캐시 미스를 줄이려면 메모리에서 차지하는 공간에 맞게 데이터 구조를 최적화해야합니다.
trie가 요구 사항에 더 적합한 아주 좋은 예는 메시징 미들웨어입니다. 다양한 카테고리 (JMS 용어-주제 또는 교환)의 메시지 구독자 및 발행자 수가 백만 명입니다. 이러한 경우 주제 (실제로 문자열 임)를 기준으로 메시지를 필터링하려는 경우 해시 테이블을 작성하고 싶지 않습니다. 백만 개의 주제를 가진 백만 개의 구독. 더 나은 방법은 토픽을 trie로 저장하는 것이므로 토픽 일치를 기준으로 필터링을 수행 할 때 복잡도는 토픽 / 구독 / 게시자 수와 무관합니다 (문자열 길이에만 의존). 공간 요구 사항을 최적화하기 위해이 데이터 구조를 창의적으로 사용할 수 있으므로 캐시 미스가 더 적기 때문에 마음에 듭니다.
답변
나무를 사용하십시오 :
- 자동 완성 기능이 필요한 경우
- ‘a’또는 ‘axe’로 시작하는 모든 단어를 찾으십시오.
- 접미사 트리는 특수한 형태의 트리입니다. 접미사 트리에는 해시가 처리 할 수없는 전체 이점 목록이 있습니다.
답변
내가 명심해야하는 것이 중요하다고 명시 적으로 언급 한 것을 보지 못한 것이 있습니다. 다양한 종류의 해시 테이블과 시도는 일반적으로 O(k)작업을 수행합니다.k 문자열의 길이가 비트 단위 (또는 문자 수) 인 .
이것은 좋은 해시 함수가 있다고 가정합니다. “farm”과 “farm animals”를 같은 값으로 해시하지 않으려면 해시 함수가 키의 모든 비트를 사용해야하므로 “farm animals”를 해시하는 데 걸리는 시간은 약 2 배입니다. “팜”(롤링 해시 시나리오에 속하지 않는 한 시도와 비슷한 작업 절약 시나리오가 있음). 바닐라 트리를 사용하면 왜 “농장 동물”을 삽입하는 것이 “농장”보다 두 배나 더 오래 걸리는지는 분명합니다. 장기적으로 압축 시도도 마찬가지입니다.
답변
트라이에 대한 삽입 및 조회는 입력 문자열 O의 길이와 선형입니다.
해시는 조회 및 삽입을 위해 O (1)을 제공하지만 먼저 O (s) 인 입력 문자열을 기반으로 해시를 계산해야합니다.
결론적으로, 점근 시간 복잡도는 두 경우 모두 선형입니다.
트라이는 데이터 관점에서 약간의 오버 헤드가 있지만 압축 된 트라이를 선택하여 해시 테이블과의 관계를 다시 어느 정도 줄일 수 있습니다.
넥타이를 끊으려면 다음과 같이 스스로에게 질문하십시오. 전체 단어 만 찾아야합니까? 아니면 접두사와 일치하는 모든 단어를 반환해야합니까? (예측 텍스트 입력 시스템과 동일). 첫 번째 경우 해시로 이동하십시오. 더 간단하고 깨끗한 코드입니다. 테스트와 유지 보수가 더 쉬워졌습니다. 접두사 또는 접미사가 중요한 좀 더 정교한 사용 사례를 보려면 시도하십시오.
그리고 당신이 재미를 위해 그것을한다면, trie를 구현하면 일요일 오후를 잘 사용할 수 있습니다.
답변
HashTable 구현은 기본 Trie 구현에 비해 공간 효율적 입니다. 그러나 문자열을 사용하면 대부분의 실제 응용 프로그램에서 순서가 필요합니다. 그러나 HashTable은 사전 순서를 완전히 방해합니다. 이제 응용 프로그램에서 사전 순서에 따라 작업을 수행하는 경우 (부분 검색, 지정된 접두사가있는 모든 문자열, 정렬 된 모든 단어 등) Tries를 사용해야합니다. 조회에만 HashTable을 사용해야합니다 (논리적으로 최소 조회 시간을 제공함).
추신 : 이것들 외에, TST (Ternary Search Trees) 가 훌륭한 선택이 될 것입니다. 조회 시간은 HashTable 이상이지만 다른 모든 작업에서는 시간 효율적입니다. 또한 시도보다 공간 효율적입니다.
