什么是最有效编辑"时间表"的好算法？

Question

这适用于小型调度应用.我需要一种算法来有效地比较两个"时间表",找到差异,并仅更新已更改的数据行,以及另一个表中具有此表作为外键的条目.这是一个很大的问题,所以我马上就说我正在寻找一般建议或具体解决方案.

编辑:正如所建议的那样,我已经大大缩短了这个问题.

在一个表中,我将资源与使用它们的时间跨度相关联.

我还有第二个表(表B),它使用表A中的ID作为外键.

表A中对应于表B的条目将具有包含表B中的时间跨度的时间跨度.并非表A中的所有条目都具有表B中的条目.

我正在为用户提供一个界面来编辑表A中的资源调度.它们基本上为表A提供了一组新的数据,我需要将其视为数据库中版本的差异.

如果他们从表B中完全删除表A中的对象,我也想从表B中删除该条目.

因此,给出以下3组:

• 表A中的原始对象(来自数据库)
• 表B中的原始对象(来自数据库)
• 表A中编辑过的对象集(来自用户,因此没有唯一的ID)

我需要一个算法:

• 如果这些对象不需要进行任何更改,则表A和表B中的行保持不变.
• 根据需要向表A添加行.
• 根据需要从表A和表B中删除行.
• 根据需要修改表A和表B中的行.

只是将对象排序到我可以应用适当的数据库操作的安排中,这对于解决方案来说已经足够了.

再次,请按照您的具体或一般情况回答,我正在寻求建议,但如果有人有一个完整的算法,只会让我的一天.:)

编辑:为了回应lassvek,我提供了一些额外的细节:

表B的项目始终完全包含在表A项目中,而不仅仅是重叠.

重要的是,表B的项目是量化的,因此它们应完全落入或完全落在外面.如果没有发生这种情况,那么我有一个数据完整性错误,我必须单独处理.

例如(使用速记):

Table A
ID Resource    Start         End
01 Resource A  10/6 7:00AM   10/6 11:00AM
02 Resource A  10/6 1:00PM   10/6 3:00PM

Table B
ID Table_A_ID  Start         End
01 02          10/6 1:00PM   10/6 2:00PM

所以我想要以下行为:

• 如果我从表A中删除ID 02,或者将其缩短到下午2:00 - 3:00 PM,我应该从表B中删除ID 01.
• 如果我将表A ID 01扩展到它在下午1:00结束的位置,则这两个条目应合并为一行,而表B ID 01现在应指向表A ID 01.
• 如果我从表A ID 01中删除8:00 AM-10:00AM,该条目应分为两个条目:一个用于7:00 AM-8:00AM,以及一个新条目(ID 03)用于10:00 AM-11: 00AM.

Answer 1

我曾经广泛地工作过一段时间,但我恐怕我完全不明白表A和B是如何协同工作的,也许这是我不明白的含义.

你能举出一些你想做的具体例子吗？

你的意思是表A中记录的时间跨度包含表B中的完全时间跨度,就像这样吗？

|---------------- A -------------------|
    |--- B ----|      |--- B ---|

或重叠？

    |---------------- A -------------------|
|--- B ----|                        |--- B ---|

或者相反的方式,B中的时间跨度包含/与A重叠？

假设它是第一个,其中B中的时间跨度与表A中的链接时间跨度相同/相同.

这是否意味着:

* A removed A-timespan removes all the linked timespans from B
* An added A-timespan, what about this?
* A shortened A-timespan removes all the linked timespans from B that now falls outside A
* A lenghtened A-timespan, will this include all matching B-timespans now inside?

这是一个例子:

|-------------- A1 --------------|    |-------- A2 --------------|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

然后你加长A1并缩短并移动A2,这样:

|-------------- A1 ---------------------------------|  |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

这意味着您要修改这样的数据:

1. Lengthen (update) A1
2. Shorten and move (update) A2
3. Re-link (update) B3 from A2 to A1 instead

如何修改,A1加长,但不足以完全包含B3,A2以相同的方式移动/缩短:

|-------------- A1 -----------------------------|      |--- A2 --|
  |---- B1 ----|  |----- B2 ---|       |---- B3 ----|  |-- B4 --|

既然B3现在不完全在A1或A2之内,那么将它删除？

我需要一些你想做的具体例子.

编辑更多问题

好的,怎么样:

|------------------ A -----------------------|
  |------- B1 -------|  |------- B2 ------|
                           |---|                   <-- I want to remove this from A

那这个呢？

或者:

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|  |B3|   |--- B2 ---|

要么:

|------------------ A1 ----|   |---- A2 -----|
  |------- B1 -------|

到目前为止总结我如何看待它,提出问题:

• 您希望能够在A上执行以下操作
  • 缩短
  • 加长
  • 当它们相邻时组合,将两个或更多个组合成一个
  • 通过去除一段时间在它们中打孔,然后将它分开
• 在上述更新后仍然包含在A中的B,必要时重新链接
• B被包含,但现在完全在外面,删除它们
• B包含,但现在部分在外,编辑:删除这些,参考数据完整性
• 对于上述所有操作,执行必要的最少工作以使数据与操作保持一致(而不是仅删除所有内容并重新插入)

我将在C#中实现一个可以在我下班回家时工作的实现,今晚我会再回来.

编辑这里是一个算法的刺.

1. 首先优化新列表(即组合相邻时段等)
2. 通过以下方式将此列表与数据库中的主周期"合并":
   1. 跟踪你在两个列表(即新的和现有的)中的位置
   2. 如果当前新期间完全在当前现有期间之前,则添加该期间,然后移至下一个新期间
   3. 如果当前新期间完全在当前现有期间之后,则删除现有期间及其所有子期间,然后移至下一个现有期间
   4. 如果两者重叠,则以下列方式调整当前现有周期等于新周期,然后继续下一个新的和现有的周期
      1. 如果新期间在现有期间之前开始,只需移动开始
      2. 如果新时段在现有时段之后开始,请检查是否有任何子时段处于差异时段,并记住它们,然后移动开始
      3. 对另一端做同样的事
3. 对于您"记住"的任何时段,请查看是否需要重新链接或删除它们

您应该创建一组大量的单元测试,并确保涵盖所有修改组合.