Cây Ternary Vs Bảng băm

Question

Tôi cần biết liệu một số ternary tree có tốt hơn hash table hay không.

Tôi đã xem câu hỏi này để trả lời another question I had nơi người nào đó nói rằng cây ba đại thường nhanh hơn bảng băm. Tôi thấy khó tin, vì vậy tôi quyết định nghiên cứu một chút về nó.

This one website from Princeton dường như là nguồn gốc của niềm tin. Tôi đã xem xét thuật toán được mô tả là O (log n + k) trong đó n là số lượng từ được lưu trữ, và k là độ dài của khóa.

Dường như với tôi rằng cách duy nhất này có thể nhanh hơn là nếu bạn thường tìm kiếm các yếu tố chưa được lưu trữ. Một điều khiến tôi phiền lòng, đó là việc thu thập thông tin không liên tục của một trie sẽ khiến bạn đánh các trang đã được hoán đổi, nhưng liệu đây có phải là một hiệu ứng chính chỉ có thể được nhìn thấy thông qua các điểm chuẩn.

Bây giờ tôi biết rằng có thể có ưu và khuyết điểm đối với cả hai người, và nếu có, tôi muốn biết họ là ai. Điểm chuẩn cũng hữu ích.

Answer 1

Điều này cũng khá thú vị với tôi. Nhưng từ wiki tôi đọc, nó tuyên bố rằng cây ternary Tree nhanh hơn ở hầu hết các vấn đề tìm kiếm. Điều này là không đáng ngạc nhiên, bởi vì mặc dù bảng băm có O (1) tra cứu, bạn vẫn cần thời gian làm băm. Vì vậy, nó không thực sự O (1) nhưng nhiều hơn như O (k) trong đó k không phụ thuộc vào N (số lượng các mục trong cấu trúc dữ liệu). Điều này có thể mang lại ấn tượng rằng Hash Table nhanh hơn. Tuy nhiên, nếu bạn đang đối phó với một cấu trúc lớn, k nhanh chóng thêm vào và sẽ có một điểm mà tốc độ tìm kiếm của Hash Tables trở nên chậm hơn so với cây Ternary.

Answer 2

Dưới đây là những gì tôi thu thập từ Dr. Dobbs Article thể truy cập từ liên kết Princeton bạn đã cho:

1. ternary Search Trees là nhanh hơn so với bảng băm trên một số vấn đề tìm kiếm lên đến 10%. Đôi khi chúng chậm hơn - tùy thuộc rất nhiều vào máy được sử dụng.
2. TRTs là cấu trúc dữ liệu tùy chỉnh được điều chỉnh bởi hai trong số những bộ óc tốt nhất của Khoa học Máy tính - Jon Bentley và Robert Sedgewick cả hai đã viết goodtextbooks và đã thực hiện phần chia sẻ lập trình thực tế của họ. Các bảng băm được xem là run-of-the-mill.
3. Các hằng số có liên quan là đáng kể, như Hao Wooi Lin nói.
4. Nhìn chung, điều này phụ thuộc vào vấn đề bạn đang giải quyết. Thời gian phát triển nhanh hơn và hỗ trợ hầu hết mọi nơi cho các bảng băm bằng nhiều ngôn ngữ lập trình thường quan trọng hơn cải thiện mười phần trăm trong thời gian chạy.

Answer 3

nhật ký (n) phát triển chậm để có thể yêu cầu một lượng lớn dữ liệu trước khi nó chậm hơn so với thuật toán O (1) khi tính đến yếu tố không đổi.

Answer 4

Cách duy nhất để trả lời câu hỏi này là theo kinh nghiệm. Câu trả lời phụ thuộc vào các chi tiết triển khai của bạn, loại tìm kiếm bạn làm, phần cứng nào bạn có và trình biên dịch bạn đang sử dụng. Bạn có thể sao chép mã C từ Princeton.Nếu bạn muốn thử một ngôn ngữ chức năng, Standard ML có bảng băm (nhìn vào SML/NJ), và đây là một số ML cho cây tìm kiếm ternary:

type key = Key.ord_key 
type item = Key.ord_key list 

datatype set = NODE of { key : key, lt : set, eq : set, gt : set } 
      | LEAF 

val empty = LEAF 

fun member (_, LEAF) = false 
    | member (h::t, NODE {key, lt, eq, gt}) = 
     (case Key.compare (h, key) 
     of EQUAL => member(t, eq) 
      | LESS => member(h::t, lt) 
      | GREATER => member(h::t, gt)) 
    | member ([], NODE {key, lt, eq, gt}) = 
     (case Key.compare (Key.sentinel, key) 
     of EQUAL => true 
      | LESS => member([], lt) 
      | GREATER => member([], gt)) 

exception AlreadyPresent 

fun insert(h::t, LEAF) = 
     NODE { key = h, eq = insert(t, LEAF), lt = LEAF, gt = LEAF } 
    | insert([], LEAF) = 
     NODE { key = Key.sentinel, eq = LEAF, lt = LEAF, gt = LEAF } 
    | insert(h::t, NODE {key, lt, eq, gt}) = 
     (case Key.compare (h, key) 
     of EQUAL => NODE {key = key, lt = lt, gt = gt, eq = insert(t, eq)} 
      | LESS => NODE {key = key, lt = insert(h::t, lt), gt = gt, eq = eq} 
      | GREATER => NODE {key = key, lt = lt, gt = insert(h::t, gt), eq = eq}) 
    | insert([], NODE {key, lt, eq, gt}) = 
     (case Key.compare (Key.sentinel, key) 
     of EQUAL => raise AlreadyPresent 
      | LESS => NODE {key = key, lt = insert([], lt), gt = gt, eq = eq} 
      | GREATER => NODE {key = key, lt = lt, gt = insert([], gt), eq = eq}) 

fun add(l, n) = insert(l, n) handle AlreadyPresent => n 

Answer 5

Bạn có thể có một cái nhìn tại tstdb: http://code.google.com/p/tstdb/

Cửa hàng kv này dựa trên Ternary Search Tree, và nó tương thích với Memcached. Hơn thế nữa, tstdb hỗ trợ tìm kiếm tiền tố và truy vấn phạm vi được hỗ trợ bởi Cây tìm kiếm Ternary.