.Distinct() 的更快替代方案

Question

我正在制作一款性能至关重要的视频游戏。

我正在使用 .Distinct() 扩展方法从列表中获取唯一值。 有没有更快的方法？ （即使这意味着有更多的代码行）

Answer 1

.Distinct 是一个 O(n) 调用。
你不可能比这更快了。

但是，您应该确保您的 GetHashCode（以及在较小程度上 Equals）尽可能快。

根据您的情况，您也许可以将 List 替换为 HashSet，这将首先防止插入重复项。 （还具有 O(1) 插入）

但是，在得出需要更快的结论之前，请务必分析您的代码。

Answer 2

它必须是一个列表吗？

是否可以从 List 切换到 HashSet？ HashSet 从一开始就防止对象被多次插入到列表中，因此 Distinct 已经完成了。

Answer 3

如果您可以就地执行不同操作，则可以通过首先使用 Array.Sort 来非常快速地进行零分配，然后：

 TSource oldV = source[0];
 int pos = 1;
 for (int i = 1; i < source.Count; i++)
 {
     var newV = source[i];
     source[pos] = newV;
     if (!eqComparer.Equals(newV, oldV))
     {
        pos++;
     }                
     oldV = newV;
 }
 //pos now == the new size of the array

然后您将必须跟踪现在较小的数组大小，或使用 Array.resize （但这将分配一个新数组）

或者，如果您使用 List 执行相同的方法，您可以在末尾调用 RemoveRange调整其大小而不分配。这最终会快得多。

其他海报可能是正确的，尽管您可以通过其他方式实现此目标，例如首先使用哈希集，或者保持并行集合，其中一个集合始终只包含不同的元素。抵消插入/删除的少量成本，以便根本不需要时间来获取不同的集合。