c# - 重複する日付範囲を分割する最速の方法

Question

次の3つの（関連するのみの）列を持つSQLDBテーブルに日付範囲データがあります。

ID（intアイデンティティ）
RangeFrom（日付のみ）
RangeTo（日付のみ）

任意の日付範囲で、（完全にまたは部分的に）重複する可能性のある任意の数のレコードが存在する可能性があります。

条件

より高い（新しいレコード）を持つすべてのレコードは、ID（完全にまたは部分的に）オーバーラップする可能性がある古いレコードよりも優先されます
RangeFrom範囲は少なくとも1日です（1日RangeTo異なります）

したがって、特定の日付範囲（つまり、5年以内）では、次のことを行う必要があります。

この範囲に該当するすべての範囲レコードを（完全にまたは部分的に）取得します
これらのオーバーラップをオーバーラップしない範囲に分割します
これらの新しい重複しない範囲を返します

私の見解

これらの範囲に関連する複雑なデータがたくさんあり（多くの結合など）、プロセッサとメモリの能力がSQL DBエンジンよりもはるかに効率的であるため、重複するデータをDBからデータレイヤーにロードして範囲を切り刻むことにしました。 /メモリ内で分割します。これにより、開発と実行の面ではるかに柔軟性とスピードが得られます。

これをDBでより適切に処理する必要があると思われる場合は、お知らせください。

質問

私は最速で、可能であればリソースを必要としない変換アルゴリズムも作成したいと思います。これらのレコードはたくさんあり、さまざまなユーザーに関連しているため、ユーザーごとにこのアルゴリズムを実行し、重複する範囲データのセットを実行する必要があります。

これらの重複する範囲を分割する最も効率的な（高速でリソースを必要としない）方法は何でしょうか？

サンプルデータ

この方法で視覚的に重複するレコードID=1がID=5あります（日付は実際には無関係です。この方法でこれらの重複をより適切に示すことができます）。

       6666666666666
                44444444444444444444444444         5555555555
          2222222222222            333333333333333333333            7777777
11111111111111111111111111111111111111111111111111111111111111111111

結果は次のようになります。

111111166666666666664444444444444444444444333333333555555555511111117777777

結果は、実際には、これらのオーバーラップを上から見て、このトップダウンビューから見えるIDを取得するように見えます。

結果は実際には新しい範囲レコードに変換されるため、古いIDは無関係になります。ただし、それらの値RangeFromとRangeTo値（および関連するすべてのデータ）が使用されます。

111111122222222222223333333333333333333333444444444555555555566666667777777

もちろん、これは重複する範囲の単なる例です。任意の日付範囲で、0レコードからXまでの任意の値にすることができます。ご覧のとおり、範囲ID = 2は4と6で完全に上書きされたため、完全に廃止されました。

score 5 · Accepted Answer

null許容整数の配列はどうですか

私は自分のアイデアを思いついた：

指定された日付範囲に対して、範囲内の日数と同じ数の項目を含む整数のメモリ内配列を作成します。
配列にnull値を入力します。それらのすべて。
IDでレコードを逆の順序で並べ替える
順序付けられたレコードを反復処理して重複する範囲をフラット化し、各アイテムに対して次の手順を実行します。
1. アイテムを入手
2. 配列の開始オフセットと終了オフセットを計算します（日数の差）
3. これら2つのオフセット間のすべての配列値をアイテムIDに設定しますが、値がnull
4. 手順4.1に進みます
平坦化された範囲の配列になり、レコードIDで埋められます
新しいレコードのセットを作成し、配列のIDが変更されたときに新しいレコードを作成します。各レコードは、配列に設定されているレコードIDに関連付けられたデータを使用する必要があります
次の人とその重複する範囲のセットに対してすべてを繰り返します（同じ配列を再利用することを忘れないでください）。=手順2に戻ります。

基本的には以上です。

与えられた10年の日付範囲には、約10年の配列が必要です。int3650 null許容整数。これはメモリフットプリントがかなり小さいと思います（各整数は4バイトを使用しますが、とを含むnull許容整数を占めるスペースの量はわかりませんが、bool合計で3650 * 8=28.52kとなる8バイトを想定します。）そしてメモリ内で簡単かつかなり高速に操作できます。日付範囲や分割などは保存していないので、値がすでに設定されているかどうかをチェックするifを使用した代入操作にすぎません。

10年の日付範囲は、まれに誇張された極端なものです。日付範囲の75％は1年の3か月または四半期（90日*8バイト=720バイト）内にあり、99％は1年の範囲（365 * 8 =2920バイト=2,85k）になります。

このアルゴリズムは、重複する日付範囲を平坦化するのに適していると思います。

メモリフットプリントを半分にするために、の代わりに使用してint、の代わりに設定int?することができます。-1null

時期尚早の反復ループブレークの可能性

設定されていない日数を保持することもできます。0に達すると、残りのすべての範囲が完全にオーバーラップし、配列にそれ以上値を設定しないため、ループを簡単に中断できます。したがって、範囲レコードがたくさんある場合（これはかなりまれです）、これによって少しスピードアップすることさえあります。

score 2 · Accepted Answer

.NET用の無料の期間ライブラリには、さまざまな重複する時間範囲と交差するツールTimePeriodIntersectorが含まれています。

アルゴリズムはタイムラインを使用し、時間範囲内のすべての瞬間を列挙します（瞬間ごとの開始/終了ポイントをカウントします）。

