IndexOf列表太慢了.更快的解决方案？

Question

我有通用列表,它必须是保留的顺序,所以我可以检索列表中对象的索引.问题是IndexOf太慢了.如果我将IndexOf注释掉,那么代码可以快速运行.有没有更好的方法,比如c#的保留有序哈希列表？

谢谢,Nate

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

Answer 1

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

如果你想要一个排序列表,然后检查以前的帖子 - 你可以SortedList<Tkey, TValue>在.Net 3.5中使用,或者对它进行排序并在较旧的.Net版本中使用BinarySearch.

[编辑]您可以在网上找到类似的例子,例如:OrderedList.这个内部使用ArrayList和HashTable,但您可以轻松地使它通用.

[Edit2] Ooops ..我给你的​​例子并没有像我在开头描述的那样实现IndexOf ...但是你明白了 - 一个列表应该被排序,另一个列表用于快速查找.

Answer 2

使用它进行排序List<T>.Sort,然后使用List<T>.BinarySearch方法:"搜索整个已排序List(T)的元素[...]此方法是一个O(log n)操作,其中n是范围内元素的数量."

Answer 3

请在此处查看本文底部。

编写自己的方法来检索索引似乎比使用 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;
}