Moyen le plus rapide de convertir T[,] en T[][]?

Question

Alors il s'avère que tous les tableaux ne sont pas créés égaux. Les tableaux multidimensionnels peuvent avoir des bornes inférieures non nulles. Voyez par exemple la propriété Range.Value de l'Excel PIA object[,] rectData = myRange.Value;

J'ai besoin de convertir ces données en un tableau échelonné. Mon premier essai ci-dessous sent la complexité. Des suggestions pour l'optimiser ? Il doit gérer le cas général où les bornes inférieures peuvent ne pas être zéro.

J'ai cette méthode ex :

    public static T[][] AsJagged( this T[,] rect )
    {
        int row1 = rect.GetLowerBound(0);
        int rowN = rect.GetUpperBound(0);
        int col1 = rect.GetLowerBound(1);
        int colN = rect.GetUpperBound(1);

        int height = rowN - row1 + 1;
        int width = colN - col1 + 1;
        T[][] jagged = new T[height][];

        int k = 0;
        int l;
        for ( int i = row1; i < row1 + height; i++ )
        {
            l = 0;
            T[] temp = new T[width];
            for ( int j = col1; j < col1 + width; j++ )
                temp[l++] = rect[i, j];
            jagged[k++] = temp;
        }

        return jagged;
    }

Utilisé ainsi :

    public void Foo()
    {
        int[,] iRect1 = { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } };
        int[][] iJagged1 = iRect1.AsJagged();

        int[] lengths = { 3, 5 };
        int[] lowerBounds = { 7, 8 };
        int[,] iRect2 = (int[,])Array.CreateInstance(typeof(int), lengths, lowerBounds);
        int[][] iJagged2 = iRect2.AsJagged();

    }

Curieux de savoir si Buffer.BlockCopy() fonctionnerait ou serait plus rapide ?

Édition : AsJagged doit gérer les types de référence.

Édition : Bug trouvé dans AsJagged(). Ajouté int l; et ajouté col1 + width à la boucle interne.

Answer 1

Quelques précautions / hypothèses à l'avance :

• Il semble que vous n'utilisiez que int comme type de données (ou du moins semblez être OK avec l'utilisation de Buffer.BlockCopy ce qui impliquerait que vous pouvez utiliser des types primitifs en général).
• Pour les données de test que vous montrez, je ne pense pas qu'il y aura beaucoup de différences en utilisant une approche raisonnable.

Cela dit, l'implémentation suivante (qui doit être spécialisée pour un type primitif spécifique (ici int) car elle utilise fixed) est environ 10 fois plus rapide que l'approche utilisant la boucle interne :

    unsafe public static int[][] AsJagged2(int[,] rect)
    {
        int row1 = rect.GetLowerBound(0);
        int rowN = rect.GetUpperBound(0);
        int col1 = rect.GetLowerBound(1);
        int colN = rect.GetUpperBound(1);

        int height = rowN - row1 + 1;
        int width = colN - col1 + 1;
        int[][] jagged = new int[height][];

        int k = 0;
        for (int i = row1; i < row1 + height; i++)
        {
            int[] temp = new int[width];

            fixed (int *dest = temp, src = &rect[i, col1])
            {
                MoveMemory(dest, src, rowN * sizeof(int));
            }

            jagged[k++] = temp;
        }

        return jagged;
    }

    [DllImport("kernel32.dll", EntryPoint = "RtlMoveMemory")]
    unsafe internal static extern void MoveMemory(void* dest, void* src, int length);

En utilisant le "code de test" suivant :

    static void Main(string[] args)
    {
        Random rand = new Random();
        int[,] data = new int[100,1000];
        for (int i = 0; i < data.GetLength(0); i++)
        {
            for (int j = 0; j < data.GetLength(1); j++)
            {
                data[i, j] = rand.Next(0, 1000);
            }
        }

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged = AsJagged(data);
        }

        Console.WriteLine("AsJagged:  " + sw.Elapsed);

        sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged2 = AsJagged2(data);
        }

        Console.WriteLine("AsJagged2: " + sw.Elapsed);
    }

Où AsJagged (le premier cas) est votre fonction initiale, j'obtiens la sortie suivante :

AsJagged:  00:00:00.9504376
AsJagged2: 00:00:00.0860492

Il existe en effet un moyen plus rapide de le faire, mais en fonction de la taille des données de test, du nombre de fois où vous effectuez réellement cette opération et de votre volonté d'autoriser du code non sécurisé et des appels P/Invoke, vous n'en aurez probablement pas besoin.

Cela dit, nous utilisions de grandes matrices de double (disons 7000x10000 éléments) où cela a effectivement fait une énorme différence.

Mise à jour : à propos de l'utilisation de Buffer.BlockCopy

J'ai pu négliger une astuce de Marshal ou autre, mais je ne pense pas qu'il soit possible d'utiliser Buffer.BlockCopy ici. Cela est dû au fait qu'il exige que à la fois le tableau source et de destination soient, eh bien, un Array.

Dans notre exemple, la destination est un tableau (par exemple int[] temp = ...) cependant la source ne l'est pas. Bien que nous "savons" que pour les tableaux bidimensionnels de types primitifs, la disposition est telle que chaque "ligne" (c'est-à-dire la première dimension) est un tableau du type en mémoire, il n'y a pas de moyen sûr (comme avec unsafe) d'obtenir ce tableau sans la surcharge de d'abord le copier. Nous avons donc essentiellement besoin d'utiliser une fonction qui gère simplement la mémoire et ne se soucie pas du contenu réel de celle-ci - comme MoveMemory. Au fait, l'implémentation interne de Buffer.BlockCopy fait quelque chose de similaire.

Answer 2

Votre complexité est O(N*M) N - nombre de lignes, M - nombre de colonnes. C'est le mieux que vous puissiez obtenir en copiant N*M valeurs...

Buffer.BlockCopy pourrait être plus rapide que votre boucle interne, mais je ne serais pas surpris si le compilateur sait comment gérer ce code correctement et que vous ne gagnerez pas de vitesse supplémentaire. Vous devriez le tester pour vous en assurer.

Vous pouvez peut-être obtenir de meilleures performances en ne copiant pas du tout les données (au prix éventuel de recherches légèrement plus lentes). Si vous créez une classe 'array row', qui contient votre rectangle et un numéro de ligne, et fournit un indexeur qui accède à la bonne colonne, vous pouvez créer un tableau de ces lignes et vous épargner la copie entièrement.

La complexité de la création d'un tel tableau de 'array rows' est O(N).

MODIFICATION: Une classe ArrayRow, juste parce que ça me tracasse...

La classe ArrayRow pourrait ressembler à ceci :

class ArrayRow
{
    private T[,] _source;
    private int _row;

    public ArrayRow(T[,] rect, int row)
    {
         _source = rect;
         _row = row;
    }

    public T this[int col] { get { return _source[_row, col]; } }
}

Maintenant vous créez un tableau de ArrayRows, vous ne copiez rien du tout, et l'optimiseur a de bonnes chances d'optimiser l'accès à une ligne entière en séquence.