个人实体有
> 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 × yx × z)
并且可能近似于该算法的复杂性：
O(n3)
我不是理论上的专家,所以你可以自由地修正我的假设.真正的是,这种复杂性是绝对不可接受的,特别是考虑到我将在很多地方和人们的长时间范围内运作.
从公式近似我们可以看到,人们将被重复迭代很多次.因此,我至少要优化这部分.为了缓解事情,我改变了一点
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)//在科罗拉多州和佛罗里达州做日期/时间扫描,否则.
根据您提供的信息,我很难知道我将使用哪些集合类型,我需要更大的应用程序范围来确定结构.例如,存储的数据在哪里,它如何被检索,它如何准备和如何呈现？了解应用程序的架构是否有助于确定其优化点.
