Tôi đã có một nhu cầu đặc biệt và những mối quan tâm quan trọng nhất là:thuật toán: số khổng lồ của mảng chút rất thưa thớt, mà mã hóa để sử dụng
- trong bộ nhớ
- nhớ rất thấp chân
- speed
Đây là "vấn đề" của tôi: Tôi cần lưu trữ, trong bộ nhớ, một số lượng lớn các mảng bit rất thưa thớt. Những bitets đó chỉ là "nối thêm" và được sử dụng chủ yếu cho các giao lộ. Bởi lớn, tôi có nghĩa là cao như 200 000 bit mảng.
Dải ô phải nằm trong khoảng từ [0 ... 16 000 000] cho mỗi bitet.
Tôi chạy một số pre-test với "chỉ" 10 673 mảng chút có chứa một số dữ liệu thực tế tôi đã có và nhận được kết quả như sau:
1% of the bit arrays ( 106 bit arrays) Hamming weight: at most 1 bit set
5% of the bit arrays ( 534 bit arrays) Hamming weight: at most 4 bits set
10% of the bit arrays (1068 bit arrays) Hamming weight: at most 8 bits set
15% of the bit arrays (1603 bit arrays) Hamming weight: at most 12 bits set
20% of the bit arrays (2137 bit arrays) Hamming weight: at most 17 bits set
25% of the bit arrays (2671 bit arrays) Hamming weight: at most 22 bits set
30% of the bit arrays (3206 bit arrays) Hamming weight: at most 28 bits set
35% of the bit arrays (3740 bit arrays) Hamming weight: at most 35 bits set
40% of the bit arrays (4274 bit arrays) Hamming weight: at most 44 bits set
45% of the bit arrays (4809 bit arrays) Hamming weight: at most 55 bits set
50% of the bit arrays (5343 bit arrays) Hamming weight: at most 67 bits set
55% of the bit arrays (5877 bit arrays) Hamming weight: at most 83 bits set
60% of the bit arrays (6412 bit arrays) Hamming weight: at most 103 bits set
65% of the bit arrays (6946 bit arrays) Hamming weight: at most 128 bits set
70% of the bit arrays (7480 bit arrays) Hamming weight: at most 161 bits set
75% of the bit arrays (8015 bit arrays) Hamming weight: at most 206 bits set
80% of the bit arrays (8549 bit arrays) Hamming weight: at most 275 bits set
85% of the bit arrays (9083 bit arrays) Hamming weight: at most 395 bits set
90% of the bit arrays (9618 bit arrays) Hamming weight: at most 640 bits set
95% of the bit arrays (10152 bit arrays) Hamming weight: at most 1453 bits set
96% of the bit arrays (10259 bit arrays) Hamming weight: at most 1843 bits set
97% of the bit arrays (10366 bit arrays) Hamming weight: at most 2601 bits set
98% of the bit arrays (10473 bit arrays) Hamming weight: at most 3544 bits set
99% of the bit arrays (10580 bit arrays) Hamming weight: at most 4992 bits set
100% of the bit arrays (10687 bit arrays) Hamming weight: at most 53153 bits set
Nhìn những con số liên quan, tôi rõ ràng là cần phải sử dụng nén mảng bit và đó không phải là một vấn đề: nó sẽ ở lại dễ dàng để đối phó với thấy rằng các mảng bit là "nối thêm chỉ".
Các bit mảng bit được bật là nhóm được nhóm, nhưng không hoàn toàn. Vì vậy, bạn sẽ có xu hướng có một vài bit trên trong cùng một khu vực (nhưng thường không phải cái khác, làm cho RLE kinda không tuyệt vời cho các bit được bật).
Câu hỏi của tôi là loại nén nào sẽ sử dụng?
Bây giờ tôi không biết liệu tôi có nên đặt cách tiếp cận đầu tiên của mình ở đây hay trong câu trả lời cho câu hỏi của riêng mình hay không.
Về cơ bản tôi tưởng tượng một "trường hợp xấu nhất" kịch bản sử dụng một mã hóa rất ngớ ngẩn:
1 chút: nếu trên, 5 bit sau xác định bao nhiêu bit là cần thiết để tính toán 'bỏ qua', nếu tắt, tối ưu hóa: 5 bit sau xác định có bao nhiêu bit cũng được thực hiện theo nghĩa đen (nghĩa là 'bật' hoặc 'tắt', không bỏ qua) [điều này sẽ chỉ được chuyển sang khi được xác định là hiệu quả hơn so với các biểu diễn khác, vì vậy khi nó khởi động, nó sẽ luôn là một tối ưu hóa (kích thước khôn ngoan)]
5 bit: số lượng bit chúng ta có thể bỏ qua trước bước tiếp theo t trên
x bit: skip
Dưới đây là một ví dụ: một mảng bit có 3 set bit, các bit đầu tiên là vào lúc 3 098 137, thứ hai lúc 3 098 141 và thứ ba tại 3 098 143.
+-- now we won't skip
|
| +-- 3 because we need 3 bits to store "6" (from 3 098 138 to 3 098 143)
| | +--- 3 098 141 is on
22 3 098 137 | 3 | +- 3 098 143 is on
1 10110 1011110100011000011001 0 00011 000101 etc.
bit đầu tiên cho biết chúng ta sẽ bỏ qua bit. 5 bit tiếp theo (luôn luôn 5) cho biết có bao nhiêu bit chúng ta cần biết số bit chúng ta sẽ bỏ qua 22 bit yêu cầu bỏ qua đến 3 098 137 một chút cho biết bây giờ chúng ta không bỏ qua các bit 5 bit tiếp theo (luôn luôn 5) cho biết có bao nhiêu bit chúng ta sẽ đọc "như là" 6 bit: tắt, tắt, tắt, bật, tắt, có nghĩa là 3 098 141 và 3 098 143 là trên , v.v.
Thấy điều tuyệt vời sparsity của các mảng bit, điều này có vẻ khá kích thước hiệu quả.Vì vậy, bằng cách sử dụng mã hóa đó, tôi lấy dữ liệu mẫu của mình và tính toán trường hợp "trường hợp xấu nhất" (tôi chưa viết bản ngã nào, trước tiên tôi muốn có một vài đầu vào ở đây): về cơ bản tôi đã xem là không chỉ có "tối ưu hóa kích thước" sẽ không bao giờ đá vào và, cũng, rằng 5 bit sẽ luôn luôn được thiết lập giá trị tối đa của họ (24 bit), mà tất nhiên không thể xảy ra.
Tôi đã làm nó chỉ để có một xấp xỉ rất thô của những gì "tồi tệ nhất của trường hợp xấu nhất" có thể được.
Tôi đã rất ngạc nhiên:
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
Các dữ liệu là dữ liệu thực tế và tất cả các dữ liệu là tương tự, tôi biết rằng, nếu xấu đến tồi tệ hơn, tôi có thể lưu trữ 200 000 mảng chút tôi trong khoảng 240 MB, được rồi.
Tôi khá chắc chắn mã hóa thực tế sẽ ít hơn nhưng tôi chưa thực sự viết nó, tôi chỉ có thể (rất dễ) tính toán "trường hợp xấu nhất", đó là lý do tại sao tôi chỉ hiển thị một.
Bất kỳ gợi ý/ý tưởng nào về cách làm cho kích thước này hiệu quả hơn (ghi nhớ đây là mảng bit siêu thưa thớt, sẽ có hàng trăm nghìn, chúng phải nằm trong bộ nhớ và chúng sẽ là " chỉ nối thêm ")?
Về trường hợp 'append-only' của tôi
Về cơ bản tôi đã có một phát triển "rộng" (phạm vi, nhưng "rộng" là một thuật ngữ thực tế như tôi hiểu nó) và rất nhiều mảng bit có một vài bộ. Khi phạm vi đi từ, ví dụ, từ 0 đến 1 000 000, tất cả các mảng bit đều từ 0 đến 1 000 000 đến. Khi phạm vi tăng lên 1 000 001, thì tất cả các mảng bit cũng đang phát triển, tất cả chỉ bằng một bit. Nhưng hầu hết các mảng bit sẽ có một '0' nối vào cuối của chúng, trong khi khoảng 4-8 của mảng bit sẽ có một '1' nối vào cuối của chúng. Tuy nhiên tôi không thể tiên đoán trước mảng bit nào sẽ có 0 hoặc 1 được nối thêm.
Vì vậy, tôi có rất nhiều mảng bit có cùng kích thước, tất cả đều rất thưa thớt (< 0,5% số bit được đặt) và tất cả đều "tăng trưởng" khi tăng trưởng phạm vi (vì vậy chúng ' tất cả luôn phát triển với cùng tốc độ).
Judy arrays thật tuyệt. Nhưng tôi đã đọc về chúng cách đây vài năm và những thứ đó là "trên đầu của tôi". Các mảng Judy là một lib 20KLOC chỉ C và tôi chắc chắn không thực hiện lại điều đó. Nhưng chúng thật tuyệt vời. Vì vậy, tôi đoán tôi cần phải thêm tôi muốn tất cả điều này để ở lại tương đối đơn giản, mà không phải là xa vời thấy đặc biệt "phụ thêm duy nhất" tài sản của mảng bit rất thưa thớt của tôi. Tôi có thể làm như vậy.
Lưu ý rằng các ý kiến về việc phát minh lại bánh xe có thể được gửi tới */dev/null *: nếu chỉ tính toán/thách thức phía sau nó Tôi muốn tự mình thực hiện điều này. Và dù sao tôi cũng sẽ rất ngạc nhiên khi tìm thấy một bánh xe có thể xử lý 200 000 mảng bit "nối thêm" trong bộ nhớ :) Nhưng nếu bạn có một, thì cơ chế đằng sau nó sẽ khiến tôi quan tâm nhiều :) – SyntaxT3rr0r
Có lý thuyết giới hạn về mật độ mã hóa: với mảng các phần tử N, n trong số đó được thiết lập, số bit tối thiểu để mã hóa sẽ là -n * log2 (n/N) - (Nn) * log (1-n/N). Đối với mảng của bạn trong đó 53153 của 16M được thiết lập này sẽ là 514kBits và cho 4992 bit thiết lập - 65 kBits. Và gần gũi hơn với bộ nhớ của bạn với giới hạn này, mã hóa phức tạp hơn bạn phải chọn. – Vovanium
@Vovanium, tôi nghĩ bạn đã bỏ qua một số bối cảnh cần thiết cho giới hạn lý thuyết của bạn (như, một số giả thiết thống kê về phân phối bit được thiết lập?) – comingstorm