1

一連の日付範囲 (開始日と終了日) と各日付範囲の値で構成されるデータセットがあるとします。たとえば、私のデータは次のようになります

Start         End           Value
2005-01-01    2005-01-31    6.54
2005-02-01    2005-02-28    5.55
2005-03-01    2005-03-31    3.67
2005-04-01    2005-04-30    2.91

これは、タプルのリストとして使用して Python に保存されます。

mydata = [(datetime.date(2005, 1, 1), datetime.date(2005, 1, 31), 6.54), 
          (datetime.date(2005, 2, 1), datetime.date(2005, 2, 28), 5.55),
          (datetime.date(2005, 3, 1), datetime.date(2005, 3, 31), 3.67),
          (datetime.date(2005, 4, 1), datetime.date(2005, 4, 30), 2.91)]

任意の日付間隔を入力として取り、値の合計を出力できる関数が必要です。たとえば、入力が の[datetime.date(2005, 2, 1), datetime.date(2005, 3, 31)]場合、出力は 9.22 (5.55 + 3.67 に等しい) になります。

ただし、入力が である場合、一致がないため[datetime.date(2005, 2, 1), datetime.date(2005, 3, 15)]、出力は になります。None

4

2 に答える 2

1

考えられる解決策の 1 つは、すべての日付 (開始と終了の両方の型) を並べ替えられたリストに格納することです。値とともに開始日と終了日の間のマッピングを維持する別のデータ構造 (おそらく辞書) があります。

検索は、指定された範囲内の並べ替えられたリスト内のすべての値を取得することで構成されます。これは、バイナリ検索で効率的に実行できます。戻り値の開始日/終了日ごとに、対応する開始日/終了日も見つける必要があります。終了日なしで開始日が見つかった場合、または開始日なしで終了日が見つかった場合、その日付範囲は検索の範囲内にないため、結果に含めるべきではありません。このステップは、辞書を使用して効率的に実装できます。

その 2 番目のステップでは、bimap を使用して、特定の日付から開始日/終了日を簡単に検索できるようにします。二分探索で見つかった日付を処理するとき、リスト内で見つけられると予想される要素を検索し、予想されるリストを維持できます。その要素が後で検索で見つかった場合は、予想されるリストから削除します。

于 2013-08-17T14:04:21.127 に答える
0

http://en.wikipedia.org/wiki/Depth-first_searchまたはhttp://en.wikipedia.org/wiki/Breadth-first_search検索を見てください。日付はノードで、値はコスト エッジです。

于 2013-08-17T14:06:07.460 に答える