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

Question

我在SQL DB表中有日期范围数据,这些数据包含以下三个(仅相关)列:

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

Answer 1

一个可空整数数组怎么样

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

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

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

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

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

   1. 获得物品
   2. 计算数组的开始和结束偏移量（天差）
   3. 将这两个偏移量之间的所有数组值设置为 item ID，但仅当 value 为 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 时，我可以轻松打破循环，因为所有剩余的范围都完全重叠，因此它们不会在数组中设置更多值。所以当我有很多范围记录（这将是相当罕见的）时，这甚至会加快速度。