「スケジュール」を最も効率的に編集するための優れたアルゴリズムは何ですか?
https://stackoverflow.com/questions/172302
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
これは小規模なスケジュール アプリ用です。2 つの「スケジュール」を効率的に比較し、相違点を見つけて、変更されたデータ行と、このテーブルを外部キーとして持つ別のテーブルのエントリのみを更新するアルゴリズムが必要です。これは大きな質問なので、すぐに答えます。どちらかを探しています 一般的なアドバイス または 具体的な解決策.
編集： 提案どおり、質問を大幅に短縮しました。
1 つのテーブルで、リソースを使用時の期間に関連付けます。
また、テーブル A の ID を外部キーとして使用する 2 番目のテーブル (テーブル B) もあります。
テーブル B に対応するテーブル A のエントリには、次の期間があります。 包含する 表Bからの期間。テーブル A のすべてのエントリがテーブル B にあるわけではありません。
ユーザーがテーブル A のリソース スケジュールを編集するためのインターフェイスを提供しています。これらは基本的に、テーブル A に新しいデータセットを提供し、それをテーブル A として扱う必要があります。 差分 DB のバージョンから。
テーブル B が指すオブジェクトをテーブル A から完全に削除した場合、そのエントリもテーブル B から削除したいと考えています。
したがって、次の 3 つのセットがあるとします。
- テーブル A (DB から) の元のオブジェクト
- テーブル B (DB から) の元のオブジェクト
- テーブル A からの編集されたオブジェクトのセット (ユーザーからのものであるため、一意の ID はありません)
次のようなアルゴリズムが必要です。
- テーブル A とテーブル B のオブジェクトを変更する必要がない場合は、それらの行をそのままにしておきます。
- 必要に応じてテーブル A に行を追加します。
- 必要に応じて、テーブル A とテーブル B から行を削除します。
- 必要に応じて、テーブル A とテーブル B の行を変更します。
適切なデータベース操作を適用できるようにオブジェクトを並べ替えるだけで、解決策としては十分です。
もう一度、次のように答えてください 具体的には または 一般的に あなたが好きなように、私はアドバイスを探していますが、誰かが完全なアルゴリズムを持っていれば、それは私の一日を楽しくするでしょう。:)
編集： lassvek への返信として、追加の詳細をいくつか提供します。
テーブル B の項目は、単に重複するのではなく、常にテーブル A の項目内に完全に含まれます。
重要なことは、 テーブル B の項目は量子化されているため、完全に内側または完全に外側に収まる必要があります。これが起こらない場合は、データ整合性エラーが発生しているため、個別に処理する必要があります。
たとえば、(短縮表現を使用するには):
Table A ID Resource Start End 01 Resource A 10/6 7:00AM 10/6 11:00AM 02 Resource A 10/6 1:00PM 10/6 3:00PM Table B ID Table_A_ID Start End 01 02 10/6 1:00PM 10/6 2:00PM
したがって、次のような動作が必要です。
- テーブル A から ID 02 を削除するか、午後 2 時から午後 3 時までに短縮する場合は、テーブル B から ID 01 を削除する必要があります。
- テーブル A ID 01 を午後 1 時に終了する位置まで拡張すると、 これら 2 つのエントリを 1 つの行にマージする必要があります。, 、テーブル B ID 01 はテーブル A ID 01 を指すようになります。
- テーブル A ID 01 から 8:00AM ～ 10:00AM を削除すると、そのエントリは 2 つのエントリに分割されるはずです。1 つは午前 7:00 ～ 8:00 で、新しいエントリ (ID 03) は午前 10:00 ～ 11:00 です。
解決
私はピリオドをよく扱ってきましたが、テーブル A と B がどのように連携するのか完全に理解できていません。おそらくそれは言葉のせいでしょう。 包摂する それはわかりません。
やってほしいことの具体例をいくつか挙げてもらえますか？
このように、テーブル A に記録されたタイムスパンには、テーブル B のタイムスパンが完全に含まれるという意味ですか?
|---------------- A -------------------|
|--- B ----| |--- B ---|
または重複しますか？
|---------------- A -------------------|
|--- B ----| |--- B ---|
それとも逆に、B のタイムスパンは A を含む/重複しますか?
これが最初のもので、B のタイムスパンがテーブル A のリンクされたタイムスパンの範囲内/同じであるとしましょう。
これは次のことを意味しますか?
* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?
以下に例を示します。
|-------------- A1 --------------| |-------- A2 --------------|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
次に、A1 を長くし、A2 を短くして移動すると、次のようになります。
|-------------- A1 ---------------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
これは、次のようにデータを変更することを意味します。
1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead
この変更はどうでしょうか。A1 は長くなりますが、B3 を完全に含めるには十分ではなく、A2 も同じように移動/短縮されます。
|-------------- A1 -----------------------------| |--- A2 --|
|---- B1 ----| |----- B2 ---| |---- B3 ----| |-- B4 --|
B3 は完全に A1 または A2 内にないので、削除しますか?
あなたがしてほしいことの具体的な例が必要です。
編集 さらに質問を
さて、どうでしょうか:
|------------------ A -----------------------|
|------- B1 -------| |------- B2 ------|
|---| <-- I want to remove this from A
これはどうですか？
どちらか：
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------| |B3| |--- B2 ---|
または：
|------------------ A1 ----| |---- A2 -----|
|------- B1 -------|
これまでの私の見解を質問とともに要約すると、次のようになります。
- A に対して次の操作を実行できるようにしたいとします。
- 短くする
- 長くする
- 隣接している場合に結合し、2 つ以上を 1 つに結合します。
- ピリオドを削除して分割することで穴を開けます。
- 上記の更新後も A 内にまだ含まれている B、必要に応じて再リンク
- 含まれていたが完全に外側になった B は削除します。
- B は収容されていたが、現在は部分的に外側にあり、 編集：これらを削除して、データの整合性を確認してください
- 上記のすべての操作では、(単にすべてを削除して新しく挿入するのではなく) データを操作に一致させるために必要な最小限の作業を実行します。
仕事から帰宅したら、機能する可能性のある C# での実装に取り組む予定です。今夜遅くにまた戻ってきます。
編集 ここでアルゴリズムを見てみましょう。
- 最初に新しいリストを最適化します (つまり、隣接するピリオドを結合するなど)
- 次の方法で、このリストをデータベース内のマスター期間と「マージ」します。
- 両方のリストのどこにあるかを追跡します（つまり、新しいものと既存のもの）あなたは
- 現在の新しい期間が現在の既存の期間より完全に前である場合は、それを追加してから次の新しい期間に移動します
- 現在の新しい期間が現在の既存の期間より完全に後である場合は、既存の期間とそのすべての子期間を削除してから、次の既存の期間に移動します。
- 2 つの期間が重なっている場合は、次の方法で現在の既存の期間が新しい期間と等しくなるように調整してから、次の新しい既存の期間に進みます。
- 新しい期間が既存の期間より前に始まる場合は、開始位置を移動するだけです
- 新しい期間が既存の期間の後に始まる場合は、差分の期間に子期間があるかどうかを確認し、それらを記憶してから、開始位置を移動します。
- もう一方の端でも同じことをします
- 「覚えている」期間がある場合は、再リンクまたは削除する必要があるかどうかを確認してください
大規模な単体テストのセットを作成し、変更のすべての組み合わせを確実にカバーする必要があります。
他のヒント
質問を2つの別々の質問に分離することをお勧めします。 最初は、「開始時刻と終了時刻を持つリソースとしてスケジュールアトムを表すとき、どのようにリソーススケジューリングについて推論するのですか？」のようなものでなければなりません。ここで、区間代数を使用するというADeptの提案は当てはまるようです。 ウィキペディアのエントリ「間隔グラフ」およびスケジューリングに関するSUNYアルゴリズムリポジトリエントリ。 2番目の質問は、データベースの質問です：「間隔をスケジュールし、2つの間隔が重複するか、または1つが別の間隔に含まれるかを示すアルゴリズムがある場合、この情報を使用して特定のスキーマのデータベースを管理するにはどうすればよいですか？」スケジューリングアルゴリズムが導入されると、データベースの問題ははるかに簡単に解決できると思います。 HTH、 ユヴァル
投稿はほとんど＆quot; too long;にあります。読みませんでした＆quot;カテゴリ-短くすると、おそらくより多くのフィードバックが得られます。
とにかく、トピック：＆quot;区間代数＆quot;
ご承知のとおり、ユーザーはテーブルAにのみ直接影響を与えることができます。C＃でプログラミングしていると仮定すると、単純なADO.Net DataSetを使用してテーブルAの変更を管理できます。新規、変更、および削除された行を適切に処理します。
さらに、テーブルBの対応するオブジェクトを自動的に削除するには、カスケード削除を定義する必要があります。
この方法で処理されない唯一のケースは、テーブルAのタイムスパンがs.tに短縮される場合です。テーブルBの対応するレコードはもう含まれません。更新ストアドプロシージャで単純にそのケースを確認するか、テーブルAで更新トリガーを定義することができます。
このためのアルゴリズムは、NewAのパス、ResourceID、StartTime、EndTimeの一致、およびOldAのどの要素がヒットしたかを追跡することを含むように思えます。次に、2つの不一致データのセット、UnmatchedNewAとUnmatchedOldAがあります。
先に進むために考えられる最も簡単な方法は、基本的にこれらを最初からやり直すことです。 UnmatchedNewAのすべてをDBに書き込み、Bの要素をUnmatchedOldAから可能な限り新しいAキー（生成されたばかりの）に転送し、そうでない場合は削除します。次に、UnmatchedOldAをすべて削除します。
多くの変更がある場合、これは確かに効率的な方法ではありません。ただし、データのサイズが圧倒的でない場合は、巧妙な最適化よりも単純さを好みます。
この最後の提案が背景なしでは意味をなすかどうかを知ることはできませんが、偶然にあなたがこのように考えなかったという偶然に：
Aコレクション全体をやり取りする代わりに、イベントリスナーなどを使用して、変更が必要な場合にのみデータモデルを更新できますか？このようにして、変更されるオブジェクトは、必要なDB操作をその場で決定できます。
