nhận được trung bình, p95 và p99 của luồng dữ liệu

Question

Tôi có dữ liệu đến và tôi muốn tính tỷ lệ phần trăm trung bình, 95 và 99 của dữ liệu đó - tôi quan tâm nhiều nhất đến 1000 giá trị cuối cùng. Bất cứ lúc nào, tôi muốn truy vấn đối tượng này để nhận được bất kỳ giá trị nào trong ba giá trị này (điều này có thể xảy ra bất kỳ lúc nào, không chỉ khi các số được xem là 1000 là 0). Có cách nào để có được ba giá trị này mà không cần lưu giữ 1000 mẫu cuối cùng không?

Điều này không cần phải hoàn hảo để chúng tôi có thể sử dụng một số thủ thuật để có ước tính tốt. Ngoài ra, tốc độ là một mối quan tâm khác. Cảm ơn

(Tôi sẽ làm điều này trong C++ nhưng tôi không nghĩ rằng vấn đề tất cả những gì nhiều)

Answer 1

Tối thiểu, bạn sẽ cần phải duy trì một hàng đợi của 1000 yếu tố gần đây nhất.

Để duy trì mức trung bình hoạt động, duy trì tổng số hoạt động của 1000 phần tử gần đây nhất; khi bạn thêm một phần tử mới vào hàng đợi, bạn thêm giá trị của nó vào tổng số và bạn cũng trừ giá trị của phần tử cũ nhất mà bạn vừa xóa khỏi hàng đợi. Trả lại tổng số chia cho 1000 và ở đó bạn đi.

Để giữ tỷ lệ phần trăm thứ hai đang chạy, hãy duy trì hai vùng heap và giữ một số phần tử trong đống; heap "thấp hơn" có N% thấp hơn của các giá trị và heap "upper" có phần trên (1-N)% (ví dụ, phần trăm 95 phần trăm thấp hơn sẽ có 950 phần tử và phần trăm thứ 5 trên sẽ có 50 phần tử). Tại bất kỳ thời điểm nào, bạn có thể trả lại phần tử thấp nhất từ ​​heap trên, và đó là phần trăm của bạn. Khi bạn xóa phần tử khỏi hàng đợi của các giá trị gần đây, sau đó xóa giá trị khỏi vùng heap. Nếu điều này rời khỏi đống không cân bằng (ví dụ heaps thấp hơn có 951 phần tử và heap phía trên có 49 phần tử) sau đó thay đổi các phần tử để cân bằng chúng ra (vd loại bỏ phần tử trên khỏi heap thấp hơn và thêm nó vào heap phía trên).

Vì bạn muốn hai phần trăm, sử dụng ba đống - phần dưới có phần tử 950 thấp hơn, phần giữa có phần tử tiếp theo là 40, và phần trên có giá trị cao nhất 10. Trả lại phần tử thấp nhất của phần giữa cho phần trăm 95 và phần tử thấp nhất của heap trên cho phần trăm thứ 99.

Thêm và loại bỏ phần tử đống là O (lg (n)), do đó, đó là chi phí thêm một phần tử mới vào hàng đợi và ba đống: loại bỏ phần tử xếp hàng cũ nhất khỏi đống (O (lg (n)), thêm phần tử hàng đợi mới vào heap thích hợp (O (lg (n)) và cân bằng heap nếu cần (một lần nữa, O (lg (n)). Thêm phần tử mới vào heap thấp nhất có phần tử cao nhất là lớn hơn các yếu tố đống, tức là

if (newElement < lowestHeap.maxElement) { 
    lowestHeap.add(newElement) 
} else if (newElement < middleHeap.maxElement) { 
    middleHeap.add(newElement) 
} else { 
    highestHeap.add(newElement) 
} 

Hãy chắc chắn rằng khối của bạn cho phép các yếu tố trùng lặp

Answer 2

Đầu tiên chúng ta hãy giả sử bạn có thể đủ khả năng để lưu trữ 1000 số (chúng ta hãy nói k lần 1000, với k là một hằng số)

Giữ 3 đống:

1. Một minheap để lưu trữ 10 (hoặc 50) yếu tố (heapA)
2. Một maxheap để lưu trữ còn lại 990 (hoặc 950 phần tử) (heapB)
3. Một minheap để giữ trật tự của các yếu tố. Phần tử cũ nhất luôn nằm trên đỉnh của vùng heapC này)

Ba vùng đặc biệt: heapC cũng giữ liên kết đến phần tử tương ứng trong heapA hoặc heapB. heapA và heapB cũng theo dõi cùng một phần tử trong heapC.

Đây là cách nó hoạt động:

1. Giả sử bạn có 1000 thành phần trong hệ thống. heapA có 10 phần tử, heapB 990 và heapC có 1000 phần tử
2. Xóa phần tử cũ nhất khỏi hệ thống. Xóa nó khỏi heapC và sử dụng liên kết xóa nó từ heapA hoặc heapB
3. Trả lại ba heap.
4. Thêm thứ tự của phần tử mới vào heapA hoặc heapB tùy thuộc vào đầu heapA
5. Thêm thứ tự của phần tử vào heapC.
6. Trong khi thực hiện việc này, cũng thêm liên kết với nhau.