2013-08-09 48 views
5

Tôi có một số mã sử dụng bộ tích lũy Tăng cường để theo dõi giá trị trung bình trên cửa sổ cuộn - "trung bình cán". Ngoài ý nghĩa luân phiên, tôi muốn theo dõi mức tối thiểu và tối đa trên cùng một cửa sổ này.lăn tối thiểu và lăn tối đa để tăng C++?

Có cách nào để tính toán min min và rolling max với bộ tăng tốc Boost không? Tôi không thấy cách nào ...

Tôi đã thử thêm các thẻ tối thiểu và tối đa vào bộ tích lũy được sử dụng cho rolling_mean, nhưng điều đó không cho tôi những gì tôi muốn.

typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t; 

trở thành

typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t; 

Tuy nhiên, min và max cung cấp ở đây được tính trên toàn bộ ác quy, chứ không phải là giới hạn ở những cửa sổ lăn giống như giá trị trung bình.

Tăng cường documentation cho biết rằng min và max được tính trên tất cả các mẫu, không giới hạn ở cửa sổ cuộn. Họ dường như không cung cấp một cách để hạn chế hoặc trọng lượng các mẫu.

Tôi muốn báo cáo giá trị trung bình/phút/tối đa trên toàn bộ cửa sổ cuộn.

Tôi hiện đang sử dụng phiên bản Boost 1.48.0. Tôi đã xem các tài liệu hướng dẫn cho phiên bản mới nhất (1.54.0) và không thấy một min/max lăn được thực hiện ở đó.

Tôi đã tìm thấy cách không tăng cường để theo dõi sliding window minimum, nhưng điều này dường như không phải là điều tôi muốn. Tôi không muốn xóa các giá trị chỉ vì chúng lớn hơn/nhỏ hơn min/max trước đó, vì điều đó sẽ làm cho rolling_mean không chính xác.

Trả lời

6

Tôi không nghĩ một người tích lũy có thể thực hiện tối thiểu/tối đa.

Vấn đề khá đơn giản: một bộ tích lũy khá nhiều theo định nghĩa chỉ sử dụng O (1) dữ liệu - nó không lưu trữ dữ liệu đang được xử lý. Nó có thể duy trì một phút hoặc tối đa với O (1) dữ liệu, bởi vì nó chỉ đơn giản là thay đổi min/max hiện tại khi một số nằm ngoài phạm vi của min/max hiện tại.

Tuy nhiên, đối với cửa sổ, nó cần được chuẩn bị để làm điều ngược lại: khi phút hiện tại đi ra ngoài cửa sổ, cần tìm số tối thiểu mới - số nhỏ nhất tiếp theo trong cửa sổ. Tương tự như vậy cho tối đa, tất nhiên.

Bây giờ, hãy xem xét điều gì xảy ra ở mức tối thiểu nếu (ví dụ) đầu vào được sắp xếp. Mỗi lần một mục bị xóa khỏi cửa sổ, chúng tôi nhận được một giá trị tối thiểu khác. Nói cách khác, bộ tích lũy sẽ cần phải lưu trữ tất cả dữ liệu trong cửa sổ để duy trì mức tối thiểu hiện tại một cách chính xác. Tương tự như vậy, cho tối đa với đầu vào được sắp xếp theo thứ tự giảm dần.

Tóm lại, bạn không thể sử dụng bộ tích lũy cho việc này. Bạn cần phải lưu trữ tất cả dữ liệu trong cửa sổ.

+0

Cảm ơn bạn. Điều này có ý nghĩa. Có thể có một cách xung quanh điều này?Tôi có thể bằng cách nào đó "thiết lập lại" hoặc ghi đè lên tối đa hiện tại và min được lưu trữ trong ắc quy? –

0

Có thể có thuật toán thông minh hơn (trên thực tế có thể), nhưng ngoài đỉnh đầu, tôi sẽ lưu trữ cửa sổ trong bộ đệm tròn và tính toán số phút/phút tối đa theo yêu cầu. Cache kết quả và thiết lập một cờ bẩn khi cửa sổ thay đổi. Điều đó cho phép một hoạt động tích lũy O (1) và một hoạt động trích xuất O (1) được phân bổ với trường hợp xấu nhất là O (K), trong đó K là kích thước của cửa sổ.

Các vấn đề liên quan