1

以下过程（解释如下）适用于非常小的列表，但是当列表包含大量项目（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 中删除算术级数系列。

4

3 回答 3

10

这个过程在大 O 表示法中的运行时间是 n^2，这是相当慢的，如果其中一个列表有 1 亿个条目，您可以预期运行时间会很慢。这里没有堆栈溢出问题，迭代这么多数据很慢。我真的没有在这里看到一个问题，你想让这个更快吗？如果是这样，嵌套的 for 循环肯定是问题所在。

于 2009-05-11T14:58:22.820 回答
8

您的问题是您要从 L 中删除很多项目，这是一项非常昂贵的操作。每次删除项目时，都会复制内存以将已删除项目上方的所有项目向下移动。移除的项目越多，洗牌的项目越多，所需的时间就越长。内存是性能的瓶颈，RAM 的运行速度比 CPU 慢，如果你要分页到磁盘，它真的很慢。

你怎么能改善这一点。

最简单的选择是使用 L 的容器，它在删除项目时具有更好的性能 - 例如 LinkedList。当元素被删除时，LinkedLists 不需要在内存中移动项目，但它们确实需要更多的内存来存储数据（每个值两个指针）。如果这开销太大，那么可能会LinkedList <List <long>>改为每个都List <long>包含最大数量的值。

或者，更改删除算法，以便遍历列表 L 并创建一个包含 _subLists 中未找到的值的新列表。您可以更改 _subLists 存储数据的方式，以更快地查找范围内的项目。

于 2009-05-11T15:11:30.347 回答
0

如果可能的话：

A) 将 L 转换为有序链表。O：n * log（n）

B）将子列表转换为排序列表对，其中第一项是 L 中序列中的 #（在发布的代码片段中重复），第二项是序列的长度。O: n * log (n)

C) 使用子列表在 L 中执行一次遍历，以确定在 L 中的给定位置要删除多少元素。利用两个列表都已排序以在任一列表中不回溯的事实。上

如果可以使用，应该能够从中获得 O: n * log(n) 复杂性。当然，我不是 100% 确定问题的所有细节。例如 - L 可以重复吗？如果是这样，子列表的顺序是否重要？您可能会被迫放弃或修改这种算法，具体取决于这些 ?s 的答案。此外，这显然会使用更多内存。

于 2009-05-11T15:59:45.853 回答