約 7,000 の金融商品があり、その終値は、理論的には、定義された期間 (たとえば、1 週間または 1 か月) にわたって特定のパーセンテージ範囲内で上下する必要があります。
これらの過去の価格を保存する内部システムにアクセスできます (リレーショナル データベースではありません!)。期間中に価格がまったく動かないか、10% 未満の製品を一覧表示するレポートを作成したいと考えています。
最初の値 (1 日目) と最後 (n 日目) の値を単純に比較することはできません。価格が最終日の値に戻る可能性があるため、製品の価格が誤検出される可能性があるためです。もちろん、その間のどこかで急上昇した可能性があります。
合理的な計算時間でこれを行うための確立されたアルゴリズムはありますか?
毎日見ないでこれを行う方法はありません。
データが次のようになっているとします。
oooo0oooo
その1日のスパイクが真ん中にあります。スパイクが発生した日をチェックしない限り、それを把握することはできません。つまり、毎日チェックする必要があります。
これを頻繁にチェックする必要がある場合 (昨年の毎日のように多数の間隔で、同じ製品セットの場合)、各アイテムの高値と安値を週/月ごとに保存できます。適切な週次および/または月次の境界を間隔の端にある生データと組み合わせることで、間隔の最小値と最大値を取得できます。
kdb にデータを追加できる場合 (つまり、読み取りアクセスが制限されていない場合)、「最後の価格変更からの日数」を新しいデータ セットとして追加することを検討してください (つまり、金融商品ごとに 1 つの数値)。毎日のタスクは、今日のマークと昨日のマークを取得し、格納されている数値を更新します。同様に、最近 (先月、昨年) の高値と安値を kdb で維持できます。最初に値を準備するために、より大きなデータセットに対してジョブを実行する必要がありますが、その後、毎日の更新に含まれるデータははるかに少なくなります。
このようなものを採用する場合は、データセットのすべてまたは一部を再実行する方法があることをお勧めします (たとえば、新しい製品を追加する場合)。
最後に、履歴は現在の価格に対して正規化されていますか? （つまり、株式分割または類似の再評価が考慮されています）。そうでない場合は、これらの不連続性を検出して分割する必要があります。
編集
生データをJavaアプリケーションに抽出するのではなく、信号処理を実装するためにkdb + / Qを使用して調査します。おっしゃるとおり高性能です。
時間間隔中の価格の最小値と最大値を追跡できる場合、これを行うことができます。これは、時間間隔が常に変更されていないことを前提としています。変化するアイテム セットの最小値と最大値を追跡する 1 つの方法は、2 つのヒープを「背中合わせに」配置することです。これと、古いアイテムを見つけて削除するために必要ないくつかのポインターを、ストア内の 1 つまたは 2 つの配列に格納できます。 . 2 つのヒープを背中合わせにするというアイデアは、Knuth の Art of Computer Programming Vol 3 の演習 31 セクション 5.2.3 にあります。Knuth はこの種の獣を Priority Dequeue と呼んでおり、これは検索可能のようです。最小値と最大値は一定のコストで利用できます。新しい価格が到着したときにそれを変更するコストは log n です。ここで、n は保管されているアイテムの数です。