Maneira mais rápida de iterar sobre uma pilha em C#

Question

Eu sinto que usar getenumerator () e fundindo ienumerator.current é caro. Alguma sugestão melhor?

Estou aberto a usar uma estrutura de dados diferente se oferecer recursos semelhantes com melhor desempenho.

Depois do pensamento:
Uma pilha genérica seria uma idéia melhor para que o elenco não fosse necessário?

Answer 1

Você fez algum benchmarks ou eles são apenas sentimentos intestinais?

Se você acha que a maior parte do tempo de processamento é gasta em pilhas, você deve comparar e garantir que seja esse o caso. Se for, você tem algumas opções.

1. Redesenhe o código para que o loop não seja necessário
2. Encontre uma construção de loop mais rápida. (Eu recomendaria genéricos, mesmo que não importaria muito. Novamente, faça benchmarks).

EDITAR:

Exemplos de loop que podem não ser necessários são quando você tenta fazer pesquisas em uma lista ou combinar duas listas ou similares. Se o loop levar muito tempo, veja se faz sentido colocar as listas em árvores binárias ou mapas de hash. Pode haver um custo inicial de criá -los, mas se o código for redesenhado, você poderá recuperar isso com as pesquisas O (1) mais tarde.

Answer 2

Stack<T> (with foreach) would indeed save the cast, but actually boxing isn't all that bad in 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.

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

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

Answer 3

Yes, using a generic stack will spare the cast.

Answer 4

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).

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

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

Answer 5

enumerating over a generic IEnumerable<T> or IEnumerator<T> doesn'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.

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

• Six Questions about Generics and Performance
• Performance Quiz #7 -- Generics Improvements and Costs
• Performance Quiz #7 -- Generics Improvements and Costs -- Solution

Answer 6

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:

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.

Answer 7

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.