什么是一个很好的算法进行编辑的"时间表"的最有效？

StackOverflow https://stackoverflow.com/questions/172302

  •  05-07-2019
  •  | 
  •  

题

这是一个小的调度程序。我需要一个算法来有效地比较两个"时间表"，发现差异，并更新的数据只行其已改变，以及项在另一表中具有这个表格外的关键。这是一个大问题，所以我就说吧，我在寻找 一般的建议 或 具体的解决方案.

编辑： 作为建议，我们大大缩短的问题。

在一个表，我准的资源的时间跨度时使用它们。

我还有第二个表(表B)其使用的标识从表一个对外关键。

该项目从表一个对应表B中将有一个跨度的时间 包括 的时间跨度从表B。不是所有的项目表的一个将拥有一个入口中的表B。

我提供一个界面为用户编辑的资源日程表A他们基本上提供一套新的数据表一个，我需要治疗作为一个 差异 从版本的数据库。

如果他们完全删除一个对象从表A这是指通过表B，我希望删除该条目从表B。

因此，考虑以下3组：

  • 原始的物体，从表A(数据库)
  • 原始的物体，从表B(数据库)
  • 编辑组对象从表A(从用户，因此没有独特的IDs)

我需要一个算法，将：

  • 离开行中的表A和表B不变，如果没有需要改变的那些对象。
  • 添加行表一需要。
  • 删除行从表A和表B作为必要的。
  • 修改行中的表A和表B作为必要的。

只是排序的对象的安排，我可以应用适当的数据库操作的是更多适当的解决方案。

再次，请回答 具体地说 或 一般 只要你喜欢，我在寻找咨询意见，但如果有人有一个完整的算法，这只会使我的一天。:)

编辑： 在响应lassvek，我提供一些额外的细节：

表B的项目总是完全包含在表一个项目，而不仅仅是重叠的。

重要的是， 表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

所以，我希望以下行为:

  • 如果我删除ID02从表一或缩短到下午2:00-下午3:00，我应该删除ID01从表B。
  • 如果我谨表一ID01至它在哪里结束在1:00， 这两个项目应当被合并在一起成一排, 和表B ID01现在应该点至表一ID01.
  • 如果我删除：上午8:00-上午10:00从表A ID01,该项目应分成两个条目：一个用于上午7:00-上午8:00，和一个新的条目(ID03)为上午10:00-上午11:00.
有帮助吗？

解决方案

我曾广泛地时期，但恐怕我不明白完全如何的表A和B的工作在一起，或许是这个词 归入 我不明白。

你可以给一些具体的例子，你想要做什么?

你的意思是，时间跨度记录中的表A中包含的全部时间跨度表B，这样吗？

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

或重叠？

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

或者相反的方式，时间跨度在B包含/重叠的?

我们说它是第一个，其时间跨度在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，去掉它吗？

我需要一些具体的例子的你想干什么。

编辑 更多的问题

Ok，什么有关：

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

这是什么？

无论是：

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

或者：

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

来总结一下我如何看到，与问题，迄今为止:

  • 你要是能够做到以下行动上的
    • 缩短
    • 延长
    • 结合时，他们相邻，结合两个或多个进入一个
    • 穿孔在他们通过删除一个周期，因而分裂它
  • B这仍然包含在一个经过上述更新，重新链接如果有必要
  • B这是包含的，但现在完全外，删除它们
  • B这是包含的，但现在部分之外， 编辑：删除这些参考数据的完整性
  • 对于所有上述行动，执少最低工作有必要使数据符合行动(而不是仅仅消除一切，并重新插入)

我会的工作在一个执行在C#可能工作的时候，我回到家，我会回来了更多以后的今晚。

编辑 这里有一个刺伤的一个算法。

  1. 优化新的列表中第一(ie。结合相邻的时期，等等)。
  2. "合并"这个名单与主期间在数据库的方式如下：
    1. 跟踪在两个列表(即。新的和现有的)你
    2. 如果当前的新的周期是完全的当前现有期间内，它加入，然后转移到下一个新的时期
    3. 如果当前的新的周期是完全在当前的现有周期期间，除现有时期和所有其孩子的时期，然后移动到一个新的现有周期
    4. 如果两个重叠，调整当前的现有周期要等到新的期间，在以下方式，然后转移到下一个新的和现有周期
      1. 如果新的周期开始之前，现有周期期间，只需将开始
      2. 如果新的时期之后开始的现有周期期间，检查是否有任何儿童时期被在的差期间，并记住它们，然后将开始
      3. 这样做的另一端
  3. 与任何时间你"铭记",看看他们是否需要重新链接或删除的

你应该创建一个大规模的设置单元测试和确保涵盖所有组合的修改。

其他提示

我建议你将你的问题分成两个单独的：第一应该是这样的："我怎么原因，有关资源的调度，当代表的安排原子作为资源的开始时间和结束时间？" 在这里，娴熟的建议使用的间隔代数似乎配合。请看看 维基百科项的时间间隔图' 和 在纽约州立大学算法储存库条目的调度.第二个问题是数据库的问题："给出的算法计划的时间间隔，并说明是否两个的时间间隔重叠或一个包含在另一个，我怎么使用这个信息管理数据库，在给定的架构？" 我相信，一旦调度的算法是在地方，该数据库的问题将更容易解决。禾田, 尤瓦

你后几乎是在"过长；没有读"类别缩短它可能会给你更多的反馈。

无论如何，在主题：你可以试着找到一种东西叫 "隔代"

因为我了解你，你的用户只能直接影响表A假设你被编程在C#你可以使用一个简单的ADO.Net 数据集管理改进对表A的库中，删除知道离开原始的行单独处理新的、修改和删除的行适当。

此外，还应该定义的一级联删除，以便自动删除相应的对象在表B。

唯一的情况下，不是这样处理是，如果时间跨度表一个被缩短。t.它并不包含对应记录在表B中了。你可以简单地检查这种情况下，在一个更新存储程序或替代定义的最新发式上的表A

这似乎我喜欢的任何算法为这将涉及通过勒瓦、匹配ResourceID、开始和结束时间，并跟踪这些元素从OldA得到的打击。然后你有两套不匹配数据，UnmatchedNewA和UnmatchedOldA.

最简单的方式我能想到的是基本上重新开始与这些：编写所有UnmatchedNewA数据库、转移要素的B从UnmatchedOldA入一个新的键(刚刚生成的)可能时，删除时没有。然后消灭了所有的UnmatchedOldA.

如果有一个很大的变化，这当然不是一种有效的方式进行。在情况的大小的数据是不是压倒性的，虽然我喜欢简单的聪明的优化。

这是不可能知道这是否最终建议使得有任何意义，如果没有更多背景，但在关闭的机会，你不认为它是这样的：

而不是通过的整个A集，你可以用事件的听众或类似的东西来更新数据模型，只有在需要改变?这种方式，目的被改变，将能够确定哪些数据库的运作是必需的。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top