从 HashSet 获取第一个（或任何）值

Question

目前，我的代码如下所示：

    private List<Node> dirtyNodes = new List<Node> dirtyNodes();

    public void UpdateDirtyNodes()
    {
        while(dirtyNodes.Count > 0)
        {
            Node nodeToUpdate = dirtyNodes[0];
            nodeToUpdate.UpdateNode();
            dirtyNodes.Remove(nodeToUpdate);
        }
    }

    public void MarkNodeDirty(Node node)
    {
        if(!dirtyNodes.Contains(node))
        {
            dirtyNodes.Add(node);
        }
    }

    public void MarkNodeClean(Node node)
    {
        dirtyNodes.Remove(node);
    }

这是代码的性能关键部分，它比我想要的要慢，因为在大多数情况下 dirtyNodes.Contains 必须遍历整个数组。我想用 HashSet 替换 List 因为它应该更快，但我不知道如何使用 UpdateDirtyNodes().

困难在于 UpdateNode() 可以随时从 dirtyNodes 添加或删除节点，因此 while 循环有点笨拙。有没有办法从 HashSet 中获取“第一个”值？顺序无关紧要，我只需要留在 while 循环中，直到 dirtyNodes 为空，更新下一个节点。

我宁愿避免使用 Linq，因为此代码将成为库的一部分，我不想强迫他们包含 Linq。

我该怎么做？

Answer 1

在 Node class 内添加一个 bool dirty 字段。这是除了保留哈希集之外。然后 MarkNodeClean() 不需要从 HashSet 中删除节点，减少一些 CPU 周期。

如果你觉得在 Node class 中添加一个字段太“脏”（双关语意），那么就做一个 HashSet<(Node, bool)> 而不是 HashSet<Node>，但是您正在失去分配和垃圾收集额外对象的性能，这并不理想，因为您的代码对性能至关重要。

UpdateDirtyNodes() 将一次取一个节点，直到 HashSet 为空。在获取每个节点后，它会查看布尔标志来决定该节点是否实际上是脏的。

P.S. 您应该从 UpdateDirtyNodes() 中删除 dirtyNodes.Clear();。这是一个竞争条件。如果while循环发现dirtyNodes.Count为0后又增加了一个结点，那么dirtyNodes.Clear();就把那个结点清除掉，不做任何处理。这是一个单独的错误，与您的问题无关。

Answer 2

事实证明，直接使用枚举器非常简单：

    public void UpdateDirtyNodes()
    {
        while(dirtyNodes.Count > 0)
        {
            using(HashSet<Node>.Enumerator enumerator = dirtyNodes.GetEnumerator())
            {
                if(enumerator.MoveNext())
                {
                    Node nodeToUpdate = enumerator.Current;
                    nodeToUpdate.UpdateNode();
                    dirtyNodes.Remove(nodeToUpdate);
                }
            }
        }
    }

    public void MarkNodeDirty(Node node)
    {
        dirtyNodes.Add(node);
    }

我最初尝试过类似的方法，但没有完全理解如何手动使用枚举器，但没有成功。

它比 List 快得多（整体帧时间快约 25-50%，具体取决于这一变化的情况）所以我很高兴。（不要对下面屏幕截图中的 30MB 分配感到恐慌 - 我正在处理它。）

从 HashSet 获取第一个（或任何）值

Get first (or any) value from HashSet

c#

hashset