分割重叠日期范围的最快方法

Question

我在 SQL DB 表中有日期范围数据，其中包含以下三列（仅相关）：

• ID（int 身份）
• RangeFrom（仅日期）
• RangeTo（仅限日期）

对于任何给定的日期范围，可能有任意数量的记录可能重叠（完全或部分）。

条件

1. 每个具有较高 ID 的记录（较新的记录）优先于可能重叠（完全或部分）的旧记录
2. 范围至少为 1 天（RangeFrom 和 RangeTo 相差一天）

因此，对于给定的日期范围（不超过即 5 年），我必须

1. 获取属于该范围的所有范围记录（全部或部分），
2. 将这些重叠部分拆分为非重叠范围
3. 返回这些新的非重叠范围

我的看法

由于有很多与这些范围相关的复杂数据（大量联接等），并且由于处理器+内存能力比 SQL 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 完全覆盖，因此它完全过时了。

Answer 1

我不太确定这会有多大用处，但我处理这个问题的方式......
（为了便于理解，首先未进行优化...）

• 将表映射从 [ID->范围] 转换为 [日期-> 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”被分成两段），因此最终将数据库保留为日期-> ID 格式而不是 ID-> 范围似乎是首选。

现在进行明显的优化 - 当然不要保留每个日期记录的 ID 列表。只需用空ID填充日期->ID表，并在填充最终记录时，替换迄今为止找到的最大记录：

• 创建所有日期条目的表，[日期->; ID]
• 原始表中的每条记录：
  • 选择范围为“从”到“到”的日期，
  • 如果有 ID 值为 null 或小于当前检查的记录 ID，请填写当前 ID。
• 然后连接 - 如果下一条记录与上一条记录具有相同的 ID，则删除下一条记录。
• 最后，您可能想要稍微反规范化，用 [date ->; 代替提取一个范围内的两个连续记录。 ID，长度]，或[日期-> ID,end_date]

添加新记录就像创建操作的一次迭代。另一方面，删除记录似乎相当棘手。

Answer 2

实际上，您想要堆叠数据，并从堆栈中选择最大值。我之前必须实现与此类似的东西以及我们使用的方法，这给了我们比您需要的更多的灵活性，因此这样做可能不合适：

拥有一个用于管理记录的对象，并将每个记录添加到这个物体。添加记录时，创建一个新的日期范围并将记录的值与该范围相关联。然后检查该范围是否与任何其他现有范围重叠。如果确实重叠，则为每个重叠创建一个新范围，并将两个/全部上的所有值（取决于您是在添加每个范围时执行此操作还是在单遍中执行此操作）将重叠范围与新范围相关联。这可以在添加数据时完成，也可以在添加所有数据后一次性完成。

最后，您有一个包含唯一范围的对象，每个范围都有一个与其关联的值的集合，有点像上面的图片。

       |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|

然后，您可以提供一个具有展平函数的类（可能使用策略模式），该函数会将具有值集合的唯一范围转换为具有单个值的唯一范围，这显然会连接最终具有相同值的范围。

您可能需要一个从每个唯一范围中选择最大值的类，但您可能还想选择最小值、对值求和、求平均值、对它们进行计数等。每个选项都可以通过传递不同的实现来完成的策略。

正如我所说，这种方法可能比仅选择最大值的方法效率低，因为在这种情况下您不需要将所有值保留在堆栈中，但据我记得，实现相当简单。

Answer 3

对于给定的日期范围

我想出了一个自己的想法：

1. ，我将在内存中创建一个整数数组，其中的项目数量与该范围内的天数一样多。

2. 用null值填充数组。所有这些。

3. 按 ID 以相反顺序对记录进行排序

4. 通过迭代有序记录来展平重叠范围，并对每个项目执行以下操作：

   1. 获取物品
   2. 计算数组的开始和结束偏移量（天差）
   3. 将这两个偏移量之间的所有数组值设置为项目 ID，但仅当值为 null
   4. 继续执行步骤 4.1

5. 您最终会得到一个扁平范围数组，并填充记录 ID

6. create新的记录集并在数组中的 ID 更改时创建每个新记录。每个记录应使用与数组中设置的记录 ID 关联的数据

7. 为下一个人及其重叠范围集重复整个过程（不要忘记重复使用同一数组）。 = 返回步骤 2。

基本上就是这样。

给定的 10 年日期范围需要大约 10 年的数组。 3650 个可空整数，我认为这是相当小的内存占用（每个整数占用 4 个字节，但我不知道具有 int 和 bool 的可空整数占用多少空间 但假设 8 个字节，总计 3650*8 = 28.52k），并且可以在内存中轻松且相当快速地进行操作。由于我没有保存日期范围、拆分或类似的内容，因此这些只是带有 if 的赋值操作，用于检查值是否已设置。

10 年的日期范围是罕见的极端夸张。 75% 的日期范围将在 3 个月或一年的四分之一内（90 天 * 8 字节 = 720 字节），99% 将落在全年范围内（365*8 = 2920 字节 = 2,85k

）发现该算法更适合展平重叠的日期范围。

为了减少一半的内存占用，我可以使用 int 而不是 int? 并设置为 -1 而不是 null。

过早迭代循环中断的可能性

我也可以保留未设置的天数，当它达到 0 时，我可以轻松地中断循环，因为所有剩余范围完全重叠，因此它们不会在数组中设置任何更多值。因此，当我有大量范围记录（这将是相当罕见的）时，这甚至会加快速度。

Answer 4

免费的.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 映射应该是一项简单的任务。