时间戳

首页 > 解决方案 > 从 HashSet 中选择“任何”项目非常慢 - 如何快速做到这一点？

c# - 从 HashSet 中选择“任何”项目非常慢 - 如何快速做到这一点？

问题描述

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

根据 MSDN 文档：

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 );
}

即：具有多组的典型贪心算法：一组“下一次迭代的起点”，以及一组或多组（这里我只展示了一组）“尚未处理且以某种方式连接的数据”到/从起点到达”。

......那里的一切都很快，唯一慢的是“第一个”电话 - 我没有理由拿第一个，我可以拿任何，但我需要拿点东西！

标签： c#

解决方案

似乎HashSet该类并未针对其第一项被重复删除的场景进行优化。该类内部保留的空间在每次移除后不会减少，而是将相应的插槽标记为空。类的枚举器枚举所有内部槽，并在找到非空槽时产生一个值。当 a 的内部空间HashSet变得稀疏时，这可能会变得非常低效。例如HashSet，曾经拥有 1,000,000 个元素并已缩减为单个元素的 a 必须枚举 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) 操作。

下面是一个使用反射来欺骗内置枚举器从随机索引而不是索引 0 开始枚举槽的解决方案。它提供了可接受的性能，但它存在已知的反射问题（开销，前向兼容性等）。静态GetRandom方法位于通用静态类中，以便FieldInfo为每种类型分别缓存信息T。

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.");
    }
}

用法示例。项目从 a 中随机删除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);
}

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

推荐阅读