优化IEnumerable<T> yield实现：无分配获取动态图节点的父/子节点

针对你提到的动态图中yield生成状态机导致内存分配的问题，以下是几种不需要在Node中存储父/子引用的无分配实现方案：

方案1：回调委托（Callback Delegate） #

直接通过遍历图中所有链接，将符合条件的节点传递给预先定义的回调方法，完全避免枚举器对象的分配。

实现代码 #

public class Graph
{
    private readonly List<Link> _links = new List<Link>();

    // 查询子节点：遍历所有链接，匹配源节点时调用回调
    public void GetChildren(Node node, Action<Node> callback)
    {
        foreach (var link in _links)
        {
            if (link.Source == node)
            {
                callback(link.Target);
            }
        }
    }

    // 查询父节点同理：匹配目标节点时调用回调
    public void GetParents(Node node, Action<Node> callback)
    {
        foreach (var link in _links)
        {
            if (link.Target == node)
            {
                callback(link.Source);
            }
        }
    }
}

// 使用示例：预先分配回调避免匿名委托的分配
public class NodeProcessor
{
    private static readonly Action<Node> _processChild = node =>
    {
        // 处理子节点的业务逻辑
        Console.WriteLine($"Processing child node: {node.Id}");
    };

    public void ProcessChildren(Graph graph, Node targetNode)
    {
        graph.GetChildren(targetNode, _processChild);
    }
}

优缺点 #

• ✅ 完全无堆分配（只要回调是预先定义的静态/实例委托）
• ✅ 实现简单，无需额外类型定义
• ❌ 写法不如foreach直观，处理逻辑需嵌入回调

方案2：自定义结构体枚举器 #

利用值类型枚举器（结构体）替代yield生成的类枚举器，避免堆内存分配。结构体枚举器会在栈上分配，不会触发GC。

实现代码 #

public class Graph
{
    internal readonly List<Link> _links = new List<Link>();

    // 返回自定义结构体枚举器
    public ChildrenEnumerator GetChildrenEnumerator(Node node)
    {
        return new ChildrenEnumerator(this, node);
    }

    public ParentsEnumerator GetParentsEnumerator(Node node)
    {
        return new ParentsEnumerator(this, node);
    }

    // 子节点枚举器（结构体，值类型）
    public struct ChildrenEnumerator : IEnumerator<Node>
    {
        private readonly Graph _graph;
        private readonly Node _source;
        private int _currentIndex;
        private Node _currentNode;

        public ChildrenEnumerator(Graph graph, Node source)
        {
            _graph = graph;
            _source = source;
            _currentIndex = -1;
            _currentNode = null;
        }

        public Node Current => _currentNode;
        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            while (++_currentIndex < _graph._links.Count)
            {
                var link = _graph._links[_currentIndex];
                if (link.Source == _source)
                {
                    _currentNode = link.Target;
                    return true;
                }
            }
            _currentNode = null;
            return false;
        }

        public void Reset()
        {
            _currentIndex = -1;
            _currentNode = null;
        }

        public void Dispose()
        {
            // 无资源需要释放，空实现
        }
    }

    // 父节点枚举器同理
    public struct ParentsEnumerator : IEnumerator<Node>
    {
        private readonly Graph _graph;
        private readonly Node _target;
        private int _currentIndex;
        private Node _currentNode;

        public ParentsEnumerator(Graph graph, Node target)
        {
            _graph = graph;
            _target = target;
            _currentIndex = -1;
            _currentNode = null;
        }

        public Node Current => _currentNode;
        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            while (++_currentIndex < _graph._links.Count)
            {
                var link = _graph._links[_currentIndex];
                if (link.Target == _target)
                {
                    _currentNode = link.Source;
                    return true;
                }
            }
            _currentNode = null;
            return false;
        }

        public void Reset()
        {
            _currentIndex = -1;
            _currentNode = null;
        }

        public void Dispose() { }
    }
}

// 使用示例：直接用foreach遍历结构体枚举器
public void ProcessChildren(Graph graph, Node targetNode)
{
    foreach (var child in graph.GetChildrenEnumerator(targetNode))
    {
        Console.WriteLine($"Processing child node: {child.Id}");
    }
}

优缺点 #

• ✅ 保持foreach的直观语法，无堆分配
• ✅ 枚举器是值类型，栈分配，GC压力为0
• ❌ 需要编写较多样板代码
• ❌ 枚举过程中如果图的链接集合被修改（增删），会导致遍历异常，需自行处理并发/一致性问题

方案3：池化枚举器对象 #

通过对象池复用枚举器实例，避免每次查询都创建新的枚举器对象，减少堆分配次数。

实现代码 #

public class Graph
{
    private readonly List<Link> _links = new List<Link>();
    private static readonly ObjectPool<PooledChildrenEnumerator> _childrenEnumeratorPool =
        new DefaultObjectPool<PooledChildrenEnumerator>(new PooledPolicy());

    public PooledChildrenEnumerator GetPooledChildrenEnumerator(Node node)
    {
        var enumerator = _childrenEnumeratorPool.Get();
        enumerator.Initialize(this, node);
        return enumerator;
    }

    // 池化的子节点枚举器
    public class PooledChildrenEnumerator : IEnumerator<Node>
    {
        private Graph _graph;
        private Node _source;
        private int _currentIndex;
        private Node _currentNode;

        public void Initialize(Graph graph, Node source)
        {
            _graph = graph;
            _source = source;
            _currentIndex = -1;
            _currentNode = null;
        }

        public Node Current => _currentNode;
        object IEnumerator.Current => Current;

        public bool MoveNext()
        {
            while (++_currentIndex < _graph._links.Count)
            {
                var link = _graph._links[_currentIndex];
                if (link.Source == _source)
                {
                    _currentNode = link.Target;
                    return true;
                }
            }
            _currentNode = null;
            return false;
        }

        public void Reset()
        {
            _currentIndex = -1;
            _currentNode = null;
        }

        public void Dispose()
        {
            // 用完放回对象池
            _childrenEnumeratorPool.Return(this);
        }
    }

    // 对象池策略
    private class PooledPolicy : IPooledPolicy<PooledChildrenEnumerator>
    {
        public PooledChildrenEnumerator Create() => new PooledChildrenEnumerator();

        public bool Return(PooledChildrenEnumerator obj)
        {
            // 重置状态，避免脏数据
            obj.Initialize(null, null);
            return true;
        }
    }
}

// 使用示例：using语句确保枚举器放回池
public void ProcessChildren(Graph graph, Node targetNode)
{
    using var enumerator = graph.GetPooledChildrenEnumerator(targetNode);
    while (enumerator.MoveNext())
    {
        Console.WriteLine($"Processing child node: {enumerator.Current.Id}");
    }
}

优缺点 #

• ✅ 兼容现有基于IEnumerator的代码
• ✅ 大幅减少枚举器对象的分配（复用实例）
• ❌ 需要维护对象池，增加复杂度
• ❌ 仍有首次分配的开销，适合高频查询场景

额外优化建议 #

如果图的动态修改频率不是极端高，可以考虑按源/目标节点分组缓存链接（比如Dictionary<Node, List<Link>>），每次链接增删时同步更新分组。这样查询父/子节点时无需遍历所有链接，直接从分组中获取，同时结合上述无分配方案，能进一步提升性能。但需注意分组缓存的维护成本，若图修改非常频繁，可能得不偿失。

内容的提问来源于stack exchange，提问作者jessejbweld