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 |

除了存储每个节点的父节点和子节点（我不想这样做，因为它是一个非常动态的图）之外，我怎样才能在没有分配的情况下实现这些方法？

如果您想要GetChildren并且根本GetParents不分配，它们必须返回一个现有对象 – 这意味着要么拥有一个可变对象（呃 – 非常非常脆弱）要么每个节点都有一个对象（一个用于子节点，一个用于父节点），您也说过您不想要。这些只是基本问题，没有任何实施问题。那么，您如何期望能够在没有任何分配的情况下实现这些方法？（当然，您可以使用列表或类似的东西缓存“最后返回”的对象……但这是一个常见的用例吗？） — 
是否可以选择将（缓存的）父/子信息保存为Graph类中的字典IDictionary<Node, ISet<Node>>？ — 
@Progman 并非如此，它是一个动态图，因此任何缓存都会因过于频繁而失效而无法使用。 — 
使用yield return更改该方法以返回实现该 IEnumerable 的生成类 —

Accepted Answer

List<T>foreach通过让其方法返回实现的，避免在语句中使用时进行分配IEnumerator<T>。来自的参考List<T>：

public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
    public Enumerator GetEnumerator()
        => new Enumerator(this);

    IEnumerator<T> IEnumerable<T>.GetEnumerator()
        => new Enumerator(this);

    IEnumerator IEnumerable.GetEnumerator()
       => new Enumerator(this);

    public struct Enumerator : IEnumerator<T>, IEnumerator
    {
         // Implementation omitted
    }

只要明确实现了IEnumerable<T>.GetEnumerator()和IEnumerable.GetEnumerator()方法，运行时就会选择公共GetEnumerator()方法并将其插入到所有foreach循环中，而不会对返回的枚举器进行装箱。

您可以采用相同的方法，将List<Link>.Enumerator自己的枚举器结构包装为必要的过滤逻辑。首先在内部引入以下可枚举和枚举器Graph：

public partial class Graph
{
    public struct NodeEnumerable : IEnumerable<Node>
    {
        readonly Graph graph;
        readonly Node node;
        readonly Func<Link, Node> getFilterNode;
        readonly Func<Link, Node> getReturnNode;
        
        internal NodeEnumerable(Graph graph, Node node, Func<Link, Node> getFilterNode, Func<Link, Node> getReturnNode) =>
            (this.graph, this.node, this.getFilterNode, this.getReturnNode) = (graph, node, getFilterNode, getReturnNode);
        
        public NodeEnumerator GetEnumerator() => new NodeEnumerator(graph.Links.GetEnumerator(), node, GetTo, GetFrom);
        IEnumerator<Node> IEnumerable<Node>.GetEnumerator() => GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

        public struct NodeEnumerator : IEnumerator<Node>, IEnumerator
        {
            List<Link>.Enumerator enumerator;
            readonly Node node;
            readonly Func<Link, Node> getFilterNode;
            readonly Func<Link, Node> getReturnNode;

            internal NodeEnumerator(List<Link>.Enumerator enumerator, Node node, Func<Link, Node> getFilterNode, Func<Link, Node> getReturnNode) => 
                (this.enumerator, this.node, this.getFilterNode, this.getReturnNode) = (enumerator, node, getFilterNode, getReturnNode);

            public void Dispose() => enumerator.Dispose();
            public Node Current => getReturnNode(enumerator.Current);
            void IEnumerator.Reset() => enumerator.Reset();

            object? IEnumerator.Current => Current;

            public bool MoveNext()
            {
                while (enumerator.MoveNext())
                    if (getFilterNode(enumerator.Current) == node)
                        return true;
                return false;
            }
        }
    }
}

public static class EnumeratorExtensions
{
    // Use to avoid boxing enumerator structs that implement Reset explicitly
    public static void Reset<TEnumerator>(ref this TEnumerator enumerator) where TEnumerator : struct, IEnumerator => 
        enumerator.Reset();
}

然后修改GetParents()如下GetChildren()：

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

    public NodeEnumerable GetParents(Node node) => new NodeEnumerable(this, node, GetTo, GetFrom);

    public IEnumerable<Node> GetChildren(Node node) => new NodeEnumerable(this, node, GetFrom, GetTo);
    
    // Make these delegates static to avoid allocations
    readonly static Func<Link, Node> GetFrom = static n => n.From;
    readonly static Func<Link, Node> GetTo = static n => n.To;
}

现在foreach循环遍历父级和子级将不再分配内存（如在 .NET 8 中运行）

Environment version: .NET 8.0.8 (8.0.8), Microsoft Windows NT 10.0.19045.0

| Method          | Mean        | Error     | StdDev      | Median      | Allocated |
|---------------- |------------:|----------:|------------:|------------:|----------:|
| Run1            |    200.0 ns |   0.00 ns |     0.00 ns |    200.0 ns |     400 B |
| Run2            |    282.3 ns |  13.30 ns |    38.37 ns |    300.0 ns |     400 B |
| RunLoop         | 25,766.3 ns | 710.75 ns | 2,004.68 ns | 25,100.0 ns |     400 B |
| GetChildren_Raw | 18,692.0 ns | 606.99 ns | 1,661.62 ns | 18,500.0 ns |     400 B |

