Cách nhanh nhất để chuyển đổi T [,] thành T [] []?

Question

Vì vậy, it turns out tất cả các mảng không được tạo bằng nhau. Mảng đa chiều có thể có giới hạn dưới khác không. Xem ví dụ về thuộc tính Range.Value của Excel PIA object[,] rectData = myRange.Value;

Tôi cần phải chuyển đổi những dữ liệu này thành một mảng răng cưa. Lần thử đầu tiên của tôi bên dưới mùi phức tạp. Bất kỳ đề xuất nào để tối ưu hóa nó? Nó cần phải xử lý các trường hợp chung mà giới hạn dưới có thể không bằng không.

tôi có phương pháp này ví dụ:

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

Được sử dụng như thế này:

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

    } 

Tò mò nếu Buffer.BlockCopy() sẽ làm việc hoặc được nhanh hơn?

Chỉnh sửa: AsJagged cần xử lý các loại tham chiếu.

Chỉnh sửa: Đã tìm thấy lỗi trong AsJagged(). Đã thêm int l; và thêm col1 + width vào vòng lặp bên trong.

Answer 1

Độ phức tạp của bạn là O (N * M) N - số hàng, M - số cột. Đó là điều tốt nhất bạn có thể nhận được khi sao chép các giá trị N * M ...

Buffer.BlockCopy có thể nhanh hơn vòng lặp bên trong của bạn, nhưng tôi sẽ không ngạc nhiên nếu trình biên dịch biết cách xử lý mã này đúng cách sẽ không đạt được tốc độ nào nữa. Bạn nên kiểm tra nó để chắc chắn.

Bạn có thể đạt được hiệu suất tốt hơn bằng cách không sao chép dữ liệu ở tất cả (với chi phí tiềm năng của việc tra cứu hơi chậm hơn). Nếu bạn tạo một lớp 'mảng hàng', giữ số trực tiếp và số hàng của bạn, và cung cấp một trình chỉ mục truy cập cột đúng, bạn có thể tạo một mảng các hàng như vậy và lưu bản sao hoàn toàn.

Sự phức tạp của việc tạo ra một mảng 'hàng mảng' như vậy là O (N).

EDIT: Một lớp ArrayRow, chỉ vì nó làm tôi phát cáu ...

Các ArrayRow có thể trông giống như thế này:

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

Bây giờ bạn tạo một mảng của ArrayRows, bạn không sao chép bất cứ điều gì cả, và trình tối ưu hóa có một cơ hội tốt để tối ưu hóa việc truy cập toàn bộ một hàng theo thứ tự.

Answer 2

Một cái nhìn cẩn thận/giả định lên phía trước:

• Bạn dường như chỉ int sử dụng như là kiểu dữ liệu của bạn (hoặc ít nhất có vẻ là OK với việc sử dụng Buffer.BlockCopy mà sẽ bao hàm bạn có thể sống với các loại nguyên thủy nói chung).
• Đối với dữ liệu thử nghiệm bạn hiển thị, tôi không nghĩ rằng sẽ có nhiều khác biệt khi sử dụng bất kỳ cách tiếp cận hơi lành mạnh nào.

Có những gì đã nói, việc thực hiện sau (mà cần phải được chuyên cho một loại nguyên thủy cụ thể (ở đây int) vì nó sử dụng fixed) là khoảng nhanh hơn so với phương pháp sử dụng vòng lặp bên trong 10 lần:

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

Sử dụng sau "mã kiểm tra":

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

đâu AsJagged (trường hợp đầu tiên) là chức năng ban đầu của bạn, tôi nhận được kết quả như sau :

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

Vì vậy, có thực sự là một cách nhanh hơn để làm việc đó, tuy nhiên tùy thuộc vào kích thước của dữ liệu kiểm tra, số lần bạn thực hiện thao tác này, và sẵn sàng để cho phép không an toàn và P/Invoke mã, có thể bạn sẽ không cần đến nó.

Có nói rằng, chúng tôi đã sử dụng các ma trận lớn double (nói các yếu tố 7000x10000) nơi thực sự đã tạo ra sự khác biệt lớn.

Cập nhật: về việc sử dụng Buffer.BlockCopy

tôi có thể bỏ qua một số Marshal hoặc khác lừa, nhưng tôi không nghĩ rằng sử dụng Buffer.BlockCopy có thể ở đây. Điều này là do thực tế là nó đòi hỏi cả mảng nguồn và đích đến, tốt, là một Array.

Trong ví dụ của chúng tôi, đích là một mảng (ví dụ: int[] temp = ...) tuy nhiên nguồn không phải là. Trong khi chúng ta "biết" rằng đối với mảng hai chiều của các kiểu nguyên thủy thì bố trí là như vậy, rằng mỗi "hàng" (tức là thứ nguyên đầu tiên) là một mảng của loại trong bộ nhớ, không có cách nào an toàn (như trong unsafe) mảng mà không cần phải sao chép nó trước. Vì vậy, về cơ bản chúng tôi cần sử dụng một hàm chỉ đơn giản là giao dịch với bộ nhớ và không quan tâm đến nội dung thực tế của nó - như MoveMemory. BTW, việc thực hiện nội bộ của Buffer.BlockCopy thực hiện điều gì đó tương tự.