Phần trăm thu thập dữ liệu trực tiếp

Question

Tôi đang tìm một thuật toán xác định phần trăm để thu thập dữ liệu trực tiếp.

Ví dụ: hãy xem xét sự phát triển của ứng dụng máy chủ.

Các máy chủ có thể có thời gian đáp ứng như sau: 17 ms 33 ms 52 ms 60 ms 55 ms , vv

Nó rất hữu ích để báo cáo thời gian phản ứng 90 phần trăm, thời gian đáp ứng 80 phần trăm , v.v.

Thuật toán ngây thơ là chèn từng thời gian phản hồi vào danh sách. Khi yêu cầu số liệu thống kê, hãy sắp xếp danh sách và nhận các giá trị ở các vị trí thích hợp.

Mức sử dụng bộ nhớ cân bằng tuyến tính với số lượng yêu cầu.

Có một thuật toán mang lại số liệu thống kê phần trăm "gần đúng" cho việc sử dụng bộ nhớ hạn chế không? Ví dụ, giả sử tôi muốn giải quyết vấn đề này theo cách tôi xử lý hàng triệu yêu cầu nhưng chỉ muốn sử dụng một kilobyte bộ nhớ để theo dõi phần trăm (loại bỏ theo dõi các yêu cầu cũ không phải là một lựa chọn vì phần trăm được cho là được cho tất cả các yêu cầu).

Cũng yêu cầu rằng không có kiến ​​thức nào trước về phân phối. Ví dụ: tôi không muốn chỉ định bất kỳ phạm vi nhóm nào trước thời hạn.

Answer 1

Tôi tin rằng có rất nhiều thuật toán gần đúng cho vấn đề này. Một phương pháp cắt giảm tốt đầu tiên là sử dụng một mảng có kích thước cố định (nói 1K giá trị của dữ liệu). Sửa một số xác suất p. Đối với mỗi yêu cầu, với xác suất p, ghi thời gian đáp ứng của nó vào mảng (thay thế thời gian cũ nhất trong đó). Kể từ khi mảng là một subsampling của dòng sống và kể từ khi subsampling bảo tồn phân phối, làm các số liệu thống kê trên mảng đó sẽ cung cấp cho bạn một xấp xỉ của các số liệu thống kê của dòng đầy đủ, sống.

Cách tiếp cận này có một số ưu điểm: nó không yêu cầu thông tin ưu tiên và dễ dàng mã hóa. Bạn có thể xây dựng nó một cách nhanh chóng và xác định bằng thực nghiệm, cho máy chủ cụ thể của bạn, tại điểm phát triển bộ đệm nào chỉ có một hiệu ứng không đáng kể đối với câu trả lời. Đó là điểm mà xấp xỉ là chính xác.

Nếu bạn thấy rằng bạn cần quá nhiều bộ nhớ để cung cấp cho bạn số liệu thống kê đủ chính xác, thì bạn sẽ phải đào sâu hơn nữa. Từ khóa tốt là: "tính toán luồng", "thống kê luồng" và tất nhiên là "phần trăm". Bạn cũng có thể thử phương pháp tiếp cận "ire và curses".

Answer 2

Nếu bạn muốn giữ mức sử dụng bộ nhớ không đổi khi bạn nhận được nhiều dữ liệu hơn, thì bạn sẽ phải resample dữ liệu đó bằng cách nào đó. Điều đó ngụ ý rằng bạn phải áp dụng một số loại lược đồ rebinning. Bạn có thể đợi cho đến khi bạn nhận được một số lượng đầu vào thô nhất định trước khi bắt đầu rebinning, nhưng bạn không thể tránh nó hoàn toàn.

Câu hỏi của bạn thực sự hỏi "cách tốt nhất để tự động nhập dữ liệu của tôi" là gì? Có rất nhiều cách tiếp cận, nhưng nếu bạn muốn giảm thiểu giả định về phạm vi hoặc phân phối giá trị bạn có thể nhận được, thì phương pháp đơn giản là trung bình trên các nhóm có kích thước cố định k, với chiều rộng phân phối lôgarit. Ví dụ: giả sử bạn muốn giữ 1000 giá trị trong bộ nhớ cùng một lúc. Chọn kích thước cho k, hãy nói 100. Chọn độ phân giải tối thiểu của bạn, hãy nói 1ms. Sau đó

• Các xô đầu tiên giao dịch với giá trị giữa 0-1ms (width = 1ms)
• Thứ hai xô: 1-3ms (w = 2ms)
• Thứ ba xô: 3-7ms (w = 4ms)
• Fourth xô: 7-15ms (w = 8ms)
• ...
• Tenth xô: 511-1023ms (w = 512ms)

