c# – 高级：如何优化我的复杂O(n²)算法

概述我有人和地点的数据如下： 个人实体有 > IList< DateRangePlaces>每个都有 > IList< Place>可能的地方 >将日期模式安排为ie. 10天可用4不可用 在特定的DateRangePlaces日期范围内,人们必须遵守计划模式,无论人们是否可以去特定的地方. >地方实体有 > IList< DateRangeTiming>每个定义每个日期范围内的开/关时间 重叠日期范 我有人和地点的数据如下：

个人实体有

> IList< DaterangePlaces>每个都有

> IList< Place>可能的地方

>将日期模式安排为IE. 10天可用4不可用

在特定的DaterangePlaces日期范围内,人们必须遵守计划模式,无论人们是否可以去特定的地方.

>地方实体有

> 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    }}

这意味着执行我的任务的步骤大约为：

∑_(places)( ∑_(days) × ∑_(people) )

这对我的理解是

O(x × y_x × z)

并且可能近似于该算法的复杂性：

O(n³)

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

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

Person.IList<DaterangePlaces>.IList<Place>

至

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

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

题

>你能否提出我可以在我的算法中实现的任何其他优化,使其更快,甚至使它在较大的O符号方面变得不那么复杂？
>您将使用哪些内存结构类型,以及为什么(列表,字典,堆栈,队列…)可以提高性能？

附录：整个问题更复杂

还有其他的复杂性,我没有提到,因为我想简化我的问题,使其更加清楚.所以.还有：

Place.IList<Permission>Person.IList<DaterangePermission>

所以这些地方需要特殊的权限,而且人们有限的时间可以到期许可.

除此之外,还有

Person.IList<DaterangeTimingRestriction>

这只告诉特定的时间,人们可以在特定的日期范围内去某个地方.和

Person.IList<DaterangePlacePrioritIEs>

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

在获得适用人员的这个过程中,我还必须计算每个人每个与

一个人可以在特定的一天访问的地方的数量
>那个人的地点优先考虑因素

所有这些都是为什么我决定在内存中 *** 作这些数据,而不是使用非常复杂的存储过程,也可以进行多个表扫描以获取每个人和地点和日子的因素.

我认为这样的存储过程将是复杂的处理和维护的方式.所以我宁愿先获取所有的数据(放置适当的内存结构来帮助性能),然后在内存中处理它.

解决方法 我建议使用关系数据库和编写存储过程来检索“适用于地点和日期的人的一套”.

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

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

>更改集合类型.您可以使用KeyedCollection,IDictionary<>甚至是断开连接的记录集.断开连接的记录集还使您能够将外键设置为子记录集,但是我认为这将是一个相当复杂的使用模式.
>在集合中维护一个集合 – 与一个外键的父/子关系基本相同的概念.对象引用将只是指向原始对象的内存空间的指针,或者如果您使用的是键控集合,则可以简单地存储其他集合的索引.
>维护布尔属性,可以允许您跳过迭代,如果为true或false.例如,在构建实体时,设置一个“HasPlaceXPermission”的布尔值.如果值为false,则您不知道不会检索与地点X相关的信息.
>维护标志 – 正确使用时,标志可以是非常好的优化技术.与#3类似,标志可以非常快地用于确定权限,例如,如果((person.PlacePermissions&(Place.colorado | Place.FlorIDa)> 0)//在科罗拉多州和佛罗里达州做日期/时间扫描,否则.

根据您提供的信息,我很难知道我将使用哪些集合类型,我需要更大的应用程序范围来确定结构.例如,存储的数据在哪里,它如何被检索,它如何准备和如何呈现？了解应用程序的架构是否有助于确定其优化点.

总结

以上是内存溢出为你收集整理的c# – 高级：如何优化我的复杂O(n²)算法全部内容，希望文章能够帮你解决c# – 高级：如何优化我的复杂O(n²)算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。