Tính trung bình di chuyển trong C++

Question

Tôi đang cố tính toán trung bình di chuyển của tín hiệu. Giá trị tín hiệu (đôi) được cập nhật vào các thời điểm ngẫu nhiên. Tôi đang tìm một cách hiệu quả để tính toán thời gian trung bình của nó trên một cửa sổ thời gian, theo thời gian thực. Tôi có thể tự làm được, nhưng nó khó hơn tôi tưởng.

Hầu hết các tài nguyên tôi tìm thấy trên internet đều tính trung bình di chuyển của tín hiệu định kỳ, nhưng cập nhật của tôi vào thời điểm ngẫu nhiên.

Có ai biết tài nguyên tốt cho điều đó không?

Cảm ơn

Answer 1

Bí quyết là như sau: Bạn nhận được cập nhật vào các thời điểm ngẫu nhiên qua void update(int time, float value). Tuy nhiên, bạn cũng cần phải theo dõi khi cập nhật rơi ra khỏi cửa sổ thời gian, do đó bạn đặt "báo thức" được gọi là time + N để xóa trước đó cập nhật từ trước đây.

Nếu điều này xảy ra trong thời gian thực, bạn có thể yêu cầu hệ điều hành để thực hiện cuộc gọi đến một phương pháp void drop_off_oldest_update(int time) được gọi tại time + N

Nếu đây là một mô phỏng, bạn không thể nhận được sự giúp đỡ từ các hệ điều hành và bạn cần phải làm điều đó bằng tay. Trong một mô phỏng, bạn sẽ gọi các phương thức với thời gian được cung cấp như một đối số (không tương quan với thời gian thực). Tuy nhiên, một giả định hợp lý là các cuộc gọi được đảm bảo để được như vậy mà các đối số thời gian đang gia tăng. Trong trường hợp này, bạn cần phải duy trì danh sách các giá trị thời gian báo thức đã được sắp xếp và cho mỗi update và read, hãy gọi cho bạn nếu đối số thời gian lớn hơn đầu danh sách báo thức.Trong khi nó là lớn hơn bạn làm việc xử lý báo động liên quan (thả ra bản cập nhật lâu đời nhất), loại bỏ đầu và kiểm tra một lần nữa cho đến khi tất cả các báo động trước khi thời gian nhất định được xử lý. Sau đó thực hiện cuộc gọi cập nhật.

Tôi cho đến nay cho rằng đó là điều hiển nhiên bạn sẽ làm gì cho tính toán thực tế, nhưng tôi sẽ giải thích chỉ trong trường hợp. Tôi giả sử bạn có một phương pháp float read (int time) mà bạn sử dụng để đọc các giá trị. Mục đích là làm cho cuộc gọi này hiệu quả nhất có thể. Vì vậy, bạn thực hiện không tính trung bình di chuyển mỗi khi phương thức read được gọi. Thay vào đó, bạn tính toán trước giá trị như lần cập nhật cuối cùng hoặc báo thức cuối cùng và "tinh chỉnh" giá trị này bằng một số thao tác dấu phẩy động để tính thời gian trôi qua kể từ lần cập nhật cuối cùng. (i. e. một số hoạt động liên tục trừ khi có lẽ xử lý một danh sách các báo động chồng chất lên).

Hy vọng điều này rõ ràng - đây phải là một thuật toán khá đơn giản và khá hiệu quả.

Tối ưu hóa tiếp theo: một trong những vấn đề còn lại là nếu một số lượng lớn cập nhật xảy ra trong cửa sổ thời gian, sau đó có một thời gian dài không đọc hoặc cập nhật. . Trong trường hợp này, thuật toán trên sẽ không hiệu quả trong việc cập nhật từng bước giá trị cho mỗi bản cập nhật sắp ngừng hoạt động. Điều này là không cần thiết vì chúng tôi chỉ quan tâm đến bản cập nhật cuối cùng ngoài cửa sổ thời gian vì vậy nếu có cách để giảm hiệu quả tất cả các bản cập nhật cũ hơn, điều đó sẽ hữu ích.

Để thực hiện việc này, chúng tôi có thể sửa đổi thuật toán để thực hiện tìm kiếm nhị phân các bản cập nhật để tìm bản cập nhật mới nhất trước cửa sổ thời gian. Nếu có ít cập nhật tương đối cần được "bỏ" thì người dùng có thể cập nhật từng bước giá trị cho từng bản cập nhật đã bị loại bỏ. Nhưng nếu có nhiều bản cập nhật cần được loại bỏ thì người ta có thể tính toán lại giá trị từ đầu sau khi gỡ bỏ các bản cập nhật cũ.

Phụ lục trên Incremental Tính: Tôi nên làm rõ những gì tôi có nghĩa là bởi tính gia tăng trên trong câu "tinh chỉnh" giá trị này bằng một vài nổi hoạt động điểm để giải thích cho thời gian trôi qua kể từ lần cập nhật cuối. Ban đầu không gia tăng tính toán:

bắt đầu với

sum = 0; 
updates_in_window = /* set of all updates within window */; 
prior_update' = /* most recent update prior to window with timestamp tweaked to window beginning */; 
relevant_updates = /* union of prior_update' and updates_in_window */, 

sau đó lặp trên relevant_updates theo thứ tự thời gian tăng:

for each update EXCEPT last { 
    sum += update.value * time_to_next_update; 
}, 

và cuối cùng

moving_average = (sum + last_update * time_since_last_update)/window_length;.

Bây giờ nếu đúng một bản cập nhật rơi khỏi cửa sổ nhưng không có bản cập nhật mới đến, điều chỉnh sum như:

sum -= prior_update'.value * time_to_next_update + first_update_in_last_window.value * time_from_first_update_to_new_window_beginning; 

(lưu ý nó là prior_update' đã timestamp của nó sửa đổi để bắt đầu của cửa sổ cuối cùng bắt đầu). Và nếu đúng một bản cập nhật vào cửa sổ nhưng không có bản cập nhật mới rơi ra, điều chỉnh sum như:

sum += previously_most_recent_update.value * corresponding_time_to_next_update. 

Như nên được rõ ràng, đây là một phác thảo thô nhưng hy vọng nó cho thấy làm thế nào bạn có thể duy trì mức trung bình như vậy mà nó là O (1) hoạt động mỗi lần cập nhật trên cơ sở khấu hao. Nhưng lưu ý tối ưu hóa thêm trong đoạn trước.Cũng lưu ý các vấn đề ổn định ám chỉ trong một câu trả lời cũ hơn, có nghĩa là các lỗi dấu phẩy động có thể tích luỹ qua một số lượng lớn các hoạt động gia tăng như vậy mà có sự phân kỳ từ kết quả của tính toán đầy đủ có ý nghĩa đối với ứng dụng.

Answer 2

Lưu ý: Rõ ràng đây không phải là cách tiếp cận này. Để nó ở đây để tham khảo về những gì là sai với cách tiếp cận này. Kiểm tra các bình luận.

CẬP NHẬT - dựa trên nhận xét của Oli ... không chắc về sự bất ổn mà anh ấy đang nói đến.

Sử dụng bản đồ đã sắp xếp "thời gian đến" so với giá trị. Khi đến của một giá trị thêm thời gian đến bản đồ được sắp xếp cùng với giá trị của nó và cập nhật trung bình di chuyển.

cảnh báo này là pseudo-code:

SortedMapType< int, double > timeValueMap; 

void onArrival(double value) 
{ 
    timeValueMap.insert((int)time(NULL), value); 
} 

//for example this runs every 10 seconds and the moving window is 120 seconds long 
void recalcRunningAverage() 
{ 
    // you know that the oldest thing in the list is 
    // going to be 129.9999 seconds old 
    int expireTime = (int)time(NULL) - 120; 
    int removeFromTotal = 0; 
    MapIterType i; 
    for(i = timeValueMap.begin(); 
    (i->first < expireTime || i != end) ; ++i) 
    { 
    } 

    // NOW REMOVE PAIRS TO LEFT OF i 

    // Below needs to apply your time-weighting to the remaining values 
    runningTotal = calculateRunningTotal(timeValueMap); 
    average = runningTotal/timeValueMap.size(); 
} 

Có ... Không đầy đủ fleshed ra nhưng bạn sẽ có được ý tưởng.

Điều cần lưu ý: Như tôi đã nói ở trên là mã giả. Bạn sẽ cần phải chọn một bản đồ thích hợp. Không loại bỏ các cặp khi bạn lặp lại thông qua vì bạn sẽ làm mất hiệu lực trình lặp và sẽ phải bắt đầu lại.
Xem bình luận của Oli bên dưới.

Answer 3

Nếu xấp xỉ là OK và có thời gian tối thiểu giữa các mẫu, bạn có thể thử lấy mẫu siêu mẫu. Có một mảng biểu diễn các khoảng thời gian khoảng cách đều nhau ngắn hơn mức tối thiểu và tại mỗi khoảng thời gian lưu trữ mẫu mới nhất đã nhận được. Khoảng thời gian càng ngắn, giá trị trung bình càng gần với giá trị thực. Khoảng thời gian không được lớn hơn một nửa mức tối thiểu hoặc có khả năng thiếu mẫu.

Answer 4

#include <map> 
#include <iostream> 

// Sample - the type of a single sample 
// Date - the type of a time notation 
// DateDiff - the type of difference of two Dates  
template <class Sample, class Date, class DateDiff = Date> 
class TWMA { 
private: 
    typedef std::map<Date, Sample> qType; 
    const DateDiff windowSize; // The time width of the sampling window 
    qType samples; // A set of sample/date pairs 
    Sample average; // The answer 

public: 

    // windowSize - The time width of the sampling window 
    TWMA(const DateDiff& windowSize) : windowSize(windowSize), average(0) {} 

    // Call this each time you receive a sample 
    void 
    Update(const Sample& sample, const Date& now) { 
    // First throw away all old data 
    Date then(now - windowSize); 
    samples.erase(samples.begin(), samples.upper_bound(then)); 

    // Next add new data 
    samples[now] = sample; 

    // Compute average: note: this could move to Average(), depending upon 
    // precise user requirements. 
    Sample sum = Sample(); 
    for(typename qType::iterator it = samples.begin(); 
     it != samples.end(); 
     ++it) { 
     DateDiff duration(it->first - then); 
     sum += duration * it->second; 
     then = it->first; 
    } 
    average = sum/windowSize; 
    } 

    // Call this when you need the answer. 
    const Sample& Average() { return average; } 

}; 

int main() { 
    TWMA<double, int> samples(10); 

    samples.Update(1, 1); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(1, 2); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(1, 3); 
    std::cout << samples.Average() << "\n"; // 1 
    samples.Update(10, 20); 
    std::cout << samples.Average() << "\n"; // 10 
    samples.Update(0, 25); 
    std::cout << samples.Average() << "\n"; // 5 
    samples.Update(0, 30); 
    std::cout << samples.Average() << "\n"; // 0 
}