Đây là loạiCách tiếp cậntương tự như các hệ thống chunking được sử dụng trong hash table algorithms, được sử dụng bởi một số hệ thống tập tin và thuật toán phân bổ bộ nhớ. Nó hoạt động tốt khi dữ liệu của bạn có phạm vi động lớn.

Khi có giá trị mới, bạn có thể chọn cách bạn muốn định lại mẫu, tùy thuộc vào yêu cầu của bạn. Ví dụ: bạn có thể theo dõi một moving average, sử dụng first-in-first-out hoặc một số phương pháp tinh vi hơn khác.Xem thuật toán Kademlia cho một phương pháp (được sử dụng bởi Bittorrent).

Cuối cùng, việc rebinning phải mất một số thông tin. Lựa chọn của bạn liên quan đến việc binning sẽ xác định các chi tiết cụ thể của những thông tin bị mất. Một cách khác để nói điều này là lưu trữ bộ nhớ kích thước không đổi ngụ ý sự cân bằng giữa dynamic range và sampling fidelity; cách bạn thực hiện việc giao dịch đó tùy thuộc vào bạn, nhưng cũng giống như bất kỳ vấn đề lấy mẫu nào, không có sự kiện cơ bản nào xảy ra.

Nếu bạn thực sự quan tâm đến ưu và nhược điểm, thì không có câu trả lời nào trên diễn đàn này có thể hy vọng là đủ. Bạn nên xem xét sampling theory. Có rất nhiều nghiên cứu về chủ đề này.

Đối với những gì đáng giá, tôi nghi ngờ rằng thời gian máy chủ của bạn sẽ có phạm vi động tương đối nhỏ, vì vậy việc mở rộng thoải mái hơn để cho phép lấy mẫu giá trị phổ biến cao hơn có thể mang lại kết quả chính xác hơn.

Chỉnh sửa: Để trả lời nhận xét của bạn, đây là ví dụ về thuật toán binning đơn giản.

• Bạn lưu trữ 1000 giá trị, trong 10 thùng. Mỗi thùng chứa 100 giá trị. Giả sử mỗi bin được thực hiện như là một mảng động (một 'danh sách', trong thuật ngữ Perl hoặc Python).

• Khi một giá trị mới do thỏa thuận hợp:

  • Xác định bin nó phải được lưu trữ trong, căn cứ vào giới hạn bin bạn đã chọn.
  • Nếu thùng chưa đầy, hãy thêm giá trị vào danh sách bin.
  • Nếu thùng đầy, hãy xóa giá trị ở đầu danh sách thùng và thêm giá trị mới vào cuối danh sách bin. Điều này có nghĩa là các giá trị cũ được vứt bỏ theo thời gian.

• Để tìm phần trăm thứ 90, sắp xếp thùng 10. Phần trăm thứ 90 là giá trị đầu tiên trong danh sách được sắp xếp (phần tử 900/1000).

Nếu bạn không thích vứt bỏ các giá trị cũ, bạn có thể triển khai một số phương án thay thế để sử dụng thay thế. Ví dụ, khi một thùng chứa đầy (đạt 100 giá trị, trong ví dụ của tôi), bạn có thể lấy trung bình của 50 thành phần cũ nhất (tức là 50 phần tử đầu tiên trong danh sách), loại bỏ các phần tử đó rồi thêm phần tử trung bình mới vào thùng rác, để lại cho bạn một thùng 51 yếu tố hiện có không gian chứa 49 giá trị mới. Đây là một ví dụ đơn giản về rebinning.

Ví dụ khác về rebinning là downsampling; vứt bỏ mọi giá trị thứ năm trong một danh sách được sắp xếp, ví dụ.

Tôi hy vọng ví dụ cụ thể này sẽ giúp ích. Điểm mấu chốt để lấy đi là có rất nhiều cách để đạt được một thuật toán lão hóa bộ nhớ liên tục; chỉ bạn mới có thể quyết định những gì đạt yêu cầu.

Answer 3

Sử dụng mảng động T [] của số nguyên lớn hoặc thứ gì đó mà T [n] đếm số lần thời gian phản hồi là n mili giây. Nếu bạn thực sự đang làm thống kê trên một ứng dụng máy chủ thì có thể 250 ms thời gian đáp ứng là giới hạn tuyệt đối của bạn. Vì vậy, 1 KB của bạn giữ một số nguyên 32 bit cho mỗi ms giữa 0 và 250, và bạn có một số phòng để phụ tùng cho một thùng tràn. Nếu bạn muốn một cái gì đó có nhiều thùng hơn, hãy đi với số 8 bit cho 1000 thùng và thời điểm bộ đếm sẽ tràn (tức làYêu cầu thứ 256 tại thời gian phản hồi đó) bạn chuyển các bit trong tất cả các thùng xuống 1. (giảm một nửa giá trị hiệu quả trong tất cả các thùng). Điều này có nghĩa là bạn bỏ qua tất cả các thùng chứa ít hơn 1/127th của sự chậm trễ mà các thùng rác được truy cập nhiều nhất.

