혹시 trie와 hash 중에 어떤것이 더욱 효과적일까요?

jms_jms의 이미지

음.. 일단 4byte에 대한 unique한 값이 들어온다고 가정했을 경우

둘중에 어떤것이 유리할까요?

4byte에 대한 값에 mark된 시점도 갖고 있는다고 가정할 경우 hash가 더욱 깔끔하지 않을까요?

+ 추가 정보를 갖는다고 했을 경우

트라이와 hash중에 성능이나 공간적인 면에서 어떤 구조가 나을까요?

저는 두개의 별 차이가 없을거 같은데.. trie가 성능이 좀 나을 것 같고..

구현 이슈는 hash가 훨 나을것 같습니다.

답변 부탁드립니다. 성능적인 issue도 좀 있는거라서...

ㅠ,.ㅠ 아직.. 초보라서 암것두 모르네염..ㅋ

익명 사용자의 이미지

hash

장점 : 빠르다
단점 : trie 보다 디스크를 많이 먹는다

trie

장점 : hash 에 비해 디스크를 덜 먹는다.
단점 : hash 보단 느리다.

-----------------------------

메모리/디스크가 빵빵한 환경이면 해쉬쓰세요.

익명_사용자의 이미지

hash도 hashing-function에 따라, collision으로 인한 많은 문제를 겪을 수가 있고,
그로인해 trie보다 느릴수 있습니다.

또한, read operation과 write operation의 빈도에 따라, hash가 빠를수도 있고, trie가 빠를수도 있습니다.
또한, read operation과 write operation의 패턴에 따라, hash가 빠를수도 있고, trie가 빠를수도 있습니다.
또한, 입력 데이터의 패턴에 따라, hash가 빠를수도 있고, trie가 빠를수도 있습니다.

hash가 빠르고, 디스크(???왠 디스크?)를 많이 먹는다는..
저런 정확하지 않은 대충써놓은 답변은 오히려 질문자를 잘못된 정보를 주는셈이 될수도 있습니다.

hash의 장점을 나열하자면
빠르다는게 아니고, access time이 O(1), 즉 상수시간입니다. 한번만에 찾으니 빠른거 아니냐고 묻는다면, 항상 그런것은 아니라고 할수 있습니다.
또한, write time또한 O(1)입니다.

단점은
access time 과 write time이 O(1)이라는것은, 오로지 collision이 없는, full-hashing 일때만입니다.
즉, collision을 해결하기 위해, 정말 최악의 시간이 나올수도 있습니다. collision을 최소화 시키는 방안들은, 기본적으로 trade-off입니다.

메모리를 희생시키던지( 이것은, 자원관리차원에서 문제가 될수도 있습니다. 메모리는 operation은 매우 비쌉니다. 또한, random-access on hash-table은 대표적인 단점 중 하나입니다. 왜냐면, hash table크기가 크고, 자료 access의 패턴이 아주 randomize되었다면, CPU cache miss-rate가 높아질수 있기 때문입니다. )
CPU를 희생시키던지( 즉, access-time이 O(N)이 될수도 있습니다. 물론, 대부분 더 좋은 collision 솔루션이 많아서, O(N)까지는 아닌 경우가 대부분이지만, 그것또한 additional memory space를 필요로 하거나, 가령 각각의 hash element는 O(logN)의 access time을 갖는 binary tree 라던지.. )

trie는 hash에 비하여 (상대적으로) cache-friendly라고 할수 있습니다.
최소한, 자주 access되는 node path들의 상위 노드들은 거의 cpu cache되었다고 생각할수도 있으니까요.

또한, key의 길이가 크고, key의 많은 부분들이 겹치는 경우라면 이득이 더욱 큽니다.

가령, 저의 경우, HTTP-request dispatcher는 trie로 구현했는데,
왜냐면, 요청이 들어오면, 갖은/비슷한 요청이 들어올 가능성이 아주 크고( CPU cache된 O(logN)은 CPU cache되지 않은 O(1)보다 훨신 빠를수 있습니다. 물론, hash또한, 같은 요청이 계속들어오면 CPU cache되는것은 동일한데, cache가 둘다 되었다면, O(logN)과 O(1)의 성능차이는 생각보다 적을수 있습니다. )

디렉토리 구조상

/abc/foo.html
/abc/foo2.html
/abc/foo3.html

이런경우, 상위 /abc의 비교는 trie구조상, 중복 비교를 없에버릴수 있기 때문입니다.

아무튼, 결론은 그냥 hash가 빠르고, trie가 느리다...이런것은 무책임한 표현이고

입력데이터의 패턴과 특징
write-operation/read-operation의 빈도
입력가능한 총 데이터의 크기

등에 따라, 다릅니다.

또한, 좀 더 이산수학적인 얘기가 아니라, 구현물에 대한 얘기까지 하면
SMP환경의 multi-threaded 프로그램이라면

해당 자료구조를 thread-safe하게 만들어야합니다.
프로그램 구조에 따라( SPSC, SPMC, MPSC, MPMC => Single Producer Single Consumer Multi Producer .... )

linked-list 자료구조를 이용한 trie가
lock-free또는 wait-free locking 알고리즘을 구현하는데 더 쉬울수가 있습니다.
( hash도 collision이 없는 full-hashing이라면 쉽게 구현할수있지만, collision이라도 있어서
re-hashing해야하는 상황을 lock-free하려면;;;;;; ㅎㄷㄷ)

성능에서 mutex같은 locking 은 쥐약이 될수도 있습니다.

clique의 이미지

4바이트라면 그냥 hash나 btree가 낫지 않을지요?
최적화된 256-nary-trie계열이라면, judyarray가 라이브러리로 공개되어있으니 테스트 해보셔도 좋을 것 같네요

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.