// ----------------------------------------------------------------------
public void TimePeriodIntersectorSample()
{
  TimePeriodCollection periods = new TimePeriodCollection();

  periods.Add( new TimeRange( new DateTime( 2011, 3, 01 ), new DateTime( 2011, 3, 10 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 05 ), new DateTime( 2011, 3, 15 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 12 ), new DateTime( 2011, 3, 18 ) ) );

  periods.Add( new TimeRange( new DateTime( 2011, 3, 20 ), new DateTime( 2011, 3, 24 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 22 ), new DateTime( 2011, 3, 28 ) ) );
  periods.Add( new TimeRange( new DateTime( 2011, 3, 24 ), new DateTime( 2011, 3, 26 ) ) );

  TimePeriodIntersector<TimeRange> periodIntersector =
                    new TimePeriodIntersector<TimeRange>();
  // calculate intersection periods; do not combine the resulting time periods
  ITimePeriodCollection intersectedPeriods = periodIntersector.IntersectPeriods( periods, false );

  foreach ( ITimePeriod intersectedPeriod in intersectedPeriods )
  {
    Console.WriteLine( "Intersected Period: " + intersectedPeriod );
  }
  // > Intersected Period: 05.03.2011 - 10.03.2011 | 5.00:00
  // > Intersected Period: 12.03.2011 - 15.03.2011 | 3.00:00
  // > Intersected Period: 22.03.2011 - 24.03.2011 | 2.00:00
  // > Intersected Period: 24.03.2011 - 26.03.2011 | 2.00:00
} // TimePeriodIntersectorSample

IDマッピングは簡単な作業です。

score 1 · Accepted Answer

それがどれほど役立つかはよくわかりませんが、これにアプローチする方法は...（最初は理解しやすいように最適化されていません...）

テーブルマッピングを[ID->range]から[date->IDのリスト]に変換します。

（日付で並べ替え、各日付-開始または終了に関係なく、次の日付まで到達する時間範囲の開始です。）テーブルが次のようになるようにします。

        |666|666666|6666|
        |   |      |4444|444|444444444444|4444444|         |55555|55555|
        |   |222222|2222|222|            |3333333|333333333|33333|     |       |7777777
 1111111|111|111111|1111|111|111111111111|1111111|111111111|11111|11111|1111111|

 1234567|890|123456|7890|123|4


 1 -> 1
 8 -> 1,6
 11 -> 6,2,1
 17 -> 6,4,2,1
 21 -> 4,2,1
 24 -> 4,1
 ...

各リストで最大の要素を選択します
同じ最大値を持つ次のレコードを連結します。

最終的なデータベースには重複するIDがあるため（この例では「1」は2つのセグメントに分割されます）、データベースをID->範囲ではなく日付->ID形式に維持することをお勧めします。

明らかな最適化のために、もちろん、各日付レコードでIDのリストを保持しないでください。日付->IDテーブルにnullIDを入力し、最終レコードを入力しながら、これまでに見つかった最大値のレコードを置き換えます。

すべての日付エントリのテーブルを作成します、[日付-> ID]
元のテーブルのレコードごとに：
- からの範囲で日付を選択します。
- ID値がnullまたは現在チェックされているレコードIDよりも小さい場合は、現在のIDを入力します。
次に連結します-次のレコードが前と同じIDを持っている場合は、次を削除します。
最後に、ビットを非正規化し、範囲の2つの連続するレコードの抽出を[date-> ID、length]または[date-> ID、end_date]に置き換えたい場合があります。

新しいレコードの追加は、作成操作の1回の反復と同じです。一方、レコードを削除するのはかなり難しいようです。

score 0 · Accepted Answer

事実上、データをスタックし、スタックから最大値を選択します。私は以前にこれに似たものを実装する必要があり、私たちが使用したアプローチはあなたが必要とするよりも少し柔軟性を与えてくれたので、これを行うのは適切ではないかもしれません：

レコードを管理するためのオブジェクトを用意し、各レコードをこのオブジェクトに追加します。レコードが追加されたら、新しい日付範囲を作成し、レコードの値を範囲に関連付けます。次に、範囲が他の既存の範囲と重複していないかどうかを確認します。オーバーラップする場合は、オーバーラップごとに新しい範囲を作成し、両方/すべてのすべての値を関連付けます（各範囲を追加するときに行うか、シングルパスで行うかによって異なります）、オーバーラップした範囲を新しい範囲に関連付けます。これは、データを追加するときに実行することも、すべてのデータが追加されたら1回のパスで実行することもできます。

最後に、上の図のように、それぞれに関連付けられた値のコレクションを持つ一意の範囲を含むオブジェクトがあります。

       | 666 | 666666 | 6666 |
       | | | 4444 | 444 | 444444444444 | 4444444 | | 55555 | 55555 |
       | | 222222 | 2222 | 222 | | 3333333 | 333333333 | 33333 | | | 7777777
1111111 | 111 | 111111 | 1111 | 111 | 111111111111 | 1111111 | 111111111 | 11111 | 11111 | 1111111 |

次に、値のコレクションを持つ一意の範囲を単一の値を持つ一意の範囲に変換するフラット化関数（おそらく戦略パターンを使用）をクラスに提供できます。これにより、最終的に同じ値になる範囲が明らかに連結されます。

それぞれの一意の範囲から最大値を選択するクラスが必要ですが、最小値の選択、値の合計、平均化、カウントなども必要になる場合があります。これらの各オプションは、異なる実装を渡すことで実行できます。戦略の。

私が言ったように、このアプローチは最大値のみを選択するアプローチよりも効率が悪いかもしれません。その場合、すべての値をスタックに保持する必要がないためですが、実装は私が覚えているようにかなり簡単でした。

c# - 重複する日付範囲を分割する最速の方法

条件

したがって、特定の日付範囲（つまり、5年以内）では、次のことを行う必要があります。

私の見解

質問

サンプルデータ

4 に答える 4

null許容整数の配列はどうですか

時期尚早の反復ループブレークの可能性

Related

Reference