タスクは、定期的な値のキャッシュを実装することです。より具体的に言うと、これらは銀行口座に関連するいくつかの記録です。各レコードには、日付と 1 日の位置があります。したがって、各レコードはこれらのプロパティによって比較できます。キャッシュには、クエリされた期間に関連するレコードのリストが含まれている必要があります。また、より長い期間のクエリが実行されたときに、キャッシュされた値をマージできます。
いくつかの例を考えてみましょう。特定のアカウントの履歴には 10 件のレコードがあります (日付形式は MM/dd/yyyy:
01/01/2012
02/01/2012
03/01/2012
04/01/2012
05/01/2012
06/01/2012
07/01/2012
08/01/2012
09/01/2012
10/01/2012
例 1
最初のクエリは、2012 年 2 月 15 日から 2012 年 3 月 15 日までの期間でした。
クエリ結果は単一のレコードになります:
03/01/2012
キャッシュにはレコードが含まれている必要があります: キー "02/15/2012 - 03/15/2012"、値 ["03/01/2012"]
その期間またはサブ期間 (つまり、2012 年 2 月 16 日から 2012 年 3 月 15 日) のすべてのクエリは、キャッシュから直接「2012 年 3 月 1 日」を返す必要があります。
実行された 2 番目のクエリは、2012 年 1 月 15 日から 2012 年 2 月 16 日までの期間でした。
クエリ結果は 2 つのレコードになります。
02/01/2012
03/01/2012
言及することは次のとおりです。
1) 基礎となるデータ ストレージへのクエリは、2012 年 1 月 15 日から 2012 年 2 月 14 日までの期間のみ実行する必要があります。これは、2012 年 2 月 15 日のすべてのエントリが既にキャッシュに含まれているためです。
2) 単一のキャッシュ エントリの境界は、格納されているレコードの数と共に更新されます。
結果として、キャッシュには単一のレコードが含まれている必要があります: キー "01/15/2012 - 03/15/2012"、値 ["02/01/2012", "03/01/2012"]。
次に、サブ期間のクエリは、キーでキャッシュ エントリを検索し、キャッシュから目的のレコードを選択する必要があります。
例 2
現在のキャッシュの状態は次のとおりです。
Entry 1: "01/15/2012 - 03/15/2012" => ["02/01/2012", "03/01/2012"]
Entry 2: "04/15/2012 - 05/15/2012" => ["05/01/2012"]
Entry 3: "07/02/2012 - 09/02/2012" => ["08/01/2012", "09/01/2012"]
クエリは、2012 年 1 月 1 日から 2012 年 10 月 1 日までの期間に対して実行されます。結果には、レコードのすべての履歴が含まれます:
01/01/2012
02/01/2012
03/01/2012
04/01/2012
05/01/2012
06/01/2012
07/01/2012
08/01/2012
09/01/2012
10/01/2012
キャッシュには次の 1 つのエントリが含まれている必要があります。 "05/01/2012"、"06/01/2012"、"07/01/2012"、"08/01/2012"、"09/01/2012"、"10/01/2012"]。
私はこのタスクに 1 週間挑戦していますが、そのようなキャッシュで動作する美しくシンプルなアルゴリズムを見つけることができません。
どんな助けでも感謝します。