Nếu bạn thực sự, thực sự cần một bộ thùng cụ thể, tôi khuyên bạn nên sử dụng ngày đầu tiên yêu cầu để đưa ra một bộ thùng cố định hợp lý. Bất cứ điều gì năng động sẽ là khá nguy hiểm trong một ứng dụng trực tiếp, hiệu suất nhạy cảm. Nếu bạn chọn con đường đó bạn nên biết những gì bạn đang làm, hoặc một ngày bạn sẽ được gọi ra khỏi giường để giải thích tại sao bộ theo dõi thống kê của bạn đột nhiên ăn 90% CPU và bộ nhớ 75% trên máy chủ sản xuất.

Đối với các thống kê bổ sung: Đối với giá trị trung bình và phương sai có một số nice recursive algorithms chiếm rất ít bộ nhớ. Hai số liệu thống kê này có thể đủ để phân phối bởi vì central limit theorem nói rằng các bản phân phối phát sinh từ một số lượng lớn các biến độc lập tiếp cận phân phối chuẩn (được định nghĩa đầy đủ bằng giá trị trung bình và phương sai). số normality tests trên N cuối cùng (trong đó N đủ lớn nhưng bị ràng buộc bởi các yêu cầu bộ nhớ của bạn) để theo dõi thời tiết giả định về tính bình thường vẫn giữ.

Answer 4

Tôi vừa xuất bản một số blog post on this topic. Ý tưởng cơ bản là giảm yêu cầu cho phép tính chính xác có lợi cho "95% phần trăm phản hồi mất 500ms-600ms trở xuống" (cho tất cả các tỷ lệ phần trăm chính xác 500ms-600ms)

Bạn có thể sử dụng bất kỳ số lượng nhóm nào bất kỳ kích thước tùy ý nào (ví dụ: 0ms-50ms, 50ms-100ms, ... bất kỳ thứ gì phù hợp với hệ thống của bạn). Thông thường, không phải là vấn đề với tất cả các yêu cầu vượt quá thời gian phản hồi nhất định (ví dụ: 5 giây đối với ứng dụng web) trong nhóm cuối cùng (tức là> 5000ms).

Đối với mỗi thời gian phản hồi mới được ghi lại, bạn chỉ cần tăng bộ đếm cho nhóm nó rơi vào. Để ước tính tỷ lệ phần trăm thứ n, tất cả những gì cần thiết là tổng hợp các bộ đếm cho đến khi tổng vượt quá n phần trăm của tổng số.

Cách tiếp cận này chỉ yêu cầu 8 byte mỗi nhóm, cho phép theo dõi 128 nhóm bằng 1K bộ nhớ. Quá đủ để phân tích thời gian phản hồi của một ứng dụng web bằng cách sử dụng độ chi tiết 50ms).

Như một ví dụ, đây là một Google Chart tôi đã tạo ra từ 1 giờ dữ liệu bị bắt (sử dụng 60 quầy với 200ms mỗi thùng):

response times http://j.mp/3bTf36

Nice, phải không?:) Read more on my blog.

Answer 5

Hãy thử thuật toán đơn giản được xác định trong bài báo “Quy trình tuần tự để ước lượng đồng thời một số phần trăm” (Raatikainen). Tốc độ nhanh, yêu cầu 2 * m + 3 điểm đánh dấu (đối với phần trăm m) và có xu hướng gần đúng nhanh chóng.

Answer 6

(Đã khá lâu kể từ khi câu hỏi này được hỏi, nhưng tôi muốn chỉ ra một vài tài liệu nghiên cứu có liên quan)

Hiện đã có một số lượng đáng kể của nghiên cứu trên percentiles gần đúng của dòng dữ liệu trong Vai năm vưa qua. Một vài giấy tờ thú vị với các định nghĩa thuật toán đầy đủ:

• A fast algorithm for approximate quantiles in high speed data streams

• Space-and time-efficient deterministic algorithms for biased quantiles over data streams

• Effective computation of biased quantiles over data streams

Tất cả những giấy tờ đề xuất các thuật toán với độ phức tạp không gian phụ tuyến tính cho tính toán các phần trăm gần đúng trên luồng dữ liệu.