multidimensional - initialize array c#

Aritmética de gran variedad en C#

Question

¿Cuál es la mejor manera de almacenar una matriz 2D en c # para optimizar el rendimiento cuando se realiza una gran cantidad de aritmética en los elementos de la matriz?

Tenemos matrices grandes (aproximadamente 1.5G), que por ejemplo queremos multiplicar entre sí elemento por elemento. El rendimiento es crítico. El contexto en el que esto se hace está en c #. ¿Hay alguna forma inteligente de almacenar las matrices y de iterar sobre ellas? ¿Podríamos escribir estas partes en C ++ no administrado y esto realmente aumentará el rendimiento? Las matrices deben estar accesibles para el resto del programa c #.

Actualmente (en c) la matriz se almacena como un único vector largo. Realizamos cálculos en cada elemento de la matriz y sobrescribimos el valor anterior. Los cálculos suelen ser únicos para cada elemento del vector.

Los experimentos de temporización muestran que almacenar e iterar sobre los datos como una matriz en C # es más lento que almacenarlos como una matriz 2D. Me gustaría saber si hay una forma mejor de manejar los datos. Las aritméticas específicas realizadas no son relevantes para la pregunta.

Answer 1

¿Usted itera la matriz por la fila o por la columna o ambas? ¿Siempre accedes a elementos cercanos o haces accesos aleatorios en la matriz?

Si hay alguna localidad en sus accesos pero no está accediendo a ella de forma secuencial (típica en la multiplicación de matrices, por ejemplo), entonces puede obtener una gran diferencia de rendimiento al almacenar su matriz de una manera más amigable con la caché.

Una forma bastante fácil de hacerlo es escribir una pequeña función de acceso para convertir los índices de fila / columna en un índice y trabajar en una matriz unidimensional, la manera de guardar caché.

La función debe agrupar coordenadas cercanas en índices cercanos. El orden Morton se puede usar si trabajas con potencia de dos tamaños. Para tamaños que no sean de energía, a menudo puede traer los 4 bits más bajos en el orden morton y usar aritmética de índice normal para los bits superiores. Todavía obtendrá una aceleración significativa, incluso si la coordenada para indexar la conversión parece ser una operación costosa.

http://en.wikipedia.org/wiki/Z-order_(curve) <- lo siento, no se puede vincular que SO no le gusta las URL con un guion. Tienes que cortar la pasta.

Una aceleración del factor 10 y más son realistas por cierto. Depende del algoritmo que tengas sobre tus matrices.

Answer 2

Anna,

Aquí hay una gran página que analiza la diferencia de rendimiento entre los lenguajes de programación científica tradicionales (fortran, C ++) y c #.

http://msdn.microsoft.com/en-us/magazine/cc163995.aspx

De acuerdo con el artículo C #, cuando se utilizan matrices rectangulares (2d) puede ser un muy buen intérprete. Aquí hay un gráfico que muestra la diferencia de rendimiento entre las matrices irregulares (una matriz de matrices) y las matrices rectangulares (multidimensionales).

texto alternativo http://i.msdn.microsoft.com/cc163995.fig08.gif

Sugiero que experimentes y utilices el Análisis de rendimiento en VS 2008 para comparar.

Si usar C # es "lo suficientemente rápido", entonces su aplicación será mucho más fácil de mantener.

¡Buena suerte!

Answer 3

Para obtener el mejor rendimiento de la matriz, asegúrese de estar utilizando una matriz de una sola dimensión con un índice más bajo de 0.

Para acceder a los elementos de la matriz lo más rápido posible, puede usar punteros inseguros como los siguientes:

int[] array = Enumerable.Range(0, 1000).ToArray();

int count = 0;
unsafe {
    fixed (int* pArray = array) {
        for (int i = 0; i < array.Length; i++) {
            count += *(pArray + i);
        }
    }
}

EDITAR ¡Drat! No noté que dijiste matriz 2D. Este truco no funcionará con una matriz multidimensional, por lo que no estoy seguro de cuánta ayuda será. Aunque podría convertir cualquier matriz en una matriz de dimensión única haciendo aritmética en el índice de matriz. Solo depende de si le preocupa el rendimiento alcanzado al indexar la matriz o al iterar sobre la matriz.

Answer 4

Si descarga F #, y hace referencia a una de las bibliotecas de tiempo de ejecución (creo que es FSharp.PowerPack), y usa Microsoft.FSharp.Maths.Matrix. Se optimiza en función de si está utilizando una matriz densa o dispersa.