Il modo più veloce per convertire T [,] in T [] []?

Question

Quindi it turns out tutti gli array non sono creati uguali. Gli array multidimensionali possono avere limiti inferiori diversi da zero. Vedere ad esempio la proprietà Range.Value di Excel PIA object[,] rectData = myRange.Value;

Ho bisogno di convertire questi dati in una matrice seghettata. La mia prima prova di sotto odora di complessità. Qualche suggerimento per ottimizzarlo? Ha bisogno di gestire il caso generale in cui i limiti inferiori potrebbero non essere zero.

ho questo ex metodo:

public static T[][] AsJagged<T>(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; 
    } 

usati in questo modo:

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(); 

    } 

Curioso se Buffer.BlockCopy() avrebbe funzionato o più veloce?

Modifica: AsJagged deve gestire i tipi di riferimento.

Modifica: trovato bug in AsJagged(). Aggiunto int l; e ha aggiunto col1 + width al ciclo interno.

Answer 1

La complessità è O (N * M) N - numero di righe, M - numero di colonne. Questo è il meglio che puoi ottenere quando copi i valori N * M ...

Buffer.BlockCopy potrebbe essere più veloce del ciclo interno, ma non sarei sorpreso se il compilatore sa come gestire questo codice in modo corretto e tu non guadagnerà più velocità. Dovresti testarlo per essere sicuro.

Potrebbe essere possibile ottenere prestazioni migliori non copiando i dati a tutti (a spese potenziali di ricerche leggermente più lente). Se si crea una classe 'array row', che contiene il rect e un numero di riga e fornisce un indicizzatore che accede alla colonna corretta, è possibile creare un array di tali righe e salvare completamente la copia.

La complessità della creazione di un tale array di "righe di array" è O (N).

EDIT: Una classe ArrayRow, solo perché mi bug ...

L'ArrayRow potrebbe essere simile a questa:

class ArrayRow<T> 
{ 
    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]; } } 
} 

Ora è creare un array di ArrayRows, non si copia qualsiasi cosa, e l'ottimizzatore ha buone possibilità di ottimizzare l'accesso a un'intera riga in sequenza.

Answer 2

Una vista caveat/ipotesi in attacco:

• È sembrano utilizzare solo int come tipo di dati (o almeno sembrano essere OK con l'utilizzo di Buffer.BlockCopy che implicherebbe è possibile la vita con i tipi primitivi in ​​generale).
• Per i dati di test che mostri, non penso che ci sarà molto diverso usando un approccio un po 'sano di mente.

Dopo aver detto, la seguente implementazione (che deve essere specializzato per un tipo primitivo specifico (qui int) perché utilizza fixed) è circa 10 volte più veloce del metodo mediante il ciclo interno:

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

Utilizzando il seguente "codice di prova":

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); 
    } 

Dove AsJagged (primo caso) è la vostra funzione originale, ottengo il seguente output :

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

Quindi non v'è davvero un modo più veloce per farlo, però a seconda delle dimensioni dei dati di test, il numero di volte che in realtà eseguire questa operazione, e la vostra disponibilità per consentire pericoloso e P/Invoke codice, probabilmente non ne avrai bisogno.

Detto questo, stavamo usando matrici grandi di double (diciamo 7000x10000 elementi) dove effettivamente faceva una grande differenza.

Aggiornamento: sull'utilizzo Buffer.BlockCopy

potrei trascurare alcuni Marshal o altro trucco, ma non credo che utilizza Buffer.BlockCopy è possibile qui. Ciò è dovuto al fatto che richiede sia la matrice di origine che quella di destinazione a, beh, essere uno Array.

Nel nostro esempio, la destinazione è un array (ad esempio int[] temp = ...) tuttavia la fonte non lo è. Mentre "sappiamo" che per le matrici bidimensionali di tipi primitivi il layout è tale, che ogni "riga" (cioè prima dimensione) è una matrice del tipo in memoria, non esiste un modo sicuro (come in unsafe) per ottenere quello array senza il sovraccarico di copiarlo prima. Quindi, fondamentalmente abbiamo bisogno di utilizzare una funzione che si occupa semplicemente di memoria e non si preoccupa del contenuto effettivo di esso - come MoveMemory. A proposito, l'implementazione interna di Buffer.BlockCopy fa qualcosa di simile.