검색어와 일치하는 인덱스 -> 검색어로 시작하는 인덱스 about youtube_caption_analyzer HOT 1 OPEN

결과 (Trie vs Dictionary)

1. 인덱싱

• 약 4MB의 명사 문서를 인덱싱하는데 걸리는 시간
• Dictionary
  1.51 s ± 66.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
• Trie
  19.8 s ± 291 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
• 약 13배 느림 (19.8 s/ 1.51 s).

2. 검색

• 다음 9개의 단어 검색하는데 걸리는 시간
  words = ['프로', 'c++', 'c#', 'c', '프로그래밍', '야근', '하드웨어', '저수준', '포프']
• n : 인덱스 단어 수, m : 검색 단어 길이
• Dictionary
  -. 검색어와 인덱스가 일치하는 검색, O(1)
  806 µs ± 13.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  -. 검색어로 시작하는 인덱스 검색, O(n)
  29 ms ± 482 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
• Trie
  -. 검색어로 시작하는 인덱스 검색, O(m)
  1.42 ms ± 20 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
• 약 20배 빠름 (29 ms/1.42 ms).

3. 결론

• Trie가 Dictionary 대비 인덱싱은 13배 느리고 검색은 20배 빠르다.
• 문서의 양이 적을 때는 Dictionary, Trie의 검색 속도는 체감상 차이가 안난다.
• 테스트 단계에서는 인덱싱이 빠른 Dictionary를 사용하고 실 사용 단계에서는, 문서의 양이 많아지면 Trie를 고려해보자.

from youtube_caption_analyzer.