c# - 从 HashSet 中选取 'any' 项非常慢 - 如何快速做到这一点？

Question

我目前正在使用贪婪算法做很多工作 - 它们不关心索引等，它们只适用于组/集合。但我发现 85% 的执行时间都花在尝试从 HashSet 中选择一个项目上。

根据 MSDN 文档:

The HashSet class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.

...除了“获取值”之外的所有事情似乎都是如此。

我已经尝试过:

• ElementAt(0) - 非常慢，据称是因为 HashSet 会生成临时排序，对所有内容进行排序，然后返回最先的内容
• 首先 - 非常慢(大概它在做同样的事情)

我的期望:

• AnyItem() - 从 HashSet 返回一个项目，但没有任何保证。可能是第一个，可能是最后一个，可能是随机的(但不要指望这一点)。

...但我似乎无法找到一种方法来做到这一点。

EDIT2:稍微更详细的源代码，以明确为什么 HashSet 中缺少的功能的一些简单解决方法没有帮助，并希望更好地展示为什么 HashSet 在所有其他方面都是正确的类:

HashSet<MyClass> candidates;
HashSet<MyClass> unvisited;

... // fill unvisited with typically: 100,000 to 10 million items
... // fill candidates with at least 1 item, potentially 100,000's of items

while( candidates.Count > 0 && unvisited.Count > 0 )
{
  var anyItem = candidates.First();

  while( ! CanProcess( anyItem ) ) // CanProcess probable checks some set intersections
  {
     candidates.Remove( anyItem );
     if( candidates.Count > 0 )
        anyItem = candidates.First();
     else
     {
        anyItem = null;
        break;
     }
  }

  if( anyItem == null ) // we've run out of candidates
     break;

  // For the algorithm: "processing" anyItem has a side-effect of 
  // transferring 0 or more items from "unvisited" into "candidates"
  var extraCandidates = Process( anyItem, unvisited );
  // ... Process probably does some set intersections
  
  ... // add all the extraCandidates to candidates
  ... // remove all the extraCandidates from unvisited
  
  candidates.Remove( anyItem );
}

即:典型的贪心算法有几组:一组“下一次迭代的起点”，以及一组或多组(这里我只显示了一组)“尚未处理的数据，以及以某种方式连接到/可以从起点到达”。

...一切都很快，唯一慢的是“第一个”调用 - 我没有理由接受第一个，我可以接受任何一个，但我需要接受一些东西!

Answer 1

HashSet 类似乎没有针对第一个项目被重复删除的场景进行优化。每次删除后，该类内部保留的空间不会减少，而是将相应的槽标记为空。该类的枚举器枚举所有内部槽，并在找到非空槽时生成一个值。当 HashSet 的内部空间变得稀疏时，这可能会变得极其低效。例如，曾经容纳 1,000,000 个元素并已减少为单个元素的 HashSet 必须枚举 1,000,000 个槽，然后才能生成存储在其单个非空槽中的元素:

var set = new HashSet<int>(Enumerable.Range(1, 1_000_000));
set.ExceptWith(Enumerable.Range(1, 999_999));
var item = set.First(); // Very slow

这是一个不容易解决的问题。一种解决方案是调用 TrimExcess每批删除后的方法。此方法通过分配新的槽数组、将项目从现有数组复制到新数组，最后丢弃旧数组，最大限度地减少类内部保留的空间。这是一项昂贵的操作，因此过于频繁地调用 TrimExcess 可能会成为应用的新瓶颈。

另一种解决方案可能是使用不受此问题困扰的第三方实现。例如Rock.Collections库包含一个 OrderedHashSet 类，该类按项目添加的顺序保留项目。它通过以链表方式连接内部槽来实现这一点。类不仅可以按正常顺序枚举，也可以按相反顺序枚举。我没有测试它，但很可能调用 First 应该是 O(1) 操作。

下面是一个使用反射来欺骗 built-in enumerator 的解决方案从随机索引而不是索引 0 开始枚举槽。它提供了可接受的性能，但受到 known problems of reflection 的影响。 (开销、前向兼容性等)。静态 GetRandom 方法位于通用静态类内部，以便为每种类型 T 单独缓存 FieldInfo 信息。

public static class HashSetRandomizer<T>
{
    private static FieldInfo _lastIndexField;
    private static FieldInfo _indexField;
    private static ThreadLocal<Random> _random;

    static HashSetRandomizer()
    {
        const BindingFlags FLAGS = BindingFlags.NonPublic | BindingFlags.Instance;
        _lastIndexField = typeof(HashSet<T>).GetField("m_lastIndex", FLAGS) // Framework
            ?? typeof(HashSet<T>).GetField("_lastIndex", FLAGS); // Core
        _indexField = typeof(HashSet<T>.Enumerator).GetField("index", FLAGS) // Framework
            ?? typeof(HashSet<T>.Enumerator).GetField("_index", FLAGS); // Core
        _random = new ThreadLocal<Random>(() => new Random());
    }

    public static T GetRandom(HashSet<T> source, Random random = null)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        random = random ?? _random.Value;
        if (_lastIndexField == null)
            throw new NotSupportedException("FieldInfo lastIndex not found.");
        if (_indexField == null)
            throw new NotSupportedException("FieldInfo index not found.");
        if (source.Count > 0)
        {
            int lastIndex = (int)_lastIndexField.GetValue(source);
            if (lastIndex > 0)
            {
                var randomIndex = random.Next(0, lastIndex);
                using (var enumerator = source.GetEnumerator())
                {
                    _indexField.SetValue(enumerator, randomIndex);
                    if (enumerator.MoveNext()) return enumerator.Current;
                }
            }
            foreach (var item in source) return item; // Fallback
        }
        throw new InvalidOperationException("The source sequence is empty.");
    }
}

使用示例。项目会从 HashSet 中随机删除，直到该集合为空。

var set = new HashSet<int>(Enumerable.Range(1, 1_000_000));
while (set.Count > 0)
{
    var item = HashSetRandomizer<int>.GetRandom(set); // Fast
    set.Remove(item);
}

即使使用这种方法，删除最后几个项目仍然很慢。