Tính xấp xỉ biểu đồ cho dữ liệu truyền trực tuyến

Question

Câu hỏi này là một phần mở rộng nhỏ của một answered here. Tôi đang làm việc để thực hiện lại phiên bản xấp xỉ biểu đồ được tìm thấy trong Mục 2.1 của this paper và tôi muốn nhận tất cả các con vịt của mình liên tiếp trước khi bắt đầu lại quá trình này. Lần trước, tôi đã sử dụng boost::multi_index, nhưng hiệu suất không phải là lớn nhất và tôi muốn tránh lôgarit trong số các nhóm chèn/tìm sự phức tạp của một số std::set. Vì số lượng biểu đồ tôi đang sử dụng (một đối tượng trên mỗi lớp cho mỗi nút lá của một cây ngẫu nhiên trong một khu rừng ngẫu nhiên), độ phức tạp tính toán phải gần như không đổi càng tốt.

Một kỹ thuật tiêu chuẩn được sử dụng để triển khai biểu đồ liên quan đến ánh xạ giá trị thực đầu vào cho một số bin. Để thực hiện điều này, một phương pháp là:

1. khởi tạo mảng C chuẩn có kích thước N, trong đó N = số thùng; và
2. nhân giá trị đầu vào (số thực) với một số yếu tố và làm sàn kết quả để lấy chỉ mục của nó trong mảng C.

Điều này phù hợp với biểu đồ có kích thước thùng đồng đều và khá hiệu quả. Tuy nhiên, Mục 2.1 của giấy được liên kết ở trên cung cấp thuật toán biểu đồ không có kích thước thùng rác thống nhất.

Một vấn đề khác là chỉ cần nhân giá trị thực đầu vào với một yếu tố và sử dụng sản phẩm kết quả làm chỉ mục không thành công với số âm. Để giải quyết vấn đề này, tôi xem xét việc xác định một thùng '0' ở đâu đó trong mảng. Thùng này sẽ được làm trung tâm ở 0.0; các thùng trên/dưới nó có thể được tính toán bằng cách sử dụng cùng một phương pháp nhân và sàn chỉ cần giải thích, với sự sửa đổi nhỏ mà sản phẩm sàn được thêm vào hai hoặc trừ từ hai khi cần thiết.

Điều này sau đó đặt ra câu hỏi về việc hợp nhất: thuật toán trong giấy kết hợp hai thùng gần nhất, được đo từ trung tâm đến tâm. Trong thực tế, điều này tạo ra một xấp xỉ biểu đồ 'lởm chởm', bởi vì một số thùng sẽ có số lượng cực kỳ lớn và số khác thì không. Tất nhiên, điều này là do thùng không có kích thước đồng đều, và không dẫn đến bất kỳ sự mất mát chính xác nào. Tuy nhiên, việc mất độ chính xác xảy ra nếu chúng ta cố gắng bình thường hóa các thùng có kích thước không đồng đều để làm đồng phục. Điều này là do giả định rằng m/2 mẫu rơi vào bên trái và bên phải của trung tâm bin, nơi m = bin đếm. Chúng tôi có thể mô hình hóa từng thùng như một gaussian, nhưng điều này vẫn sẽ dẫn đến mất chính xác (mặc dù tối thiểu)

Vì vậy, đó là nơi tôi bị kẹt ngay bây giờ, dẫn đến câu hỏi chính này: Cách tốt nhất để triển khai một biểu đồ chấp nhận dữ liệu luồng và lưu trữ từng mẫu trong các thùng có kích thước đồng đều?

Answer 1

Giữ bốn biến.

int N; // assume for simplicity that N is even 
int count[N]; 
double lower_bound; 
double bin_size; 

Khi mẫu mới x đến, hãy tính double i = floor(x - lower_bound)/bin_size. Nếu i >= 0 && i < N, sau đó tăng count[i]. Nếu i >= N, sau đó liên tục tăng gấp đôi bin_size cho đến x - lower_bound < N * bin_size. Trên mỗi tăng gấp đôi, điều chỉnh số lượng (tối ưu hóa điều này bằng cách khai thác sparsity cho nhiều doublings).

for (int j = 0; j < N/2; j++) count[j] = count[2 * j] + count[2 * j + 1]; 
for (int j = N/2; j < N; j++) count[j] = 0; 

Trường hợp i < 0 là phức tạp hơn, vì chúng ta cần phải giảm lower_bound cũng như tăng bin_size (một lần nữa, tối ưu hóa cho thưa thớt hoặc điều chỉnh số lượng trong một bước).

while (lower_bound > x) { 
    lower_bound -= N * bin_size; 
    bin_size += bin_size; 
    for (int j = N - 1; j > N/2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1]; 
    for (int j = 0; j < N/2; j++) count[j] = 0; 
} 

Trường hợp ngoại lệ rất đắt nhưng chỉ xảy ra số logarit trong phạm vi dữ liệu của bạn trên kích thước thùng ban đầu.

Nếu bạn thực hiện điều này trong dấu chấm động, hãy lưu ý rằng số dấu chấm động không phải là số thực và rằng những câu như lower_bound -= N * bin_size thể hoạt động sai (trong trường hợp này, nếu N * bin_size là nhỏ hơn nhiều so lower_bound). Tôi khuyên rằng bin_size là sức mạnh của cơ số (thường là hai) mọi lúc.