陣列初始化 - C#中多維數組和數組之間有什麼區別?




c#陣列初始化 (6)

在C#中double[,]多維數組double[,]和array-of-arrays double[][]什麼區別?

如果有差異,每個人最好用什麼?


前言:此評論旨在解決share ,但由於SO的愚蠢聲譽系統,我無法將其發佈在其所屬的位置。

由於方法調用,你斷言一個比另一個慢,這是不正確的。 由於更複雜的邊界檢查算法,其中一個比另一個慢。 您可以通過查看,而不是在IL上,而是在編譯後的程序集中輕鬆驗證。 例如,在我的4.5安裝中,訪問ecx指向的二維數組中存儲eax和edx索引的元素(通過edx中的指針),看起來像這樣:

sub eax,[ecx+10]
cmp eax,[ecx+08]
jae oops //jump to throw out of bounds exception
sub edx,[ecx+14]
cmp edx,[ecx+0C]
jae oops //jump to throw out of bounds exception
imul eax,[ecx+0C]
add eax,edx
lea edx,[ecx+eax*4+18]

在這裡,你可以看到方法調用沒有任何開銷。 邊界檢查非常複雜,這要歸功於非零索引的可能性,這是一種不具備鋸齒狀數組的功能。 如果我們刪除非零情況下的sub,cmp和jmps,代碼幾乎可以解析為(x*y_max+y)*sizeof(ptr)+sizeof(array_header) 。 這個計算速度一樣快(一個乘法可以被一個移位所替代,因為這是我們選擇字節大小為兩個位的大小的全部原因)與隨機訪問元素的其他任何東西一樣。

另一個複雜的情況是,有很多情況下現代編譯器會優化掉嵌套邊界 - 在遍歷單維數組時檢查元素訪問。 結果是代碼基本上只是在數組的連續內存上推進索引指針。 對多維數組的初始迭代通常涉及額外的嵌套邏輯層,因此編譯器不太可能優化操作。 因此,即使訪問單個元素的邊界檢查開銷根據數組維數和大小分配到常量運行時間,但是測量差異的簡單測試用例可能需要多次執行。


一個多維數組創建一個很好的線性內存佈局,而一個鋸齒形數組意味著幾個額外的間接級別。

在鋸齒狀數組中查找jagged[3][6]jagged[3][6] var jagged = new int[10][5]像這樣工作:查找索引3處的元素(這是一個數組)並在索引處查找元素6在該數組中(這是一個值)。 對於這種情況下的每個維度,都有一個額外的查找(這是一個昂貴的內存訪問模式)。

多維數組在存儲器中線性排列,實際值是通過將索引相乘而得到的。 但是,給定數組var mult = new int[10,30] ,該多維數組的Length屬性返回元素的總數,即10 * 30 = 300。

鋸齒狀數組的Rank屬性始終為1,但多維數組可以有任何級別。 任何數組的GetLength方法都可以用來獲取每個維度的長度。 對於此示例中的多維數組, mult.GetLength(1)返回30。

索引多維數組速度更快。 例如,在這個例子中給出多維數組mult[1,7] = 30 * 1 + 7 = 37,得到該索引為37的元素。這是一個更好的內存訪問模式,因為只涉及一個內存位置,數組的地址。

因此多維數組分配一個連續的內存塊,而鋸齒狀數組不必是方形的,例如jagged[1].Length不必等於jagged[2].Length ,對於任何多維數組來說都是如此。

性能

性能方面,多維數組應該更快。 速度要快得多,但由於CLR的實施很糟糕,它們不是。

 23.084  16.634  15.215  15.489  14.407  13.691  14.695  14.398  14.551  14.252 
 25.782  27.484  25.711  20.844  19.607  20.349  25.861  26.214  19.677  20.171 
  5.050   5.085   6.412   5.225   5.100   5.751   6.650   5.222   6.770   5.305 

第一行是參差不齊的數組,第二行顯示多維數組,第三行,以及它應該如何。 該程序如下所示,僅供參考,這是測試運行單聲道。 (窗口時間差別很大,主要是由於CLR實施變化)。

在窗口上,鋸齒狀數組的時序非常優越,與我自己對多維數組查找應該是什麼樣子的解釋大致相同,請參見'Single()'。 令人遺憾的是,Windows JIT編譯器確實很愚蠢,不幸的是這使得這些性能討論變得困難,因此存在太多的不一致。

