重构 IEnumerable<T> 产量

Question

今天我学到了新东西。

我有以下代码，用于创建在

links

 之间包含 

nodes

的简单图表

public class Node(string name)
{
    public string Name { get; } = name;
}

public class Link(Node from, Node to)
{
    public Node From { get; } = from;
    public Node To { get; } = to;
}

public class Graph
{
    public List<Node> Nodes = new();
    public List<Link> Links = new();

    public IEnumerable<Node> GetParents(Node node)
    {
        foreach (var link in Links)
        {
            if (link.To == node)
                yield return link.From;
        }
    }

    public IEnumerable<Node> GetChildren(Node node)
    {
        foreach (var link in Links)
        {
            if (link.From == node)
                yield return link.To;
        }
    }
}

由于存在大量节点和链接，并且由于图形高度动态，我选择不将每个节点的父节点和子节点存储在

Node

实例本身上（一个节点可以有许多父节点和许多子节点）。但相反，在

GetParents

类上有

GetChildren

和

Graph

辅助方法。

但是，我学到了一些新东西。在此过程中，由于 IEnumerable/yield 所需的支持代码，对这两个方法中的任何一个进行的每次调用都会进行分配。

如下测试所示：

[MemoryDiagnoser]
public class Test
{
    Graph _graph;

    [IterationSetup]
    public void Setup()
    {
        _graph = new Graph();

        Node a = new("A"), b = new("B"), c = new("C");

        _graph.Nodes = [a, b, c];
        _graph.Links = [new Link(a, b), new Link(a, c)];
    }

    [Benchmark]
    public void Run1()
    {
        _graph.GetParents(_graph.Nodes[1]);
    }

    [Benchmark]
    public void Run2()
    {
        _graph.GetParents(_graph.Nodes[1]);
        _graph.GetParents(_graph.Nodes[1]);
    }

    [Benchmark]
    public void RunLoop()
    {
        for (int i = 0; i < 1000; ++i)
            _graph.GetParents(_graph.Nodes[1]);
    }

    [Benchmark]
    public void GetChildren_Raw()
    {
        int count = 0;

        for (int i = 0; i < 1000; ++i)
        {
            foreach (var link in _graph.Links)
            {
                if (link.From == _graph.Nodes[1])
                {
                    count++;
                }
            }
        }
    }
}

| Method          | Mean        | Error       | StdDev       | Median      | Allocated |
|---------------- |------------:|------------:|-------------:|------------:|----------:|
| Run1            |    673.6 ns |    24.84 ns |     69.66 ns |    700.0 ns |     480 B |
| Run2            |    740.0 ns |    28.49 ns |     81.74 ns |    700.0 ns |     560 B |
| RunLoop         | 31,390.9 ns | 4,295.45 ns | 12,597.80 ns | 35,600.0 ns |   80400 B |
| GetChildren_Raw | 14,674.2 ns |   455.90 ns |  1,322.66 ns | 14,100.0 ns |     400 B |

我的问题是，除了存储每个节点的父节点和子节点（我不想做的事情，因为它是一个非常动态的图）..我如何在没有分配的情况下实现这些方法？

Answer 1

如果您希望完全优化函数

GetParents

和

GetChildren

返回的分配，那么不要返回隐式分配的引用对象。您可以使用操作来有效地执行回调，而是使用项目上的 lambda 操作。

    public void ForEachParent(Node node, Action<Link> action)
    {
        foreach (var link in Links)
        {
            if (link.To == node)
                action(link);
        }
    }

然后不要说：

   _graph.Links.ForEachParent(_graph.Nodes[1], (x) => Console.WriteLine(x));

当然，这种程度的优化会牺牲灵活性；该函数可能需要根据调用者的要求进行定制以执行其他操作。这是一种侵入式优化。

有一个这样做的用例；但与此级别的任何类型的优化一样，必须仔细权衡其侵入性、刚性和相对维护开销，以及您将看到多少 CPU 成本效益以及需要多少 CPU 成本效益。

一个旁注是，如果您要达到这种优化级别，我们开始为了纯粹的迭代速度而牺牲开发人员的可用性，请不要使用 foreach。它不如索引那么快。