12

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

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

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

条件

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

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

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

我的看法

由于有很多与这些范围相关的复杂数据（大量连接等），并且由于处理器 + 内存能力比 SQL DB 引擎效率更高，我决定将重叠数据从 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 覆盖，因此它完全过时了。

4

4 回答 4

5

一个可以为空的整数数组怎么样

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

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

  2. null用值填充数组。他们全部。

  3. 按 ID 逆序排列记录

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

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

  5. 您最终会得到一系列扁平范围并填充记录 ID

  6. 创建新记录集并在数组中的 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 时，我可以轻松打破循环，因为所有剩余的范围都完全重叠，因此它们不会在数组中设置更多值。因此，当我有很多范围记录（这将是相当罕见的）时，这甚至会加快速度。

于 2011-04-19T07:52:51.330 回答
2

.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 映射应该是一件容易的事。

于 2011-06-09T15:56:10.597 回答
1

我不太确定这会有多大用处，但我将如何处理这个......（首先未优化以便于理解......）

  • 将表映射从 [ID->range] 转换为 [date->list of IDs]。

（按日期排序，每个日期 - 无论是开始还是结束，都是到达下一个日期的时间范围的开始。）所以你的表格看起来像：

        |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”在您的示例中分为两个段），因此最终将数据库保持为 date-> ID 格式而不是 ID-> range 似乎是首选。

现在进行明显的优化——当然不要在每个日期记录中保留 ID 列表。只需使用空 ID 填写 date->ID 表，并在填写最终记录的同时，替换目前找到的值最大的记录：

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

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

于 2011-04-19T07:29:53.873 回答
0

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

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

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

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

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

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

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

于 2011-04-19T06:48:31.643 回答