高级:如何优化我的复杂O(n²)算法

Question

我有人和地方数据如下:

• Person 实体有
  • IList<DateRangePlaces> 每个人都有
    • IList<Place> 可能的地方
  • Schedule日模式为ie.10天可用4不可用

在特定的DateRangePlaces日期范围内,人们必须遵守模仿Schedule人是否可以去某个特定的地方.

• Place 实体有
  • IList<DateRangeTiming> 每个定义每个日期范围内的开/关时间

重叠日期范围可用作LIFO.因此,对于之前已经定义的每一天,新的时间定义都会优先考虑.

问题

现在我需要做这样的事情(在伪代码中):

for each Place
{
    for each Day between minimum and maximum date in IList<DateRangeTiming>
    {
        get a set of People applicable for Place and on Day
    }
}

这意味着执行我的任务的步骤数约为:

Σ _(地方)(Σ _(天) ×Σ _(人))

这对我的理解是

O(x×y _x ×z)

并且可能与此算法的复杂性近似:

O(n ³)

我不是理论专家,所以你可以自由地纠正我的假设.真实的是,这种复杂性绝对是不可接受的,特别是考虑到我将在很多地方和人的长日期范围内运作.

从公式近似中我们可以看到人集会被多次迭代.因此,我想至少优化这一部分.为了缓解事情,我改变了一点

Person.IList<DateRangePlaces>.IList<Place>

至

Person.IList<DateRangePlaces>.IDictionary<int, Place>

无论一个人是否可以在特定日期到某个地方,这会给我一个更快的结果,因为我只会检查是否Place.Id存在于字典中而不是IList.Where()每次都必须扫描整个列表的LINQ子句.

题

1. 您是否可以建议我可以在算法中实现任何其他优化,以使其更快,甚至在大O符号方面使其更简单？

2. 您将使用哪种内存结构类型(列表,字典,堆栈,队列......)来提高性能？

附录:整个问题更加复杂

还有一些我没有提到的复杂性,因为我想简化我的问题以使其更清晰.所以.还有:

Place.IList<Permission>
Person.IList<DateRangePermission>

因此,地点需要特定权限,并且人们有限时间许可授予到期.

除此之外,还有

Person.IList<DateRangeTimingRestriction>

它只告诉特定时间该人可以在特定日期范围内去某个地方.和

Person.IList<DateRangePlacePriorities>

其中定义了特定日期范围的地点优先级.

在获得适用人员的这个过程中,我还必须计算每个人每个人的某些因素:

• 一个人在特定日期可以访问的地方数量
• 在某一天,人的地方优先考虑因素

所有这些都是我决定在内存中操作这些数据的原因,而不是使用一个非常复杂的存储过程,该过程也会进行多个表扫描以获得每个人和每个地方的因子.

我认为这样的存储过程将是复杂的处理和维护方式.所以我宁愿首先得到所有的数据(把它放在合适的内存结构中以帮助提高性能)然后在内存中进行修改.

Answer 1

我建议使用关系数据库并编写一个存储过程来检索“适用于地点和日期的人员集”。

如果模型架构正确，存储过程方法不会很复杂，也不会难以维护。此外，关系数据库具有主键和索引以避免表扫描。

使用集合加快速度的唯一方法是：

1. 更改集合类型。您可以使用 KeyedCollection、IDictionary<> 甚至断开连接的记录集。断开连接的记录集还使您能够为子记录集设置外键，但是我认为这将是一个相当复杂的使用模式。

2. 在集合中维护集合 - 基本上与使用外键的父/子关系相同的概念。对象引用只是指向原始对象内存空间的指针，或者，如果您使用的是键控集合，则可以简单地存储其他集合的索引。

3. 维护布尔属性，允许您在 true 或 false 时跳过迭代。例如，在构建实体时，设置“HasPlaceXPermission”的布尔值。如果该值为 false，则您知道不检索与地点 X 相关的信息。

4. 维护标志 - 如果使用得当，标志可以是一种非常好的优化技术。与 #3 类似，标志可用于非常快速地确定权限，例如 if((person.PlacePermissions & (Place.Colorado | Place.Florida) > 0) // 在科罗拉多州和佛罗里达州进行日期/时间扫描，否则不扫描't。

根据您提供的信息很难知道我将使用哪些集合类型，我需要更大的应用程序范围才能从架构上确定。例如，数据存储在哪里、如何检索、如何准备以及如何呈现？了解应用程序的架构将有助于确定其优化点。