2

我在一个类（我们称之为MyClass）中发现了一些非常讨厌的代码，它广泛使用了 List of T.Add/Remove方法。此外，同一个类将该集合公开为具有 T 类型 IList 的属性，因此更改类型将涉及一些重构。

此外，该 MyClass 集合用作事件侦听器对象的容器，因此客户端代码只需订阅（将自身添加到集合中）和取消订阅（将自身从集合中删除）。顺序无关紧要，无论是列表的开始/中间/结束。

为了提高性能，我想替换内部实现细节，将 List of T 替换为.... 不知道是什么。我尝试了 T 的 LinkedList，但它没有实现 T 的 IList。我在 MSDN 上查看了 T 的 IList，但没有实现 IList 的类列表，因此我可以比较文档。

另一件事是我试图将 T 的 IList 更改为 T 的 ICollection，这可能是一个解决方案（因为MyClass的客户端代码使用 Add/Remove 方法，因此不需要重构）但发生了有趣的事情：

        LinkedList<string> list = new LinkedList<string>();
        list.Add("test");

由于出现错误，此代码无法编译：

“System.Collections.Generic.LinkedList”不包含“Add”的定义，也没有扩展方法“Add”

但是当我将其更改为：

        ICollection<string> list = new LinkedList<string>();
        list.Add("test");

然后我工作了。你能解释一下为什么第一个示例没有编译+告诉.NET Framework 中 T 的 IList 在添加/删除项目方面的最快实现是什么？

谢谢。

4

2 回答 2

5

LinkedList<T>基本上ICollection<T>使用显式接口实现来实现。因此，该Add方法仅在您将其“视为”时可用ICollection<T>。

关键是如果你知道你使用的是链表，你应该使用AddFirstorAddLast代替。

于 2012-08-09T18:45:48.450 回答
1

没有一个单一的类在添加和删除方面是最快的。它们都是为了在某些情况下更快而构建的，它们也都有其缺点。 List大多数时候可以快速添加到末尾，但它会定期进行昂贵的添加，涉及复制每个元素。当您开始在接近开始时添加项目时，它会变得越来越昂贵。去除在最后是便宜的，并且随着你向开始移动而变得越来越昂贵。

LinkedList可以有效地添加到开头或结尾，但是这些添加仍然比添加到 a 的末尾要慢很多List（但没有任何非常大的添加）。LinkedList添加到快速获取昂贵的开始或结束以外的位置。在大多数实际情况下，LinkedList从性能的角度来看，这不是一个好的选择。

我可以继续，但需要一段时间。重点仍然是我们需要了解有关如何使用集合的更多详细信息，以便提出更高性能的替代方案（或使用现有集合的不同方式）。

由于您已经描述了您所拥有的只是一组不需要排序的数据，只需要有效地添加/删除/迭代所有最好的集合都是HashSet<T>. 您可以自己对基于散列的数据结构的内部工作进行一些研究（这很酷），但关键是它是一个无序的数据结构，具有非常有效的元素添加/删除，并且您可以有效地迭代。这非常适合您的情况。使用基于哈希的数据结构要记住的一件事是，您的对象需要具有有意义的实现GetHashCode（Equals默认的通常不适用于您的自定义类型）。如果您使用类似int或string作为关键，它已经有了很好的实现。

于 2012-08-09T18:56:15.933 回答