1 c# big-o list micro-optimization
以下程序(以下说明)适用于非常小的列表,但是当列表包含大量项目(1/2万)时,应用程序进入"无响应"状态,并且完成大约需要2.5分钟(非常糟糕)时间).我可能会添加应用程序需要至少(最终)处理1亿个项目的列表.
这是有问题的过程的代码:
public void removeItems(List<long> L, SortedList<long, List<long>> _subLists)
{
foreach (KeyValuePair<long, List<long>> kvp in _subLists)
{
foreach (long duplicate in kvp.Value)
{
int j = L.IndexOf(duplicate);
L.RemoveRange(j,(int)kvp.Key);
}
}
}
L是长值列表._subLists是一个排序列表,其中每个值都是来自L的值列表,开始一些差异的算术级数系列(不相关).与该值关联的键是值包含的序列的长度.
例:
L = {1,2,3,5,6,7,18,20,21} _subLists = {2,<20>} {3,<1,5>}
该过程简单地从L中删除算术级数序列.
Alb*_*oPL 10
这个程序在大O表示法中的运行时间是n ^ 2,这是相当慢的,如果其中一个列表有1亿个条目,你可以预期运行时间会很慢.这里没有堆栈溢出问题,迭代这么多数据的速度很慢.我真的没有在这里看到一个问题,你是否想要加快速度？如果是这样,嵌套的for循环肯定是问题.
你的问题是你要从L中移除很多物品,这是一项非常昂贵的操作.每次删除项目时,都会复制内存以将已删除项目上方的所有项目向下移动.删除的项目越多,随机播放的项目越多,所需的时间就越长.内存是性能的瓶颈,RAM运行速度比CPU慢,如果你正在分页到磁盘而不是真的很慢.
你怎么能改善这一点.
最简单的选择是使用L的容器,在删除项目时具有更好的性能 - 例如LinkedList.LinkedLists在删除元素时不需要在内存中移动项目,但是它们需要更多内存来存储数据(每个值两个指针).如果这是过多的开销,那么也许LinkedList <List <long>>相反,每个都List <long>拥有最大数量的值.
或者,更改删除算法,以便迭代列表L并创建一个包含_subLists中未找到的值的新列表.您可以更改_subLists存储数据的方式,以便更快地查找范围内的项目.