Collection.Contains Big-O
我需要优化一个功能，该功能显示系统的警报数量，当系统达到20 000个警报时，这些警报会变得难以忍受。 （警报由一个警报和一个条件组成，意味着它实际上是40 000个对象）。这个数字每5秒刷新一次。现在Collection.Contains Big-O
，永远记住，需要的仅仅是一个整数，通过实现此之前的程序员：
- 加载每个报警条件从数据库在每次调用（确认和未确认）
- 遍历每个闹钟以查找未确认的闹钟（使用一些定制的Linq扩展）
- 将未确认的闹钟列表和条件匹配列表发送到Silverlight应用程序
- 比较未确认GED警报未确认报警的缓存列表
- 重复4.条件
- 绑定标签
Alarms.Count和Conditions.Count
这显然会导致很多不必要的开销，我正打算通过更换来解决一切都与SQL语句
SELECT COUNT(*) as UnAckAlarms
FROM Alarms
WHERE AckTime IS NULL
不过没有关系，我不知道是第4步 在那里，我发现这一点：
foreach (var alarm in loadResult.Entities)
{
if (!ActiveAlarms.Contains(alarm.AlarmId))
{
ActiveAlarms.Add(new AlarmInfo
(...)
据我所知，报警是一个对象，没有散列，所以我想知道..是否收集.Contains() O（n）的bigO？在这种情况下，上面的代码是不是有O（n^2）？而且，如果我通过替换整个集合来优化这个代码到O（n），甚至O（1），我的速度是否会增加0.99％？ （40000/400000^2） 或者我应该用SQL语句替换所有内容并重写应用程序的主要部分？
编辑：所以，一些结果： 优化之前：60+秒总得到 删除不必要的循环和自定义添加后：8秒。从服务器加载时间约7秒，因此： 服务器端优化后：0.3秒。
这大约提高了200％的速度。 :)
假设ActiveAlarms是Collection类型或List的，并利用哈希未实现，那么Contains()为O（n）的，与上面的代码为O的确实（N^2）。
如果您可以将ActiveAlarms更改为哈希集合，那么Contains()将为O（1），并且上面的整个代码将变为O（n）。问题是O（1）是否实际上比O（n）快得多，这取决于哈希表的内部哈希函数的复杂程度。但我认为我们可以肯定，在大多数正常情况下它会更快。
确切的速度提高你会得到是不可预知的。衡量一下，我会说！
祝你好运！
由于这些警报都有唯一的ID，我开始研究如何在散列函数中使用它。事实证明，这已经有点糟糕了：add函数通过Collection进行第二次循环，找到AlarmID> item.AlarmID的项目。好的，那么另一个O（n）。当满足条件时发生了什么？ Collection.Insert，它也有O（n）。总之，我没有O（n^2），但在O（n^2）和O（n^4）之间的某个地方......除去了所有这些无意义的东西，并使我的速度提高了98％。 （从30秒到0.8秒）。现在已经够好了。稍后我会实施适当的哈希。 – AkselK 2012-01-30 14:39:14
伟大的结果，祝贺！ – 2012-01-30 14:40:38
我会把这整个事情变成sql。创建一组触发器，在添加/删除/确认/等警报时，可以从运行总计中增加/减少触发器。仅仅计算事物的运行循环根本没有必要
我做了一些进一步的测量，结果发现步骤1,2和3没有花费不合理的时间。但是，触发器如何更新字段与SQL count（）语句进行比较？ – AkselK 2012-01-30 14:41:13
你在谈论哪种类型的集合？ – 2012-01-30 14:02:32
在这种情况下，ObservableCollection（T），但我相信它继承了Collection（T）的大多数方法。 – AkselK 2012-01-30 14:05:29