在C#中迭代堆栈的最快方法

Question

我感觉使用GetEnumerator()和强制类型转换IEnumerator.Current是很耗费性能的。有更好的建议吗？

如果有其他数据结构可以提供类似的功能并且具有更好的性能，我也可以接受。

想法：
使用泛型栈是否会更好，这样就不需要进行强制类型转换了？

- Adam Naylor

---

它们都会是一样的... 当使用值类型时，强制转换只会稍微慢一点。根据使用情况，我怀疑它不会对性能产生太大影响。 - leppie

Answer 1

Stack<T>（带foreach）确实可以省去类型转换，但是在总体上实际装箱并不是那么糟糕。如果您有性能问题，我怀疑这不是您可以增加多少价值的领域。使用分析器，并专注于真正的问题，否则这将是过早的。

请注意，如果您只想读取数据一次（即满足于使用堆栈），则这可能会更快（避免枚举器的开销）。个人情况各异。

    Stack<T> stack = null;
    while (stack.Count > 0)
    {
        T value = stack.Pop();
        // process value
    }

- Marc Gravell

Answer 2

你做过任何基准测试吗，还是只是凭直觉？

如果你认为大部分处理时间都花在循环遍历栈上，那么应该进行基准测试并确保情况确实如此。如果是这样，你有几个选择。

1. 重新设计代码，使循环不再必要
2. 找到更快的循环结构。（我会推荐使用泛型，尽管这不会有太大影响。再次进行基准测试）

编辑：

可能不需要循环遍历的循环示例包括尝试在列表中查找或匹配两个列表等。如果循环花费了很长时间，请看看是否有意义将列表放入二叉树或哈希映射中。虽然创建它们可能会有一些初始成本，但如果重新设计代码，您可能会通过具有O（1）查找的后续操作获得回报。

- mats

---

是的，现在只是一种感觉。我会运行一些基准测试来确认。谢谢。 - Adam Naylor

Answer 3

如果你需要使用堆栈的功能（而不是列表或其他集合类型），那么是的，使用通用堆栈。这将加快速度，因为编译器会在编译时跳过强制转换（因为它在编译时已经保证了）。

Stack<MyClass> stacky = new Stack<MyClass>();

foreach (MyClass item in stacky)
{
    // this is as fast as you're going to get.
}

- Timothy Khouri

Answer 4

是的，使用通用堆栈将节省强制转换的步骤。

- csgero

Answer 5

枚举泛型的 IEnumerable<T> 或 IEnumerator<T> 不会创建转换，如果迭代变量是类型 T，则在大多数情况下使用泛型会更快，但泛型存在一些非常微妙的问题，特别是在与值类型一起使用时。

Rico Mariani（微软性能架构师）有一些帖子详细介绍了差异和基础知识。

• 关于泛型和性能的六个问题
• 性能测试 #7 -- 泛型改进和成本
• 性能测试 #7 -- 泛型改进和成本 -- 解决方案

- Pop Catalin

Answer 6

就速度而言，有多个变量，这取决于上下文。例如，在像C#这样的自动内存管理代码库中，您可能会遇到分配峰值，这可能会影响游戏帧率。您可以进行一项不错的优化，而不是使用foreach，可以使用具有while循环的枚举器：

var enumerator = stack.GetEnumerator();

while(enumerator.MoveNext ()) {
  // do stuff with enumerator value using enumerator.Current
  enumerator.Current = blah
}

就CPU基准测试而言，这可能不比foreach更快，但是foreach可能会产生意外的分配峰值，最终可能会“降低”应用程序的性能。

- Rob Bennet

Answer 7

创建枚举器的另一种方法是使用ToArray方法，然后迭代数组。堆栈迭代器会导致一些轻微的开销，用于检查堆栈是否已被修改，而对数组进行迭代将会很快。但是，首先创建数组当然会有开销。正如mats所说，您应该对这些替代方案进行基准测试。

- Martin v. Löwis

---

使用“ToArray”非常昂贵...在您开始迭代之前，创建新对象的方式会导致巨大的性能损失。 - Timothy Khouri

你确定它非常昂贵吗？你有测量过吗？ - Martin v. Löwis