reqの番号を追跡するためのアルゴリズム

Question

私はreqを登録するために使用されるapiを持っています。それぞれのreqは、ある量のショップで販売されています。 ex。
販売：{タイムスタンプ：23212312312
量：500£}

は、その後、私は私の最後の60秒で行われ、販売の詳細を与えるために責任がある機能の統計情報を持っています。戻ります 統計： 平均：最後の60秒 分間で行われたすべての販売量の平均：最大量
合計：すべての販売量の合計最後の60年代に 最大を行って販売量分最後の60秒で
件数：最後に実行された売上げ数60秒

この関数は、時空間でO（1）である必要があります。今、スペースreqを無視すると、リンクされたリストを使用して売上を最後の60秒間に格納し、それを継続的に更新する必要がありますか？統計関数が呼び出されたときに更新する必要があります。これはどのようにしてO（1）空間で行うことができますか？

私のソリューション： これは私のこの問題を解決するためのアプローチです： 私たちが何かを販売するたびに、そのアイテムをリンクリストに追加します。 java linkedlistには最初と最後の要素へのポインタがあるので、最初の要素は今から60年前に起こった最初の要素を指します。私たちが売り上げをするとき、私たちは60秒の時間枠の外に出るまで、要素をリストの最初から削除します。統計を呼び出すときには、タイムスタンプを見つけてそれを使ってリストの先頭から要素を削除するために現在の時刻 - 60秒をとります。しかし、min、max avgとsumを計算するときには、リストと=> O（n）を時間と空間の両方でループする必要があります。

Answer 1

1つのアプローチは、間隔を1秒のバケットに分割することです。 各バケットには、カウント、合計、最小、および最大値を含めることができます。新しい販売が報告されるたびに、タイムスタンプの適切なバケットを更新します。統計クエリが作成されると、バケットを集計して総計、合計などを取得します。また、各API呼び出し（更新またはクエリ）ごとに、60秒以上経過したバケットを破棄し、新しい空のバケットを作成して置き換えます。

我々は、パラメータkとしてバケットの数を含めたい場合は、販売nの数に加えて、単一のバケットを更新するO(1)で、クエリ統計がO(k)です。単純な実装では、バケットのリストを更新するのはO(k)ですが、アクセスするときに各バケットを更新するだけで回避できます。必要なスペースはO(k)です。

固定数のバケットの場合、販売数量にかかわらず、操作ごとに時間と空間の複雑さが軽減されます（O(1)）。

精度と計算時間の間のトレードオフにバケット間隔を調整できます。