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. 不要尝试使用插入、更新和删除来更新两个数据结构 - 源信息和已解决的日历 - 而是更新源数据，然后使用其他人建议的简单扫描算法重新计算已解决的信息。如果您需要在源数据更改之间缓存已解决的日历，请执行此操作（每当源更改并重新计算时清除缓存副本）否则每次都重新计算它，因为内存而不是 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;
    }
}

selectedActivities将包含一个有序的活动列表，它们的适用范围（DateRange我刚刚发明），就像你想要的那样。但是，您必须添加一些代码才能首先转到请求范围内的第一个活动，然后在请求范围外的第一个活动处停止。

于 2010-04-09T23:54:17.567 回答