Najszybszy sposób konwertowania T [,] na T [] []?

Question

Tak więc wszystkie tablice nie są sobie równe. Wielowymiarowe tablice mogą mieć niezerowe niższe granice. Patrz na przykład Excel PIA's Range.Value Właściwość object[,] rectData = myRange.Value;

Muszę przekonwertować te dane na poszarpaną tablicę. Moja pierwsza próba poniżej pachnie złożonością. Wszelkie sugestie optymalizacji? Musi obsłużyć ogólny przypadek, w którym dolna granica nie może wynosić zero.

mam tej metody Ex:

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

używany tak:

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

    } 

Ciekawy jeśli Buffer.BlockCopy() będzie działać lub być szybciej?

Edycja: AsJagged musi obsługiwać typy odniesienia.

Edytuj: Znaleziono błąd w AsJagged(). Dodano int l; i dodał col1 + width do wewnętrznej pętli.

Answer 1

Twoja złożoność to O (N * M) N - liczba wierszy, M - liczba kolumn. To najlepsze, co można uzyskać podczas kopiowania wartości N * M ...

Bufor.BlockCopy może być szybszy niż wewnętrzna pętla for, ale nie zdziwiłbym się, gdyby kompilator wiedział, jak poprawnie obsłużyć ten kod, a ty nie uzyska żadnej dodatkowej prędkości. Powinieneś przetestować go, aby się upewnić.

Być może uda się uzyskać lepszą wydajność , nie kopiując danych w ogóle (z potencjalnym wydatkiem nieznacznie wolniejszych wyszukiwań). Jeśli utworzysz klasę wiersza tablicy, która będzie zawierała twój numer prostokąta i numer wiersza, i udostępni indeksator, który uzyskuje dostęp do właściwej kolumny, możesz utworzyć tablicę takich wierszy i całkowicie zapisać kopię.

Złożoność tworzenia takiej tablicy "rzędów tablicy" to O (N).

EDIT: Klasa ArrayRow, tylko dlatego, że bugs mnie ...

ArrayRow mógłby wyglądać tak:

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

Teraz utworzyć tablicę ArrayRows, nie kopiować cokolwiek w ogóle, a optymalizator ma duże szanse na optymalizację dostępu do całego rzędu w sekwencji.

Answer 2

Widok PRZESTROGI/Założenia do góry przód:

• Wydaje się używać tylko int jako typ danych (lub przynajmniej wydaje się być OK, z użyciem Buffer.BlockCopy co sugerujesz może życie prymitywnych typów w ogóle).
• W przypadku danych testowych, które pokazujesz, nie sądzę, że będzie wiele różnic przy użyciu jakiegoś rozsądnego podejścia.

uwzględniając powiedział, co następuje realizacja (który musi być specjalnie przystosowane do konkretnego prymitywnego typu (tutaj int), ponieważ używa fixed) jest około 10 razy szybciej niż podejście z wykorzystaniem pętli wewnętrznej:

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

Korzystanie następujący kod „test”:

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

Gdzie AsJagged (pierwszy przypadek) ma swoją pierwotną funkcję, pojawia się następujący komunikat :

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

Więc rzeczywiście istnieje szybszy sposób to zrobić, jednak w zależności od wielkości danych testowych, ile razy rzeczywiście wykonać tę operację, a swoją gotowość do umożliwienia niebezpieczny i P/Invoke kod, prawdopodobnie nie będziesz go potrzebować.

Mając to powiedziane, korzystaliśmy z dużych matryc z double (powiedzmy elementy 7000x10000), w których rzeczywiście zrobiła ogromną różnicę.

Aktualizacja: o używaniu Buffer.BlockCopy

mogę przeoczyć jakiś Marshal lub innej sztuczki, ale nie sądzę, jest możliwe przy użyciu Buffer.BlockCopy tutaj. Wynika to z faktu, że wymaga ona zarówno macierzy źródłowej, jak i docelowej, aby, no cóż, być Array.

W naszym przykładzie miejscem docelowym jest tablica (np. int[] temp = ...), jednak źródłem nie jest. Chociaż "wiemy", że dla dwuwymiarowych tablic typów pierwotnych układ jest taki, że każdy "wiersz" (tj. Pierwszy wymiar) jest tablicą typu w pamięci, nie ma bezpiecznego (jak w unsafe) sposobu na uzyskanie tego tablica bez konieczności wcześniejszego kopiowania. Musimy więc użyć funkcji, która po prostu zajmuje się pamięcią i nie dba o rzeczywistą jej zawartość - np. MoveMemory. BTW, wewnętrzna implementacja Buffer.BlockCopy robi coś podobnego.