用於流數據的數據結構

Question

您應該使用哪種數據結構，以便您的服務器能夠告訴您在任何時間點上一小時內處理的請求數？

例如，在10:20:23你詢問處理了多少個請求;它必須告訴你從9:20:23到現在的總數。同樣，在10:00時，它必須從9:00告訴你總數。

Answer 1

一種選擇是將所有數據存儲在按時間排序的標準動態數組中。每當有傳入的請求時，都會將其附加到數組的末尾。

要查看過去一小時內發生了多少次請求，可以對數組執行二進制搜索，以查找小時內發生的第一次請求。比較這個數組元素的索引和元素的總數會給你在那個時間窗口中的總請求數。

爲了防止數組變得太大，一種選擇是將數組視爲越來越多的環形緩衝區。每當數組中的空間用盡時，對數組中的第一個元素進行二進制搜索，在過去一小時內發生。之前的所有元素都可以被丟棄。如果將陣列存儲爲環形緩衝區，則可以通過調整開始位置以從邏輯上將其從緩衝區中刪除，從而有效地在O（1）時間內刪除所有這些元素。如果您仍然需要更多的空間，那麼您可以將環形緩衝區的大小加倍並複製舊的元素。如果你強制執行一個策略，如果在丟棄舊元素（比如75％）之後填充的緩衝區中有多個不變的部分被填滿，則總是複製所有內容，然後這需要每插入一次O（1）次。

簡而言之，您可以獲得O（1）插入和O（log n）最近一次查詢過去一小時內有多少請求的最壞情況查找。

希望這會有所幫助！