這些是我在windows上得到的時間,在這裡同樣的交易,第一行是參差不齊的數組,第二個多維和第三個我自己的多維實現,請注意,與單聲道相比,這是多少速度。

  8.438   2.004   8.439   4.362   4.936   4.533   4.751   4.776   4.635   5.864
  7.414  13.196  11.940  11.832  11.675  11.811  11.812  12.964  11.885  11.751
 11.355  10.788  10.527  10.541  10.745  10.723  10.651  10.930  10.639  10.595

源代碼:

using System;
using System.Diagnostics;
static class ArrayPref
{
    const string Format = "{0,7:0.000} ";
    static void Main()
    {
        Jagged();
        Multi();
        Single();
    }

    static void Jagged()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var jagged = new int[dim][][];
            for(var i = 0; i < dim; i++)
            {
                jagged[i] = new int[dim][];
                for(var j = 0; j < dim; j++)
                {
                    jagged[i][j] = new int[dim];
                    for(var k = 0; k < dim; k++)
                    {
                        jagged[i][j][k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Multi()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var multi = new int[dim,dim,dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        multi[i,j,k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Single()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var single = new int[dim*dim*dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        single[i*dim*dim+j*dim+k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }
}

我想對此進行更新,因為在.NET中,核心多維數組比鋸齒形數組快 。 我運行了來自John Leidegren的測試,這些是.NET Core 2.0預覽版2的結果。我增加了維度值,以使背景應用程序的任何可能影響都看不見。

Debug (code optimalization disabled)
Running jagged 
187.232 200.585 219.927 227.765 225.334 222.745 224.036 222.396 219.912 222.737 

Running multi-dimensional  
130.732 151.398 131.763 129.740 129.572 159.948 145.464 131.930 133.117 129.342 

Running single-dimensional  
 91.153 145.657 111.974  96.436 100.015  97.640  94.581 139.658 108.326  92.931 


Release (code optimalization enabled)
Running jagged 
108.503 95.409 128.187 121.877 119.295 118.201 102.321 116.393 125.499 116.459 

Running multi-dimensional 
 62.292  60.627  60.611  60.883  61.167  60.923  62.083  60.932  61.444  62.974 

Running single-dimensional 
 34.974  33.901  34.088  34.659  34.064  34.735  34.919  34.694  35.006  34.796 

我看著反彙編,這是我發現的

jagged[i][j][k] = i * j * k; 需要執行34條指令

multi[i, j, k] = i * j * k; 需要執行11條指令

single[i * dim * dim + j * dim + k] = i * j * k; 需要執行23條指令

我無法確定為什麼一維數組仍然比多維數據更快,但我的猜測是它必須與CPU上的一些最優化有關


我正在解析由ildasm生成的.il文件,以構建用於執行轉換的安裝程序,類,方法和存儲過程的數據庫。 我遇到以下,這打破了我的解析。

.method private hidebysig instance uint32[0...,0...] 
        GenerateWorkingKey(uint8[] key,
                           bool forEncryption) cil managed

Serge Lidin,Apress出版的Expert .NET 2.0 IL Assembler一書,2006年出版,第8章,原始類型和簽名,第149-150頁。

<type>[]被稱為<type>的Vector,

<type>[<bounds> [<bounds>**] ]被稱為<type>的數組

**表示可以重複, [ ]表示可選。

例子:讓<type> = int32

1) int32[...,...]是一個未定義的下限和大小的二維數組

2) int32[2...5]是下界2和大小4的一維數組。

3) int32[0...,0...]是下界0和未定義大小的二維數組。

湯姆


簡單地說,多維數組與DBMS中的表類似。
數組數組(鋸齒形數組)讓您可以讓每個元素保存另一個具有相同類型變量長度的數組。

因此,如果您確定數據結構看起來像一個表(固定行/列),則可以使用多維數組。 鋸齒形數組是固定元素,每個元素可以包含一個可變長度的數組

例如Psuedocode:

int[,] data = new int[2,2];
data[0,0] = 1;
data[0,1] = 2;
data[1,0] = 3;
data[1,1] = 4;

將上述想像為2x2表格:

1 | 2
3 | 4
int[][] jagged = new int[3][]; 
jagged[0] = new int[4] {  1,  2,  3,  4 }; 
jagged[1] = new int[2] { 11, 12 }; 
jagged[2] = new int[3] { 21, 22, 23 }; 

將上述想像為具有可變列數的每行:

 1 |  2 |  3 | 4
11 | 12
21 | 22 | 23

這可能是在上面的答案中提到的,但不是明確的:對於鋸齒形數組,您可以使用array[row]來引用整行數據,但這不適用於multi-d數組。





jagged-arrays