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

声明:本页面是StackOverFlow热门问题的中英对照翻译,遵循CC BY-SA 4.0协议,如果您需要使用它,必须同样遵循CC BY-SA许可,注明原文地址和作者信息,同时你必须将它归于原作者(不是我):StackOverFlow 原文地址: http://stackoverflow.com/questions/252917/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me): StackOverFlow

提示:将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间:2020-08-03 20:03:15  来源:igfitidea点击:

Fastest way to iterate over a stack in c#

c#optimizationstack

提问by Adam Naylor

I feel that using GetEnumerator() and casting IEnumerator.Current is expensive. Any better suggestions?

I'm open to using a different data structure if it offers similiar capabilities with better performance.

我觉得使用 GetEnumerator() 和转换 IEnumerator.Current 很昂贵。有什么更好的建议吗?

如果它提供类似的功能和更好的性能,我愿意使用不同的数据结构。

After thought:
Would a generic stack be a better idea so that the cast isn't necessary?

经过思考:
通用堆栈是否是一个更好的主意,这样就不需要演员表了?

采纳答案by Mats Fredriksson

Have you done any benchmarks, or are they just gut feelings?

您是否做过任何基准测试,或者它们只是直觉?

If you think that the majority of the processing time is spent looping through stacks you should benchmark it and make sure that that is the case. If it is, you have a few options.

如果您认为大部分处理时间都花在遍历堆栈上,那么您应该对其进行基准测试并确保是这种情况。如果是,您有几个选择。

  1. Redesign the code so that the looping isn't necessary
  2. Find a faster looping construct. (I would recommend generics even though it wouldn't matter that much. Again, do benchmarks).
  1. 重新设计代码,以便不需要循环
  2. 找到一个更快的循环结构。(我会推荐泛型,即使它没有那么重要。再次,做基准测试)。

EDIT:

编辑:

Examples of looping that might not be necessary are when you try to do lookups in a list or match two lists or similar. If the looping takes a long time, see if it make sense to put the lists into binary trees or hash maps. There could be an initial cost of creating them, but if the code is redesigned you might get that back by having O(1) lookups later on.

可能不需要的循环示例是当您尝试在列表中查找或匹配两个列表或类似内容时。如果循环需要很长时间,看看将列表放入二叉树或哈希映射是否有意义。创建它们可能会产生初始成本,但如果重新设计代码,您可能会通过稍后进行 O(1) 查找来收回成本。

回答by csgero

Yes, using a generic stack will spare the cast.

是的,使用通用堆栈将节省演员阵容。

回答by Timothy Khouri

If you need the functionality of a Stack (as apposed to a List, or some other colleciton type), then yes, use a generic stack. This will speed things up a bit as the compiler will skip the casting at runtime (because it's garunteed at compile time).

如果您需要堆栈的功能(与列表或其他一些集合类型相关),那么是的,请使用通用堆栈。这将加快速度,因为编译器将在运行时跳过转换(因为它在编译时是 garunteed)。

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

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

回答by Pop Catalin

Enumerating over a generic IEnumerable<T>or IEnumerator<T>doesn't create a cast if the iterating variable is of type T, so yes using the generic is going to be faster in most cases, but generics have some very subtle issues, especially when used with value types.

如果迭代变量的类型为 T,则枚举泛型IEnumerable<T>IEnumerator<T>不创建强制转换,因此在大多数情况下使用泛型会更快,但泛型有一些非常微妙的问题,尤其是在与值类型一起使用时。

Rico Mariani (Microsoft performance architect) has some posts detailing the differences and the underpinnings

Rico Mariani(微软性能架构师)有一些帖子详细介绍了差异和基础

回答by Martin v. L?wis

An alternative to creating an enumerator is to use the ToArray method, and then iterate over the array. The stack iterator causes some slight overhead for checking whether the stack has been modified, whereas iteration over the array would be fast. However, there is of course the overhead of creating the array in the first place. As mats says, you should benchmark the alternatives.

创建枚举器的另一种方法是使用 ToArray 方法,然后遍历数组。堆栈迭代器在检查堆栈是否已被修改时会产生一些轻微的开销,而对数组的迭代会很快。但是,首先当然有创建数组的开销。正如垫子所说,您应该对替代品进行基准测试。

回答by Marc Gravell

Stack<T>(with foreach) would indeed save the cast, but actually boxing isn't all thatbadin the grand scheme of things. If you have performance issues, I doubt this is the area where you can add much value. Use a profiler, and focus on real problems - otherwise this is premature.

Stack<T>(使用foreach)确实可以挽救演员阵容,但实际上拳击在宏伟的计划中并不是那么糟糕。如果您有性能问题,我怀疑这是您可以增加很多价值的领域。使用分析器,并专注于实际问题 - 否则为时过早。

Note that if you only want to read the data once (i.e. you are happy to consume the stack), then this maybe quicker (avoids the overhead of an enumerator); YMMV.

请注意,如果您只想读取一次数据(即您乐于使用堆栈),那么这可能会更快(避免枚举器的开销);天啊。

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

回答by Rob Bennet

As far as speed is concerned there are multiple variables, depends on the context. For example, in a auto-memory-managed codebase like C#, you can get allocation spikes which can affect framerate in something like, say, a game. A nice optimization you can make for this instead of a foreach is an enumerator with a while loop:

就速度而言,有多个变量,取决于上下文。例如,在像 C# 这样的自动内存管理代码库中,您可能会遇到分配峰值,这会影响诸如游戏之类的帧率。您可以为此进行的一个很好的优化而不是 foreach 是一个带有 while 循环的枚举器:

var enumerator = stack.GetEnumerator();

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

As far as CPU benchmarks, this probably isn't any faster than a foreach, but foreach can have unintended allocation spikes, which can ultimately "slow down" the performance of your application.

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