列表中的IndexOf方法太慢了，有更快的解决方案吗？

Question

列表中的IndexOf方法太慢了，有更快的解决方案吗？

c#listperformanceindexof

14

我有一个通用列表，必须保留其顺序，以便我可以检索列表中对象的索引。问题是IndexOf方法太慢了。如果我注释掉IndexOf方法，代码运行速度就会非常快。是否有更好的方法，比如C#中的保留有序哈希列表？

谢谢， Nate

编辑 - 添加/插入项目的顺序就是它需要的顺序。不需要对它们进行排序。此外，这个列表可能经常更新，添加、删除、插入。基本上，由于它们在网格控件中表示，我需要将对象转换为索引，以便可以根据索引在网格控件上执行操作。

- NastyNateDoggy

代码？您在列表中存储了什么？顺序是否重要？ - jjnguy

你是想获取对象本身还是只是对象的索引？ - kemiller2002

"Ordered" 的意思是已经排序，还是必须保持原有的顺序？ - vgru

抱歉，我去开会然后吃午饭了。需要几分钟来检查答案。我需要保持它们被添加到列表中的顺序。 - NastyNateDoggy

回复DavidN，插入和删除可以慢一些，但显然不应该太慢。对于性能来说，获取列表中项目的索引是最重要的部分，因为它经常需要执行。是的，这些项必须保持它们添加到列表中的顺序。 - NastyNateDoggy

显示剩余2条评论

9个回答

8

使用 List<T>.Sort 进行排序，然后使用 List<T>.BinarySearch 方法进行查找：“在整个已排序的 List(T) 中搜索元素[...] 此方法是 O(log n) 操作，其中 n 是范围内元素的数量。”

- RichieHindle

6

请看这篇文章底部。

似乎编写自己的检索索引方法比使用IndexOf方法更快，因为它会根据类型调用虚拟方法。

因此，像这样做可能会提高性能。我编写了一个小单元测试来验证这是否改善了搜索性能，并且确实如此，在包含10,000个项目的列表中，性能提高了约15倍。

static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}

- Chris Grant

那段代码该如何使用？我收到了“找不到类型或命名空间名称'Item'”的错误信息。 - JohnSaps

1

@JohnSaps，你应该用列表中存储的项的类型替换 "Item"。例如，如果你有 "IList<Contact>"，那么你应该将 "Item" 替换为 "Contact"。 - Chris Grant

3

也许您正在寻找 SortedList<TKey, TValue>？（链接）

- Andrew Hare

我相信他只是指“保持顺序”，而不是排序。 - vgru

3

如果列表中对象的顺序必须保持不变，那么我所能想到的唯一方法是，在将对象添加到列表时告诉对象其索引位置。这样，您可以查询对象以获取其在列表中的索引。缺点是，插入的对象现在对列表具有依赖性，这在我的观点中是一个很大的缺点。

- Barry Carr

谢谢回复。我也考虑过这个，但最终选择了在被接受的答案下面评论中所描述的方法。 - NastyNateDoggy

2

我建议在需要排序的情况下使用 SortedList<TKey, TValue> 或者 SortedDictionary<TKey, TValue> 类。两者的区别如下：

SortedList<TKey, TValue> 比 SortedDictionary<TKey, TValue> 使用更少的内存。
SortedDictionary<TKey, TValue> 在插入和删除未排序数据时具有更快的速度：时间复杂度是 O(log n)，而 SortedList<TKey, TValue> 是 O(n)。
如果列表一开始就被填满了已经排好序的数据，SortedList<TKey, TValue> 将比 SortedDictionary<TKey, TValue> 更快。

如果您只想保留顺序，可以使用一个 Dictionary<TKey, TValue>，将项目存储为键，将索引存储为值。缺点是重新排序项目、插入或删除相当昂贵。

- Daniel Brückner

是的，字典是一种我考虑过的方法，但会增加维护和性能损失的负担。 - NastyNateDoggy

1

好吧，你永远不应该需要订购散列列表......这就是重点。然而，散列列表应该非常容易解决问题。

- Peter

1

如果您正在使用List类，那么您可以使用Sort方法在初始填充后对其进行排序，然后使用BinarySearch方法查找适当的元素。

- William Edmondson

1

我不确定C#中的具体情况，但您可能可以对其进行排序（快速排序？），然后在其中使用二分查找（二分查找性能为O(log2(N))，而顺序查找，如indexOf，则为O(n)）。（重要提示：对于二分查找，您的结构必须经过排序）

当您向数据结构插入项目时，您可以尝试使用修改后的二分查找来查找插入点，或者如果您正在添加大量项目，则会将它们添加并对其进行排序。

唯一的问题是插入速度会变慢。

- bgw

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vgru · Accepted Answer

如果不需要排序，但是需要保留顺序，那么可以有一个单独的Dictionary<YourClass, int>，其中包含每个元素的索引。

如果想要排序列表，请查看之前的帖子 - 您可以在 .Net 3.5 中使用SortedList<Tkey, TValue>，或对其进行排序并在旧版 .Net 中使用BinarySearch。

[编辑]您可以在网上找到类似的示例，例如：OrderedList。这个示例内部使用了ArrayList和HashTable，但您可以轻松地使其通用。

[编辑2]哎呀..我给你的例子没有按照我一开始描述的方式实现IndexOf...但是您懂了吧 - 一个列表应该是有序的，另一个列表用于快速查找。