算法在過去一段時間

Question

內收集的事件總數我面臨的一個算法問題。

我們有運行每隔10ms和運行過程中，一個事件可以發生或沒有發生的任務。有沒有簡單的算法可以讓我們跟蹤事件在最近1秒鐘內觸發多少次？

是我唯一的想法就是實現一個數組，並保存所有的事件。正如我們在嵌入式系統編程，沒有足夠的空間...提前

感謝。

Answer 1

你需要某種形式的列表/隊列等，但ringbuffer有可能是最好的性能。 您需要存儲100個計數器（在最後一秒內每個時間間隔爲10毫秒）和一個當前計數器。

Ringbuffer解決方案： （我使用僞代碼）。

創建100個計數器的counter_array（最初用0填充的）。

int[100] counter_array; 
current_counter = 0 

在10毫秒週期：

counter_array[current_counter] = 0; 
current_counter++; 

對於每一個事件：

counter_array[current_counter]++ 

要在過去的支票事件的數量，採取counter_array的總和

Answer 2

你能買得起100個布爾值的數組嗎？也許作爲一個領域？只要你能負擔得起的成本的空間，就可以跟蹤恆定的時間事件的數量：

1. 商店：
   1. 的計數器C，最初0
   2. 布爾B的陣列的大小等於你想跟蹤的間隔數，即100，最初都是假的。
   3. 索引I，最初0
2. 每個時間間隔：
   1. 閱讀在B [i]於布爾，和減量c如果這是真的。
   2. 設置布爾在B [i]於爲true，如果發生在這個間隔中的事件，否則爲假。
   3. 增量C如果事件發生在這個時間間隔。
3. 當I達到100時，復位爲0。

這樣，你至少避免掃描整個陣列的每個時間間隔。

---

編輯 - 好了，你想在最後3分鐘（180秒，18000個區間）來跟蹤事件。利用上述算法和填鴨式的布爾成位字段，需要總存儲：

2 byte unsigned integer for C 
2 byte unsigned integer for I 
2250 byte bit-field for B 

，如果你需要有事件的數量的精確計數在最後180.0秒在所有這幾乎是不可避免的倍。我不認爲要證明您需要所有這些信息才能夠隨時提供準確答案並不困難。但是，如果您只能瞭解最近180 +/- 2秒內的事件數量，則可以改爲縮短時間分辨率。這裏有一個詳細的例子，展開下面的評論。

上述算法概括：

1. 商店：
   1. 的計數器C，最初0
   2. 計數器B的陣列，大小等於要跟蹤間隔的數量的，即，100，最初所有0
   3. 索引I，最初0
2. 每個時間間隔：
   1. 閱讀B [i]，並將C減少該量。
   2. 將發生此間隔的事件數寫入B [i]。
   3. 按此間隔發生的事件數量遞增C.
3. 當我到達B的長度，將其重置爲0。

如果要切換的時間間隔爲2秒，然後在那個時候可能發生0-200事件。所以數組中的每個計數器都可以是一個無符號的單字節整數。在3分鐘內你會有90個這樣的間隔，所以你的數組需要90個元素= 90個字節。

如果將間隔切換爲150ms，那麼在此期間可能會發生0-15個事件。如果你按下空格鍵，你可以把它塞進一個半字節的無符號整數。你會在3分鐘內有1200個這樣的間隔，所以你的數組需要1200個元素= 600個字節。

Answer 3

13個字節的數組，用於10ms步驟中的第二個事件。

考慮它的104位標記0毫秒的陣列，以104MS如果發生事件標記位和增量到下一個時間

，否則只遞增到下一個比特/字節。

如果您希望...每秒鐘後運行長度編碼將事件位卸載到另一個值中。 或......將其視爲循環緩衝區，並保持計數可用於查詢。 或兩者兼有

您可以減小陣列大小以匹配可用空間。

不清楚在任務運行時事件是否會多次發生，或者事件之間總是有10ms。

Answer 4

請問以下工作適合您嗎？

滾動事件計數器，可以增加每個事件。

在每10ms運行一次的例程中，將當前事件計數器值與上次運行例程時存儲的事件計數器值進行比較。

這會告訴您在10ms窗口期間發生了多少事件。

Answer 5

這是更多或更少什麼Dtyree和Weeble所建議的，但是一個示例性實現可以幫助（爲了圖示的C代碼）：

#include <stdint.h> 
#include <stdbool.h> 

#define HISTORY_LENGTH 100 // 1 second when called every 10ms 

int rollingcount(bool event) 
{ 
    static uint8_t event_history[(HISTORY_LENGTH+7)/8] ; 
    static int next_history_bit = 0 ; 
    static int event_count = 0 ; 

    // Get history byte index and bit mask 
    int history_index = next_history_bit >> 3 ;    // ">> 3" is same as "/ 8" but often faster 
    uint8_t history_mask = 1 << (next_history_bit & 0x7) ; // "& 0x07" is same as "% 8" but often faster 

    // Get current bit value 
    bool history_bit = (event_history[history_index] & history_mask) != 0 ; 

    // If oldest history event is not the same as new event, adjust count 
    if(history_bit != event) 
    { 
     if(event) 
     { 
      // Increment count for 0->1 
      event_count++ ; 

      // Replace oldest bit with 1 
      event_history[history_index] |= history_mask ; 
     } 
     else 
     { 
      // decrement count for 1->0 
      event_count-- ; 

      // Replace oldest bit with 0 
      event_history[history_index] &= ~history_mask ; 
     } 
    } 

    // increment to oldest history bit 
    next_history_bit++ ; 
    if(next_history_bit >= HISTORY_LENGTH) // Could use "next_history_bit %= HISTORY_COUNT" here, but may be expensive of some processors 
    { 
     next_history_bit = 0 ; 
    } 

    return event_count ; 
} 

對於100樣品歷史，它需要13個字節加上兩個靜態分配內存的整數，我已經使用int作爲通用性，但在這種情況下，uint8_t計數器就足夠了。另外還有三個堆棧變量，如果需要真正優化內存使用，則不需要使用int。所以總共可以使用15個字節加上3個字節的堆棧。 event參數可能會或可能不會傳遞到堆棧上，然後是函數調用返回地址，但又取決於您的編譯器/處理器的調用約定。