14

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

谢谢，内特

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

9 回答 9

14

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

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

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

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

于 2009-07-02T17:53:12.073 回答
7

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

于 2009-07-02T17:45:28.857 回答
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;
}
于 2011-11-25T09:21:31.203 回答
3

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

于 2009-07-02T17:43:48.640 回答
3

如果必须保留列表中对象的顺序，那么我能想到的唯一方法是在哪里获得最快的访问权限，就是告诉对象在将其添加到列表时的索引位置是什么。这样您就可以查询对象以获取其在列表中的索引。缺点，在我看来也是一个很大的缺点，是插入的对象现在依赖于列表。

于 2009-07-02T19:55:07.623 回答
2

如果您需要对项目进行排序，我建议使用SortedList<TKey, TValue>or类。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>.

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

于 2009-07-02T17:51:06.383 回答
1

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

于 2009-07-02T17:43:22.993 回答
1

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

于 2009-07-02T17:46:23.830 回答
1

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

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

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

于 2009-07-02T17:53:13.790 回答