La forma más rápida de iterar sobre una pila en C #

Question

Siento que usar GetEnumerator () y lanzar IEnumerator.Current es costoso. ¿Alguna sugerencia mejor?

Estoy abierto a usar una estructura de datos diferente si ofrece capacidades similares con un mejor rendimiento.

Pensamiento posterior:
¿Sería una mejor idea una pila genérica para que el lanzamiento no sea necesario?

Answer 1

¿Has hecho algún punto de referencia, o son solo sensaciones?

Si cree que la mayor parte del tiempo de procesamiento se pasa recorriendo las pilas, debe compararlo y asegurarse de que ese sea el caso. Si es así, tiene algunas opciones.

1. Rediseña el código para que el bucle no sea necesario
2. Encuentra una construcción de bucle más rápida. (Recomendaría genéricos aunque no importaría tanto. Nuevamente, haga puntos de referencia).

EDITAR:

Ejemplos de bucles que pueden no ser necesarios son cuando intenta hacer búsquedas en una lista o hacer coincidir dos listas o similares. Si el bucle lleva mucho tiempo, vea si tiene sentido colocar las listas en árboles binarios o mapas hash. Podría haber un costo inicial de crearlos, pero si el código se rediseña, puede recuperarlo al tener búsquedas O (1) más adelante.

Answer 2

Stack<T> (con foreach) realmente salvaría el elenco, pero en realidad boxeando no es todo eso malo en el gran esquema de las cosas. Si tiene problemas de rendimiento, dudo que esta sea el área donde puede agregar mucho valor. Use un generador de perfiles y concéntrese en problemas reales; de lo contrario, esto es prematuro.

Tenga en cuenta que si solo desea leer los datos una vez (es decir, está contento de consumir la pila), entonces esto puede ser más rápido (evita la sobrecarga de un enumerador); YMMV.

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

Answer 3

Sí, usar una pila genérica ahorrará el lanzamiento.

Answer 4

Si necesita la funcionalidad de una Pila (como se le asigna a una Lista, o algún otro tipo de colección), entonces sí, use una pila genérica. Esto acelerará un poco las cosas, ya que el compilador se saltará el casting en tiempo de ejecución (porque es voluntario en tiempo de compilación).

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

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

Answer 5

enumerar sobre un genérico IEnumerable<T> o IEnumerator<T> no crea una conversión si la variable iterativa es de tipo T, por lo que sí, usar el genérico será más rápido en la mayoría de los casos, pero los genéricos tienen algunos problemas muy sutiles, especialmente cuando se usan con tipos de valor.

Rico Mariani (arquitecto de rendimiento de Microsoft) tiene algunas publicaciones que detallan las diferencias y los fundamentos

• Seis preguntas sobre genéricos y rendimiento
• Prueba de rendimiento n.º 7: mejoras genéricas y costes
• Prueba de rendimiento n.º 7 - Mejoras genéricas y costos - Solución

Answer 6

En cuanto a la velocidad, existen múltiples variables, depende del contexto. Por ejemplo, en una base de código administrada de memoria automática como C #, puede obtener picos de asignación que pueden afectar la velocidad de fotogramas en algo como, por ejemplo, un juego. Una buena optimización que puede hacer para esto en lugar de un foreach es un enumerador con un ciclo while:

var enumerator = stack.GetEnumerator();

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

En cuanto a los puntos de referencia de la CPU, esto probablemente no sea más rápido que un foreach, pero foreach puede tener picos de asignación no intencionados, que en última instancia pueden " ralentizar " el rendimiento de su aplicación.

Answer 7

Una alternativa para crear un enumerador es utilizar el método ToArray y luego iterar sobre la matriz. El iterador de la pila causa una ligera sobrecarga para verificar si la pila se ha modificado, mientras que la iteración sobre la matriz sería rápida. Sin embargo, existe la sobrecarga de crear la matriz en primer lugar. Como dice esteras, debe comparar las alternativas.