リアルタイムでの時系列の平均サブセット

Question

株価のリアルタイム供給があるとします。そのサブセットの平均をどのようにして計算しますか（過去1週間など）？

これはインタビューの質問でした。私はO（n^2）でそれを行うアルゴリズムを考え出すことができますが、インタビュアーはO（n）のアルゴリズムを望んでいました。

Answer 1

便利な方法は、配列の累積合計を計算することです。

これは、累積合計配列の各エントリが以前のすべての価格の合計であることを意味します。

これは、1つの減算を使用して入力の特定のサブアレイに対して合計を生成できるので便利です。

新しい入力が到着したときは、新しい累積合計を計算するために1回の加算が必要になります（古い累積合計に新しい要素を追加するだけなので）。

Answer 2

もう1つのアプローチは、Genomicsのスキューを計算することに似ています。

過去1週間の平均を計算する場合は、移動するウィンドウの合計を含む変数を作成します。エントリが作成されると、上記のsum変数にエントリを追加し、そこから移動ウィンドウ内の最も古いエントリを減算します。ウィンドウのサイズは一定であるため、過去1週間の平均は、過去1週間のエントリ数に対する移動平均です。