Trình bày các tập số nguyên thưa thớt?

Question

Cách tốt nhất để trình bày các tập số nguyên thô (thực sự là địa chỉ bộ nhớ C) một cách gọn nhẹ và nhanh chóng. Tôi đã biết về những điều hiển nhiên như bit-vector và mã hóa độ dài chạy. nhưng tôi muốn một cái gì đó nhỏ gọn hơn một từ cho mỗi phần tử thiết lập. Tôi cần thêm và xóa các thành phần và kiểm tra tư cách thành viên. Tôi không cần các hoạt động thiết lập khác, như công đoàn.

Tôi đã đọc về một thư viện như vậy nhiều năm trước nhưng đã quên tên của nó. Tôi nghĩ rằng nó đã được phát hành như là mã nguồn mở của HP và có một tên của người phụ nữ.

Answer 1

Bạn đang tham chiếu đến mảng bản án. Đó là một dự án HP. Tôi nghĩ rằng chúng được sử dụng trong ruby ​​và có sẵn trong c. Cấu trúc dữ liệu rất thú vị. Sử dụng thực tế rằng phân bổ là (ít nhất) từ phù hợp, có cấu trúc riêng biệt cho phạm vi dày đặc và thưa thớt.

http://judy.sourceforge.net/index.html

Answer 2

Nếu tất cả những gì bạn cần là chèn, xóa và thử nghiệm thành viên, thì bảng băm sẽ phù hợp với bạn một cách độc đáo. Bạn có thể tìm thấy một số hàm băm tốt để băm số nguyên 32 bit here.

Answer 3

Nếu bạn muốn cấu trúc nhỏ hơn tập hợp dữ liệu, bạn nên xem xét một số loại sắp xếp cây. Làm cho mỗi cấp của một cách 4 cây phím tắt 2 bit bắt đầu từ cao cấp và nó có thể nhỏ gọn khá tốt (nếu con trỏ có bất kỳ mức độ của địa phương không gian). Các trick sẽ được mã hóa nó đủ nhỏ gọn (chỉ mục vào mảng của các nút? Một mảng ánh xạ cây?).

Answer 4

Cấu trúc dữ liệu rất nhỏ gọn sẽ là bộ lọc nở, có lẽ bộ lọc đếm đếm để hỗ trợ xóa.

http://en.wikipedia.org/wiki/Bloom_filter

Bộ lọc Bloom, hình thành bởi Burton H. Bloom vào năm 1970, là một cấu trúc dữ liệu xác suất không gian hiệu quả được sử dụng để kiểm tra xem một yếu tố là thành viên của một tập. Sai tích cực là có thể, nhưng âm tính giả thì không. Các phần tử có thể được thêm vào tập hợp, nhưng không bị xóa (mặc dù điều này có thể được giải quyết bằng bộ lọc đếm)