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

Question

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

- ID (int identity) - 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完全覆盖，因此它变得完全过时了。

- Robert Koritnik

---

你说范围至少为1天，但它们可以是1.5天吗？还是它们总是代表整整的一天？ - tdaines

@tdaines：仅限整天。两个范围列的SQL数据类型均为date而不是datetime。并且两个列都包含日期范围（范围内包括两个日期）。 - Robert Koritnik

Answer 1

如何处理可空整数数组

我有自己的想法：

1. 对于给定的日期范围，我会创建一个内存数组，其中包含与该范围中的天数一样多的项。

2. 用 null 值填充数组。所有的值都是这个。

3. 按 ID 的相反顺序排序记录

4. 通过迭代排序记录来展开重叠的范围，并在每个项目上执行以下操作：

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

5. 最终得到一个展开的范围数组，并填充了记录 ID

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

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

基本上就是这样。

一个为期 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 时，我可以轻松地中断循环，因为所有剩余的范围都完全重叠，因此它们不会再设置数组中的任何值。因此，当我有大量范围记录时（这将相当罕见），这将加速事情。

- Robert Koritnik

---

如果你只需要处理整天，那么这可能是合适的。按开始日期排序存储一段时间可能更有效率，因为你只需要检查整数并设置少量值。由于它们按开始日期排列，你可以使用二分搜索列表来快速找到匹配的范围。 - Sam Holder

@Sam Holder：保存范围需要检查重叠，将现有范围分割成新的范围等等。我认为这会增加更复杂的处理，而没有明显的好处。内存占用很小，内存也很便宜。由于相同的数组将被重复使用，即使看起来我正在丰富地使用内存，我认为这会更快。 - Robert Koritnik

你的想法与我类似，只不过我考虑将日期和ID存储在数组中。我认为这样可以简化你的第6步骤。 - tdaines

Answer 2

免费的.NET时间段库Time Period Library for .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映射应该是一个简单的任务。

- user687474

Answer 3

我不太确定这样做有多大用处，但我会这样处理...

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

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

• 创建所有日期条目的表，[日期 -> ID]
• 对于原始表中的每条记录：
  • 选择从开始到结束的日期范围，
  • 如果任何一个ID值为空或低于当前检查的记录ID，请使用当前ID填写。
• 然后连接-如果下一个记录与上一个记录具有相同的ID，则删除下一个记录。
• 最后，您可能需要进行一些去规范化，使用[date -> ID，长度]或[date -> ID，结束日期]替换提取范围的两个连续记录

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

- SF.

---

不用担心数据删除，所有这些操作都只会在内存中进行。数据库中的原始数据将保持不变。我必须说，你的做法有点类似于我想要做的事情。实际上，我正在尝试让其他人思考这个问题，看看是否有更好的解决方案。 - Robert Koritnik

Answer 4

你需要有效地堆叠数据，并从堆栈中选择最大值。我以前曾经实现过类似的东西，我们使用的方法比你要求的灵活一些，可能不太合适，做法如下：

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

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

|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|
您可以提供一个具有压平函数的类（可能使用策略模式），该函数将具有值集合的唯一范围转换为具有单个值的唯一范围，这显然会连接以相同值结束的范围。
您会想要一个类，它选择每个唯一范围中的最大值，但您也可能想选择最小值，对值求和，求平均值，计数等等。每个这些选项都可以通过传递不同的策略实现来完成。
正如我所说，与仅选择最大值的方法相比，此方法可能效率较低，因为在这种情况下您不需要保留堆栈中的所有值，但是我记得实现相当简单。

- Sam Holder

---

尽管你正在使用数据堆栈并以某种方式组合这些数据，但这仍然是有用的。只要它能激发我的思维，那就没问题。 - Robert Koritnik