Có ai có cài đặt Cuckoo hashing trong C không? Nếu có một nguồn mở, phiên bản không phải của GPL sẽ hoàn hảo!Cuckoo băm trong C
Vì Adam đã đề cập đến nó trong bình luận của mình, có ai biết tại sao nó không được sử dụng nhiều? Nó chỉ là một vấn đề của việc thực hiện hoặc các tính chất lý thuyết tốt không thực hiện trong thực tế?
Cảm ơn, điều đó rất hữu ích vì nó đi kèm với báo cáo về băm d-ary! –
Không chắc chắn về việc cấp phép ở đây. – Demi
Cuckoo băm tương đối không được sử dụng bên ngoài học viện (ngoài bộ đệm phần cứng, đôi khi mượn ý tưởng từ, nhưng không thực sự triển khai đầy đủ). Nó đòi hỏi một bảng băm rất thưa thớt để có được thời gian tốt trên chèn - bạn thực sự cần phải có 51% của bảng của bạn trống cho hiệu suất tốt. Vì vậy, nó hoặc là nhanh chóng và mất rất nhiều không gian, hoặc làm chậm và sử dụng không gian hiệu quả - không bao giờ cả hai. Các thuật toán khác đều hiệu quả về thời gian và không gian, mặc dù chúng tồi tệ hơn so với cúc cu khi chỉ có thời gian hoặc không gian được tính đến.
Đây là code generator for cuckoo hash tables. Kiểm tra giấy phép của máy phát điện để xác minh rằng đầu ra không phải là GPL. Nó nên được, nhưng hãy kiểm tra anyway.
-Adam
Bản thân máy phát điện được đánh dấu là GPLv3. Đã không tìm ra nếu đầu ra là hay không. –
Nó đòi hỏi một bảng là 51% trống cho hiệu suất tốt, do đó, nó là thời gian hiệu quả, hoặc không gian hiệu quả, nhưng không phải cả hai. Các phương pháp khác chỉ đơn giản là tốt hơn trên cả hai số, mặc dù chúng có thể tồi tệ hơn trên một hoặc khác. Hơn nữa, nó là khó khăn để thực hiện tốt (đó là lý do tại sao có một máy phát điện ...) –
Tôi đã có một cái nhìn tại máy phát điện. Thật không may, nó dường như là nhằm tạo các bảng tra cứu tĩnh thay vì các thùng chứa chung chung. Tuy nhiên đó là một lựa chọn tốt cho gperf, tôi nghĩ! –
Ngôn ngữ IO có một, trong PHash.c. Bạn có thể tìm thấy số code for IO trên Github. IO được cấp phép BSD.
Cảm ơn Jordi. Tôi sẽ có một cái nhìn –
Các tập tin PHash.c trong nguồn Io là lỗi thời. Nó đã không được chấp nhận bởi CHash.c trong libbasekit được đóng gói với Io. http://www.dekorte.com/projects/opensource/libbasekit/ –
Tôi thấy điểm sử dụng nhưng đây là lý do của tôi để thử lược đồ băm cụ thể này. Xin vui lòng cho tôi biết nếu tôi bỏ lỡ một cái gì đó.
Theo hiểu biết của tôi, các lựa chọn thay thế có thể có cho hashtables để tạo từ điển động là cây nhị phân (cân bằng) và skiplists. Chỉ để thảo luận chúng ta hãy tóm tắt từ các loại khóa và giá trị và giả sử rằng chúng ta sẽ truy cập các giá trị thông qua một void *.
Đối với một cây nhị phân tôi sẽ có:
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
Vì vậy, con trỏ giả có tất cả các kích thước tương tự s, để lưu trữ n mục tôi sẽ cần 4 s byte.
Skiplists là gần như giống nhau như số lượng trung bình của con trỏ trong một nút là 2.
Trong một Hashtable tôi sẽ có:
struct slot {
void *key;
void *value;
}
Vì vậy, mỗi mục sẽ chỉ requre 2 s byte được lưu trữ. Nếu hệ số tải là 50%, để lưu trữ n mục, tôi sẽ cần cùng một số 4 s byte làm cây.
Nó không có vẻ quá xấu với tôi: cuckoo hashtable sẽ chiếm nhiều hơn hoặc ít hơn cùng một lượng bộ nhớ như một cây nhị phân nhưng sẽ cho tôi O (1) thời gian truy cập thay vì O (log n).
Không tính độ phức tạp của việc giữ cân bằng cây và thông tin bổ sung có thể được yêu cầu để lưu trữ thông tin cân bằng trong nút.
Các chương trình băm khác có thể đạt được hệ số tải tốt hơn (75% hoặc 80%) mà không đảm bảo thời gian truy cập trường hợp xấu nhất (thậm chí có thể là O (n)).
Nhân tiện, d-ary cuckoo hashing và "cuckoo hashing with a stash" dường như có thể tăng hệ số tải trong khi vẫn giữ thời gian truy cập liên tục.
Cuckoo băm có vẻ là một kỹ thuật có giá trị đối với tôi và tôi nghĩ rằng nó đã được khám phá; đó là lý do cho câu hỏi của tôi.
Btw, O (1) tra cứu cho hashtables về cơ bản là một huyền thoại. Các bit tối thiểu cần thiết để thể hiện N giá trị riêng biệt tỷ lệ với log N, do đó hàm băm hầu như luôn có hiệu lực O (log N). Nếu bạn lưu trữ giá trị băm bên trong các đối tượng, thì đó là O (1) cho các lần tra cứu lặp lại tiếp theo của cùng một đối tượng. –
Điều đó nói rằng, hashtables thường nhanh hơn cây.Nhưng đó là vì cây thường thu thập dữ liệu trên toàn bộ bộ nhớ và/hoặc sử dụng chức năng so sánh "không liên tục". –
O() chỉ được đề cập đến số lượng so sánh cần thiết để kiểm tra khóa. Đối với yêu cầu bộ nhớ: Tôi nghĩ rằng tôi cho thấy rằng không gian nhiều hơn 50% (nhiều hơn hoặc ít hơn) những gì người ta nhận được nếu anh ta chọn một từ điển dựa trên cây. Tôi không chắc tôi đã bỏ lỡ một cái gì đó vì vậy tôi muốn chào đón bất kỳ bình luận về điều đó! –
Sau một nhận xét từ "onebyone", tôi đã triển khai và thử nghiệm một vài phiên bản của buckoo băm để xác định yêu cầu bộ nhớ thực.
Sau một số thử nghiệm, xác nhận quyền sở hữu mà bạn không phải xích cho đến khi bảng gần như đầy 50% có vẻ đúng, đặc biệt nếu lừa "stash" được thêm vào.
Vấn đề là khi bạn phóng to bảng. Cách tiếp cận thông thường là tăng gấp đôi kích thước của nó nhưng điều này dẫn đến bảng mới chỉ được sử dụng 25%!
Thực tế, giả định hashtable có 16 vị trí, khi tôi chèn số phần tử thứ 8, tôi sẽ hết các vị trí tốt và sẽ phải xâu chuỗi. Tôi sẽ tăng gấp đôi nó và bây giờ bảng là 32 khe với chỉ 8 trong số họ chiếm đó là một chất thải 75%!
Đây là mức giá phải trả để có thời gian truy xuất "không đổi" (về giới hạn trên cho số lượng truy cập/so sánh).
Tôi đã nghĩ ra một giản đồ khác: bắt đầu từ lũy thừa 2 lớn hơn 1, nếu bảng có n vị trí và n là lũy thừa của hai, thêm n/2 vị trí khác khi thêm n/3 vị trí:
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
, vv
Cùng với giả định rằng reashing sẽ chỉ xảy ra khi bảng là 50% đầy đủ, điều này dẫn đến một thực tế rằng bảng sẽ chỉ có 66% sản phẩm nào (1/3) chứ không phải hơn 75% sản phẩm nào (1/4) sau khi xích (tức là trường hợp xấu nhất).
Tôi cũng đã tìm ra (nhưng tôi vẫn cần phải kiểm tra toán học) mở rộng mỗi lần bằng sqrt (n), không gian lãng phí tiệm cận gần 50%.
Tất nhiên giá phải trả cho mức tiêu thụ bộ nhớ ít hơn là sự gia tăng số lượng dây xích cần thiết cuối cùng. Than ôi, không có gì đến miễn phí.
Tôi sẽ điều tra thêm nếu có ai quan tâm.
Thông thường, bảng được giới hạn ở kích thước POT để cho phép bitwise AND được sử dụng trên băm chứ không phải là mô đun. – NateS
Như câu trả lời khác đã chỉ ra, đó là sự thật rằng chim cu Hashtable đơn giản đòi hỏi rằng bảng được một nửa sản phẩm nào. Tuy nhiên, khái niệm này đã được tổng quát thành d băm cúc cu trong khi mỗi phím có d các địa điểm có thể làm tổ, thay vì 2 vị trí trong phiên bản đơn giản.
Hệ số tải có thể chấp nhận tăng nhanh khi d được tăng lên. Chỉ với d = 3, bạn đã có thể sử dụng khoảng 75% toàn bộ bảng. Nhược điểm là bạn cần d hàm băm độc lập. Tôi là một fan hâm mộ của hàm băm Bob Jenkins 'cho mục đích này (xem http://burtleburtle.net/bob/c/lookup3.c), mà bạn có thể thấy hữu ích trong việc triển khai băm cuckoo.
Vâng, "các hàm băm khác nhau" cũng có thể là cùng chức năng với các hạt khác nhau. –
Tôi không thể nói cho phần mềm nhưng buckoo cuckoo chắc chắn được sử dụng trong phần cứng và trở nên rất phổ biến. Các nhà cung cấp thiết bị mạng chính đã và đang xem xét việc băm cúc cu và một số đã sử dụng nó. Sự hấp dẫn để buckoo cúc bừa đến từ thời gian tra cứu liên tục, tất nhiên, nhưng cũng gần thời gian chèn liên tục.
Mặc dù chèn về mặt lý thuyết có thể không bị chặn, trong thực tế nó có thể được gắn với O (log n) của số hàng trong bảng và khi được đo, thời gian chèn là khoảng 1,1 * d bộ nhớ truy cập trung bình . Đó chỉ là 10% nhiều hơn mức tối thiểu tuyệt đối! Truy cập bộ nhớ thường là yếu tố hạn chế trong thiết bị mạng.
Hàm băm độc lập là phải và chọn chúng đúng cách là khó khăn. Chúc may mắn.
Mặc dù nó là một câu hỏi cũ, ai đó có thể vẫn được quan tâm :)
This paper mô tả thi hành một d-ary băm chim cu song song trên GPU (CUDA/OpenCL). Nó được mô tả rất tốt và thực hiện nó dựa trên mô tả là khá dễ dàng. Nói chung đáng đọc, nếu bạn quan tâm đến chủ đề này. (Tuy nhiên, bạn sẽ cần đăng nhập ACM.)
Có thể bạn sẽ bị giảm bớt cho yêu cầu "không GPL" ... :-))) –
Chúng ta có thực sự cần một thẻ buckoo-băm không? Thành thật mà nói ... –
Tôi hy vọng không - Tôi biết những người đam mê GPL có thể hung hăng, nhưng tôi hy vọng họ có thể thấy sự cần thiết cho các giấy phép khác và ít nhất là khoan dung. –