追蹤req數量的算法

Question

我有一個用於註冊req的api，每個req都是在一個有數量的商店裏出售。 ex。
銷售：{時間戳：23212312312
金額：£500}

然後，我有一個函數統計負責給我在最後60秒內完成的銷售細節。 統計將返回： 平均：平均都在最後60秒 分鐘完成的銷售金額的：分在最後60秒完成 最大的銷售金額：最高金額
總和：所有的銷售金額的總和在過去60秒內
計數：在過去60年代完成的銷售數量

此功能在空間和時間上應該爲O（1）。現在，如果我們忽略空間請求，是否應該使用鏈表來存儲最近60秒內發生的銷售並不斷更新？或者當統計函數被調用時應該更新它。這怎麼可能在O（1）空間中完成？

我的解決方案： 這是我解決這個問題的方法： 每次我們賣東西的時候，都會將該項添加到鏈表中。 由於java鏈表具有指向第一個和最後一個元素的指針，因此第一個元素將指向從現在開始60秒發生的第一個銷售。當我們做銷售時，我們從列表的開頭刪除元素，直到我們在60秒內完成。當我們調用統計信息時，我們將採用當前時間 - 60秒來查找時間戳，並使用它從列表的開頭刪除元素。但是當計算最小，最大平均值和總和時，我需要在空間和時間中遍歷list => O（n）。

Answer 1

一種方法是將間隔分成1秒「桶」。 每個桶可以包含計數，總和，最小值和最大值。每次報告新的銷售時，都要更新時間戳的相應存儲桶。進行統計查詢時，彙總存儲桶以獲取總計數，總和等。另外，對於每個API調用（更新或查詢），丟棄60秒以前的存儲桶並創建新的空存儲桶以替換它們。

如果我們要作爲一個參數k桶的數量，除了銷售n的數量，然後更新單桶O(1)和查詢統計是O(k)。在幼稚的實現中更新存儲桶列表O(k)，但只有在訪問存儲桶時更新每個存儲桶才能避免這種情況。空間要求是O(k)。

對於任何固定數量的存儲桶，這會減少到每個操作的時間和空間複雜性，無論銷售量如何。

您可以調整桶間隔以在精度和計算時間之間進行折衷。