2

日付範囲を扱うコードに取り組んでいます。その範囲の特定の価格を設定するために、開始日と終了日を持つ価格設定アクティビティがあります。交差する日付範囲を持つ複数の価格設定アクティビティがあります。

最終的に必要なのは、日付範囲の有効な価格を照会する機能です。(jan1,jan31) を渡すと、jan1-->jan10 $4 、jan11-->jan19 $3 jan20-->jan31 $4 というリストが返されます。

価格設定活動には優先順位があります。一部のタイプの価格設定アクティビティは優先度が高いため、他の価格設定アクティビティを上書きし、特定のタイプの価格設定アクティビティでは最低価格が優先されます。

私は現在、これらの価格設定アクティビティを保持し、解決済みの価格カレンダーを保持するクラスを持っています。新しい価格設定アクティビティを追加すると、解決されたカレンダーが更新されます。より多くのテスト/コードを作成するにつれて、すべての異なるケース (さまざまな方法で交差する価格設定アクティビティ) で非常に複雑になり始めました。新しく追加された価格設定アクティビティを解決する非常に複雑なコードになってしまいました。以下の方法を参照してくださいAddPricingActivity()。

これに対処するより簡単な方法を考えられる人はいますか? どこかに同様のコードがあるでしょうか？

Public class PricingActivity()
{
    DateTime startDate;
    DateTime endDate;
    Double price;

    Public bool StartsBeforeEndsAfter (PricingActivity pAct)
    {
        // pAct covers this pricing activity
    }
    Public bool StartsMiddleEndsAfter (PricingActivity pAct){
        // early part of pAct Itersects with later part of this pricing activity 
    }
    //more similar methods to cover all the combinations of intersecting
}
Public Class PricingActivityList()
{
    List<PricingActivity> activities;
    SortedDictionary<Date, PricingActivity> resolvedPricingCalendar;
    Public void AddPricingActivity(PricingActivity pAct)
    {
        //update the resolvedCalendar
        //go over each activity and find intersecting ones 
        //update the resolved calendar correctly
        //depending on the type of the intersection
        //this part is getting out of hand…..
    }
}
4

3 に答える 3

2

シンプルなライン スイープアルゴリズムが探しているものです。基本的に：

  • 価格設定アクティビティのすべての開始点と終了点を一連の「イベント」に分類します。
  • この配列をステップ実行すると、基本的に、発生した各価格設定の「イベント」が取得されます (価格設定期間の開始または終了)。
  • この配列を順番にスキャンすると、特定の日付に有効なアクティビティのリストを維持できます。

したがって、任意の日付範囲を指定すると、次のことができます。

  1. 空の「現在の活動セット」を使用して、配列の先頭から開始します。
  2. 配列内の各要素を見てください。それが開始点である場合は、そのアクティビティを現​​在のセットに追加します。それが終点の場合は、そのアクティビティをセットから削除します。
  3. 希望する日付範囲に達するまでスイープを続けます。
  4. 「出力範囲」を通過すると、セット内のアクティビティに基づいて有効な価格を生成できます。イベントステップごとに価格を再計算します。
  5. 目的の範囲を超えてスキャンしたら、完了です。

この方法では、潜在的なサイズのアクティビティ交差のセットを維持する必要がなくn!、単一のO(n*a)パスで有効な価格表を生成できます (a現在のセット内のアクティビティの平均数です。それが小さい/一定である場合は線形に十分近いです)。 ）。

于 2010-04-09T23:55:59.423 に答える
1

いくつかの提案：-

  1. これからDateTimeRangeを抽象化します。ここではなく、再利用可能なDateTimeRangeクラスでオーバーラップ、交差、およびユニオンを計算するすべての作業を実行します。

  2. 挿入、更新、削除で2つのデータ構造（ソース情報と解決されたカレンダーの両方）を更新しようとしないでください。代わりに、ソースデータを更新してから、他の人が提案しているように、単純なスイープアルゴリズムを使用して解決された情報を再計算してください。ソースデータの変更の間に解決されたカレンダーをキャッシュする必要がある場合は、それを実行します（ソースが変更されるたびにキャッシュされたコピーをクリアして再計算します）。そうでない場合は、CPUではなくメモリが最近のボトルネックであり、最適化を行う必要があるため、毎回再計算します。必要な場合のみ。

于 2010-04-10T00:34:24.587 に答える
0

実装でき、ソート可能IComparable<T>になります。PricingActivity私があなたを正しく理解していれば、範囲の開始、次に優先度でソートする必要があると思います。そうすれば、並べ替えられたリストをクエリすると、範囲が開始され、優先度が最も高い最初のアクティビティが取得されます。次に、最後に選択したアクティビティが終了した後に開始するアクティビティを見つけるか、最後に選択したアクティビティよりも優先度の高いアクティビティを見つけるまで、リストをたどります。リスト全体を取得したら、考えられる各 (サブ) 範囲間隔で最も優先度の高いアクティビティを選択する必要があります。

このようなもの：（テストされていません）

Date selectedStart = Date.MinValue;
PricingActivity selected = sortedList[0];
foreach(PricingActivity act in sortedList)
{
    if (act.Start >= selected.End ||
        act.Priority > selected.Priority)
    {
        // Store the selected activity with the applicable date range.
        selectedActivities.Add(
                new DateRange(selectedStart, Math.Min(selected.End, act.Start)),
                selected);
        // The next activity (act) would start here.
        selectedStart = act.Start;
        selected = act;
    }
}

selectedActivitiesDateRangeあなたが望むように、適用可能な範囲（私が発明したばかりです）の順序付けられたアクティビティのリストが含まれます。ただし、最初に要求された範囲内にある最初のアクティビティに移動し、要求された範囲のすぐ外側にある最初のアクティビティで停止するコードを追加する必要があります。

于 2010-04-09T23:54:17.567 に答える