列表上的 IndexOf 太慢。更快的解决方案？

StackOverflow https://stackoverflow.com/questions/1075734

  •  21-08-2019
  •  | 
  •  

题

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

谢谢，内特

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

解决方案

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

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

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

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

其他提示

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

请参阅底部 这篇文章在这里.

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

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

我建议使用 SortedList<TKey, TValue> 或者 SortedDictionary<TKey, TValue> 如果您需要对项目进行排序，请类。差异如下。

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

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

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

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

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

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

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

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

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top