C# 列表中的 IndexOf 太慢。更快的解决方案？

IndexOf too slow on list. Faster solution?

提问by NastyNateDoggy

I have generic list which must be a preserved order so I can retrieve the index of an object in the list. The problem is IndexOf is way too slow. If I comment the IndexOf out, the code runs fast as can be. Is there a better way, such as a preservedordered hash list for c#?

我有一个必须是保留顺序的通用列表，以便我可以检索列表中对象的索引。问题是 IndexOf 太慢了。如果我将 IndexOf 注释掉，代码会尽可能快地运行。有没有更好的方法，例如c#的保留有序哈希列表？

Thanks, Nate

谢谢，内特

• Edit - The order in which the items are added/inserted is the order it needs to be. No sorting on them is necessary. Also this list has the potential to be updated often, add, remove, insert. Basically I need to translate the object to an index due to them being represented in a grid control so I can perform operations on the grid control based on index.

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

采纳答案by Groo

If it's not sorted, but the order needs to be preserved, then you could have a separate Dictionary<YourClass, int>which would contain the index for each element.

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

If you want a sorted list, then check previous posts - you can use SortedList<Tkey, TValue>in .Net 3.5, or sort it and use BinarySearch in older .Net versions.

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

[Edit] You can find similar examples on the web, e.g.: OrderedList. This one internally uses an ArrayList and a HashTable, but you can easily make it generic.

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

[Edit2] Ooops.. the example I gave you doesn't implement IndexOf the way I described at the beginning... But you get the point - one list should be ordered, the other one used for quick lookup.

[Edit2] 哎呀.. 我给你的例子没有按照我在开头描述的方式实现 IndexOf ......但是你明白了 - 一个列表应该被排序，另一个用于快速查找。

回答by Peter

Well there is no reason you should ever have to order a hash list...that's kind of the point. However, a hash list should do the trick quite readily.

好吧，您没有理由必须订购哈希列表……这就是重点。然而，哈希列表应该很容易做到这一点。

回答by Andrew Hare

Perhaps you are looking for SortedList<TKey, TValue>?

也许您正在寻找SortedList<TKey, TValue>？

回答by RichieHindle

Sort it using List<T>.Sort, then use the List<T>.BinarySearchmethod: "Searches the entire sorted List(T)for an element [...] This method is an O(log n) operation, where n is the number of elements in the range."

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

回答by William Edmondson

If you are using the List class then you could use the Sort method to sort it after is initially populated then use the BinarySearch Method to find the appropriate element.

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

回答by Daniel Brückner

I suggest to use the SortedList<TKey, TValue>or SortedDictionary<TKey, TValue>class if you need the items sorted. The differences are the following.

如果您需要对项目进行排序，我建议使用SortedList<TKey, TValue>orSortedDictionary<TKey, TValue>类。区别如下。

• SortedList<TKey, TValue>uses less memory than SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<TKey, TValue>.

• If the list is populated all at once from sorted data,SortedList<TKey, TValue>is faster than SortedDictionary<TKey, TValue>.

• SortedList<TKey, TValue>使用的内存少于SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue>对未排序的数据有更快的插入和删除操作：O(log n) 而不是 O(n) for SortedList<TKey, TValue>。

• 如果列表从排序的数据中一次性全部填充，SortedList<TKey, TValue>则比SortedDictionary<TKey, TValue>.

If you just want to preserve the ordering, you can just use a Dictionary<TKey, TValue>and store the item as key and the index as value. The drawback is that reordering the items, insertions, or deletion are quite expensive to do.

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

回答by bgw

I'm not sure about specifics in C#, but you might be able to sort it (QuickSort?) and then use a binary search on it (BinarySearch performance is O(log2(N)), versus Sequential, such as indexOf, which is O(n)). (IMPORTANT: For a Binary Search, your structure must be sorted)

我不确定 C# 中的具体细节，但您可以对其进行排序（QuickSort？），然后对其使用二分搜索（BinarySearch 性能为 O(log2(N)），而不是 Sequential，例如 indexOf，是 O(n))。（重要提示：对于二分搜索，您的结构必须排序）

When you insert items to your data structure, you could try a modified binary search to find the insertion point as well, or if you are adding a large group, you would add them and then sort them.

当您将项目插入到数据结构中时，您也可以尝试修改二进制搜索来找到插入点，或者如果您要添加一个大组，您可以添加它们然后对它们进行排序。

The only issue is that insertion will be slower.

唯一的问题是插入会更慢。

回答by Barry Carr

If the order of the objects in the list hasto be preserved then the only way I can think of where you're going to get the fastest possible access is to tell the object what its index position is when its added etc to the list. That way you can query the object to get its index in the list. The downside, and its a big downside in my view, is that the inserted objects now have a dependency on the list.

如果在列表中的对象的顺序有被保留，然后我能想到你要去哪里，以获得最快的速度访问的唯一方法就是告诉对象时，它的加入等，以列表的索引位置是什么。这样您就可以查询对象以获取其在列表中的索引。缺点，在我看来也是一个很大的缺点，是插入的对象现在依赖于列表。

回答by Chris Grant

See the bottom of this article here.

请在此处查看本文底部。

It appears that writing your own method to retrieve the index is much quicker than using the IndexOf method, due to the fact that it calls into a virtual method depending on the type.

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

Something like this may therefore improve your performance. I wrote a small unit test to verify that this improves the performance of the search, and it did, by about 15x in a list with 10,000 items.

因此，这样的事情可能会提高您的表现。我写了一个小单元测试来验证这提高了搜索的性能，在一个包含 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;
}