c# - 拆分重叠日期范围的最快方法

Question

我在具有以下三个(仅相关)列的 SQL 数据库表中有日期范围数据:

• ID(整数身份)
• RangeFrom(仅限日期)
• RangeTo(仅限日期)

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

条件

1. 每条具有更高 ID 的记录(较新的记录)都优先于可能重叠(全部或部分)的较旧的记录
2. 范围至少为 1 天(RangeFrom 和 RangeTo 相差 1 天)

所以对于给定的日期范围(不超过即 5 年)我必须

1. 获取落入该范围内的所有范围记录(全部或部分)
2. 将这些重叠部分拆分为不重叠的范围
3. 返回这些新的非重叠范围

我的看法

由于有很多与这些范围相关的复杂数据(很多连接等)，并且由于处理器 + 内存能力比 SQL 数据库引擎更高效，我决定宁愿将重叠数据从数据库加载到我的数据层并执行内存中的范围斩波/拆分。这在开发和执行方面给了我更大的灵 active 和速度。

如果您认为这应该在 DB 中得到更好的处理，请告诉我。

问题

我想写出最快的，如果可能的话，也是资源非饥饿的转换算法。由于我得到了很多这样的记录并且它们与不同的用户相关，我必须为每个用户及其重叠范围数据集运行这个算法。

拆分这些重叠范围的最有效(快速且不占用资源)方法是什么？

示例数据

我有记录 ID=1 到 ID=5 以这种方式在视觉上重叠(日期实际上是不相关的，我可以通过这种方式更好地显示这些重叠):

       6666666666666
                44444444444444444444444444         5555555555
          2222222222222            333333333333333333333            7777777
11111111111111111111111111111111111111111111111111111111111111111111

结果应该是这样的:

111111166666666666664444444444444444444444333333333555555555511111117777777

结果实际上看起来就像我们从顶部查看这些重叠，然后获取我们从这个自上而下 View 中看到的 ID。

结果实际上会转换为新的范围记录，因此旧 ID 变得无关紧要。但是它们的 RangeFrom 和 RangeTo 值(以及所有相关数据)将被使用:

111111122222222222223333333333333333333333444444444555555555566666667777777

这当然只是重叠范围的一个例子。对于任何给定的日期范围，它可以是从 0 条记录到 X 的任何值。正如我们所见，范围 ID=2 被 4 和 6 完全覆盖，因此它完全过时了。

Answer 1

一个可空整数数组怎么样

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

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

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

3. 按 ID 倒序排列记录

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

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

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

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