笔记：

List<T>.GetEnumerator()返回 .NET 运行时将会注意并使用的可变结构的优化从 .NET 2 开始就已经存在。
如果将 aList<T>向上转换为 an，IList<T>则优化将会丢失，并且列表枚举器将被装箱。
但是 LINQ 会通过检查传入的枚举是否实际上是列表，然后将其枚举器包装在专门的包含枚举器中来避免这种装箱，该枚举器明确声明了列表枚举器，例如。如果您经常将和返回的可枚举传递到某些 LINQ 表达式中，您可能需要执行类似操作。GetParents()GetChildren()
GetParents()我对和都使用了一个结构体，并为和逻辑GetChildren()传递了静态委托。为了获得绝对最大的性能，如果您想避免委托回调，您可以为每个单独的枚举器。FromTo
对于另一个性能调整，您可能想要调查避免使用readonly字段关键字是否会导致速度提升。有关为什么这可能是真的，请参阅的。

这里付出了很多努力，回答得很好；小事一桩：现在很多 API 都用于[ReadOnly]不会改变状态的成员，这避免了很多只读复制问题（在现代运行时） — 
ReadOnlyAttribute是的成员System.ComponentModel，因此实际上似乎不是一个通用属性。我找不到任何 C# 文档说明此属性可以影响编译时或 JIT 代码 – 我是否遗漏了什么？ — 
真的很感激。说实话，这可能超出了我的理解范围，但我会尽力去理解。 — 
@jessejbweld – 很高兴能帮上忙。顺便说一句， JonasH值得考虑。您可以将与结合起来，创建一个双向集合，跟踪每个父级的多个子级。 —

Answer 2

如果您希望完全优化函数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));

注意：这是一个非常简单的示例，用于展示其用法；我们确实在对操作进行分配。然而，重要的是，这可以很容易地重构到 for 循环之外，甚至在类实例之外，并在需要时将其设为静态。

优化平衡

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

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

进一步讨论

如果我们达到了这种优化水平，开始牺牲开发人员的可用性来换取纯粹的迭代速度，请考虑避免使用foreach。它不如索引的快for。

在我的例子中，我还提到使用 lambda。如果使用“硬”函数而不是 lambda，速度会更快。

谢谢，我确实尝试了 lambda，因为它们在我发布问题后立即出现在我脑海中（对我来说通常都是这样 :P）。它们工作得很好，但现在代码看起来很奇怪，所以需要额外的注释来解释原因……这总是一个不好的迹象……可能会恢复它 😛 — 
确实，如果代码需要注释，那就很糟糕了。如果您确实使用了 lambda，请在上一行中将其功能性地命名。或者可以考虑使用。或者有时最好使用命名的“真实”函数；我提供的解决方案将采用上述任何一种并隐式实例化Action。您甚至可以让Actiona 成员停止每次都必须实例化它。我认为您不会找到其他答案。 —

Answer 3

我认为你忽略了这里更大的问题。每次你想让子节点或父节点到达某个节点时，你都需要遍历图中的所有链接。一旦图的大小开始变大，这就会是一个比几次分配更大的问题。

更典型的解决方案是使用字典来存储链接：

Dictionary<Node, List<Node>> links = new ();

这样您就可以快速找到所有连接的节点。要添加双向链接，只需将每个节点添加到彼此的列表中。这种方法还可以方便地避免分配问题。

您可以将此字典制作成一个单独的辅助类，其中包含在添加节点的第一个链接时自动创建列表的方法。这有时称为MultiValueDictionary，并且在许多情况下可能是一个有用的集合。

我在问题中解释过，我不想缓存任何东西，因为状态变化太频繁，缓存没有任何实际好处，而且有些逻辑非常特定于我正在解决的问题，缓存不太适用。事后看来，我本可以不带任何图表来问这个问题。我本应该问的是，“你能实现一个没有分配的收益方法吗？”:) — 
@jessejbweld 我真的不明白你说的“缓存”是什么意思。这不是缓存，而是图表的完整描述。其他答案已经涵盖了分配问题，但在提问时你应该提到实际的应用程序以避免 XY 问题。使用O(n)算法，即使只是作为一个例子，当 aO(1)可以做到时，我会怀疑你是否把时间花在了正确的问题上。 — 
这是一个动态图表，链接经常变化，所以我需要不断更新你建议的字典。 — 
@jessejbweld 是的，但是字典的添加和删除都是O(1)。而从列表中删除是O(n)，因此唯一一个列表更好的情况是，如果您只添加链接，而从不进行遍历或删除。您还可以考虑使用 HashSet 而不是 List 作为内部集合。自定义集合可能会做得更好，但需要更多关于如何修改此图的知识。 —

c# – 重构 IEnumerable 收益 – 堆栈内存溢出

最佳答案
3

优化平衡

进一步讨论

最佳答案 3

优化平衡

进一步讨论

最佳答案
3