在c#中多维数组和数组的数组之间有什么区别?

c#中的多维数组double[,]和数组的数组double[][]之间有什么区别?

如果有区别，每一种的最佳用途是什么?

157532 次浏览
小开
最佳答案

数组的数组(锯齿数组)比多维数组更快，可以更有效地使用。多维数组有更好的语法。

如果你使用交错数组和多维数组写一些简单的代码，然后用IL反汇编器检查编译后的程序集，你会发现从交错数组(或一维数组)中存储和检索是简单的IL指令，而多维数组的相同操作是方法调用，总是比较慢。

考虑以下方法:

static void SetElementAt(int[][] array, int i, int j, int value)
{
array[i][j] = value;
}


static void SetElementAt(int[,] array, int i, int j, int value)
{
array[i, j] = value;
}

他们的IL将如下:

.method private hidebysig static void  SetElementAt(int32[][] 'array',
int32 i,
int32 j,
int32 'value') cil managed
{
// Code size       7 (0x7)
.maxstack  8
IL_0000:  ldarg.0
IL_0001:  ldarg.1
IL_0002:  ldelem.ref
IL_0003:  ldarg.2
IL_0004:  ldarg.3
IL_0005:  stelem.i4
IL_0006:  ret
} // end of method Program::SetElementAt


.method private hidebysig static void  SetElementAt(int32[0...,0...] 'array',
int32 i,
int32 j,
int32 'value') cil managed
{
// Code size       10 (0xa)
.maxstack  8
IL_0000:  ldarg.0
IL_0001:  ldarg.1
IL_0002:  ldarg.2
IL_0003:  ldarg.3
IL_0004:  call       instance void int32[0...,0...]::Set(int32,
int32,
int32)
IL_0009:  ret
} // end of method Program::SetElementAt

当使用锯齿状数组时，可以轻松地执行行交换和行大小调整等操作。也许在某些情况下使用多维数组会更安全，但即使Microsoft FxCop也告诉我们，当您使用锯齿数组来分析您的项目时，应该使用锯齿数组而不是多维数组。

小开
简单地说，多维数组类似于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
小开

多维数组创建了一个很好的线性内存布局，而锯齿数组意味着几个额外的间接层次。

在锯齿状数组var jagged = new int[10][5]中查找值jagged[3][6]的工作方式如下:查找该数组中下标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

第一行是锯齿数组的计时，第二行是多维数组第三行，应该是这样的。该程序如下所示，仅供参考，这是测试运行mono。(窗口时间有很大的不同，主要是由于CLR实现的变化)。

在窗口上，锯齿数组的计时非常优越，与我自己对多维数组查找应该是什么样子的解释大致相同，请参阅“Single()”。不幸的是，windows的jit编译器真的很愚蠢，这使得这些性能讨论很困难，有太多的不一致。

这些是我在windows上得到的时间，这里也是一样，第一行是锯齿数组，第二行是多维的，第三行是我自己的多维实现，注意这在windows上比mono慢多了。

  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();
}
}
小开

多维数组是(n-1)维矩阵。

所以int[,] square = new int[2,2]是一个2x2的方阵，int[,,] cube = new int [3,3,3]是一个3x3的立方方阵。比例不是必需的。

交错数组只是数组的数组——每个单元格包含一个数组的数组。

所以MDA是成比例的，JD可能不是!每个单元格可以包含任意长度的数组!

小开

前言:此注释旨在解决答案由奥库坦提供关于锯齿数组和多维数组之间性能差异的问题。

一种类型因为方法调用而比另一种类型慢的断言是不正确的。其中一种比另一种慢，因为它的边界检查算法更复杂。您可以通过查看编译后的程序集而不是IL轻松验证这一点。例如，在我的4.5安装中，访问存储在ecx指向的二维数组中的元素(通过edx中的指针)，索引存储在eax和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和__abc2，代码几乎会解析为(x*y_max+y)*sizeof(ptr)+sizeof(array_header)。这种计算的速度与随机访问元素的速度一样快(一个乘法可以被一个移位所取代，因为这就是我们选择字节大小为两位幂的全部原因)。

另一个复杂的问题是，在很多情况下，现代编译器在迭代一维数组时，会优化掉元素访问的嵌套边界检查。结果得到的代码基本上只是在数组的连续内存中向前移动一个索引指针。多维数组上的朴素迭代通常涉及一个额外的嵌套逻辑层，因此编译器不太可能优化操作。因此，即使访问单个元素的边界检查开销根据数组的尺寸和大小平摊到常量运行时，一个简单的测试用例来测量差异可能会花费很多倍的时间来执行。

小开

这可能在上面的回答中提到过，但没有明确地提到:对于锯齿数组，您可以使用array[row]来引用整行数据，但这对于多维数组是不允许的。

小开

我正在解析ildasm生成的.il文件，以构建用于进行转换的程序集、类、方法和存储过程的数据库。我遇到了下面的问题，打断了我的解析。

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

Serge Lidin于2006年出版的《Expert . net 2.0 IL汇编器》一书，第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且大小未定义的二维数组。

汤姆

小开

除了其他答案之外，请注意，多维数组被分配为堆上的一个大块对象。这有一些含义:

  1. 一些多维数组将被分配到大对象堆(LOH)上，而它们等效的锯齿状数组对应对象在其他情况下不会被分配到那里。
  2. GC将需要找到单个连续的空闲内存块来分配多维数组，而锯齿状数组可能能够填补由堆碎片引起的空白……这在。net中通常不是一个问题，因为压缩，但是LOH在默认情况下不会被压缩(你必须请求它，而且每次你想要它的时候都必须请求)。
  3. 如果你只使用锯齿数组，你会想要在问题出现之前查找<gcAllowVeryLargeObjects>中的多维数组道路。
小开

更新。net 6:

随着. net 6的发布，我决定是时候重新讨论这个话题了。我重写了new . net的测试代码，并按照每个部分至少运行一秒钟的要求运行它。基准测试是在AMD Ryzen 5600x上完成的。

结果吗?它是复杂的。对于小型和大型数组，单数组似乎是性能最好的(<~ 25 x25x25,>~200x200x200)和锯齿阵列之间的速度最快。不幸的是，从我的测试来看，多维度似乎是迄今为止最慢的选择。最好的表现是最快选择的两倍慢。但是!这取决于你需要数组做什么因为锯齿状数组在50^3立方上初始化需要更长的时间初始化时间大约是一维数组的3倍。多维只比一维慢一点点。

结论?如果您需要快速的代码，请自己在将要运行它的机器上进行基准测试。CPU架构可以完成各个方法的相对性能变化。

数字!

Method name         Ticks/Iteration     Scaled to the best
Array size 1x1x1 (10,000,000 iterations):
Jagged:             0.15                4.28
Single:             0.035               1
Multi-dimensional:  0.77                22


Array size 10x10x10 (25,000 iterations):
Jagged:             15                  1.67
Single:             9                   1
Multi-dimensional:  56                  6.2


Array size 25x25x25 (25,000 iterations):
Jagged:             157                 1.3
Single:             120                 1
Multi-dimensional:  667                 5.56


Array size 50x50x50 (10,000 iterations):
Jagged:             1,140               1
Single:             2,440               2.14
Multi-dimensional:  5,210               4.57


Array size 100x100x100 (10,000 iterations):
Jagged:             9,800               1
Single:             19,800              2
Multi-dimensional:  41,700              4.25


Array size 200x200x200 (1,000 iterations):
Jagged:             161,622             1
Single:             175,507             1.086
Multi-dimensional:  351,275             2.17


Array size 500x500x500 (100 iterations):
Jagged:             4,057.413           1.5
Single:             2,709,301           1
Multi-dimensional:  5,359,393           1.98

不相信我?自己运行并验证。

注意:常量大小似乎给锯齿状数组一个边缘，但并不足以改变我的基准测试中的顺序。我在一些实例中测量到，当使用用户输入的大小时，锯齿状数组的性能下降了7%，对于单个数组没有差异，对于多维数组的性能下降非常小(~1%或更少)。它在中间最为突出，锯齿状阵列占据主导地位。

    using System.Diagnostics;


const string Format = "{0,7:0.000} ";
const int TotalPasses = 25000;
const int Size = 50;
Stopwatch timer = new();


var functionList = new List<Action> { Jagged, Single, SingleStandard, Multi };


Console.WriteLine("{0,5}{1,20}{2,20}{3,20}{4,20}", "Run", "Ticks", "ms", "Ticks/Instance", "ms/Instance");


foreach (var item in functionList)
{
var warmup = Test(item);
var run = Test(item);


Console.WriteLine($"{item.Method.Name}:");
PrintResult("warmup", warmup);
PrintResult("run", run);
Console.WriteLine();
}


static void PrintResult(string name, long ticks)
{
Console.WriteLine("{0,10}{1,20}{2,20}{3,20}{4,20}", name, ticks, string.Format(Format, (decimal)ticks / TimeSpan.TicksPerMillisecond), (decimal)ticks / TotalPasses, (decimal)ticks / TotalPasses / TimeSpan.TicksPerMillisecond);
}


long Test(Action func)
{
timer.Restart();
func();
timer.Stop();
return timer.ElapsedTicks;
}


static void Jagged()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var jagged = new int[Size][][];
for (var i = 0; i < Size; i++)
{
jagged[i] = new int[Size][];
for (var j = 0; j < Size; j++)
{
jagged[i][j] = new int[Size];
for (var k = 0; k < Size; k++)
{
jagged[i][j][k] = i * j * k;
}
}
}
}
}


static void Multi()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var multi = new int[Size, Size, Size];
for (var i = 0; i < Size; i++)
{
for (var j = 0; j < Size; j++)
{
for (var k = 0; k < Size; k++)
{
multi[i, j, k] = i * j * k;
}
}
}
}
}


static void Single()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var single = new int[Size * Size * Size];
for (var i = 0; i < Size; i++)
{
int iOffset = i * Size * Size;
for (var j = 0; j < Size; j++)
{
var jOffset = iOffset + j * Size;
for (var k = 0; k < Size; k++)
{
single[jOffset + k] = i * j * k;
}
}
}
}
}


static void SingleStandard()
{
for (var passes = 0; passes < TotalPasses; passes++)
{
var single = new int[Size * Size * Size];
for (var i = 0; i < Size; i++)
{
for (var j = 0; j < Size; j++)
{
for (var k = 0; k < Size; k++)
{
single[i * Size * Size + j * Size + k] = i * j * k;
}
}
}
}
}

经验教训:总是在基准测试中包含CPU，因为它会有所不同。这次是吗?我不知道，但我怀疑是。

最初的回答:

我想对此进行更新，因为在.NET Core多维数组比锯齿数组更快中。我从约翰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上的一些优化有关

小开

我想从未来开始，我应该在这里补充一些。net 5的性能结果，因为从现在开始，它将成为每个人都使用的平台。

这些是约翰Leidegren使用的相同的测试(在2009年)。

我的结果。净5.0.1):

  Debug:
(Jagged)
5.616   4.719   4.778   5.524   4.559   4.508   5.913   6.107   5.839   5.270
  

(Multi)
6.336   7.477   6.124   5.817   6.516   7.098   5.272   6.091  25.034   6.023
  

(Single)
4.688   3.494   4.425   6.176   4.472   4.347   4.976   4.754   3.591   4.403




Release(code optimizations on):
(Jagged)
2.614   2.108   3.541   3.065   2.172   2.936   1.681   1.724   2.622   1.708


(Multi)
3.371   4.690   4.502   4.153   3.651   3.637   3.580   3.854   3.841   3.802


(Single)
1.934   2.102   2.246   2.061   1.941   1.900   2.172   2.103   1.911   1.911

运行在一个6核3.7GHz AMD Ryzen 1600机器上。

看起来性能比率仍然大致相同。我想说，除非你真的很难优化，否则就使用多维数组，因为语法更容易使用。

小开

使用基于约翰Leidegren的测试，我使用。net 4.7.2对结果进行了基准测试，这是与我的目的相关的版本，我认为我可以分享。我最初从dotnet核心GitHub存储库中的这样的评论开始。

随着数组大小的变化，性能似乎有很大变化，至少在我的设置中是这样，1个处理器xeon, 4physical 8logical。

w =初始化一个数组，并将int I * j放入其中。 Wr = do w，然后在另一个循环中设置int x为[i,j]

随着数组大小的增长，多维似乎表现得更好。

< span style=" font - family:宋体;"> < / th >大小 < span style=" font - family:宋体;"> rw < / th > < span style=" font - family:宋体;"> < / th方法> < span style=" font - family:宋体;">是< / th > < span style=" font - family:宋体;"> < / th >错误 < span style=" font - family:宋体;"> StdDev < / th > < span style=" font - family:宋体;">Gen 0/1k Op < span style=" font - family:宋体;">Gen 1/1k Op < span style=" font - family:宋体;">Gen 2/1k Op < span style=" font - family:宋体;">分配的内存/ Op < / th > < span style=" font - family:宋体;"> 1800 * 500道明> < / < span style=" font - family:宋体;"道明> > w < / < span style=" font - family:宋体;">参差不齐的道明> < / > /td> . . . . . . < span style=" font - family:宋体;"> 2000 * 4000道明> < / < span style=" font - family:宋体;"道明> > w < / < span style=" font - family:宋体;">参差不齐的道明> < / . . . . . . . . < span style=" font - family:宋体;"> 1000 * 2000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">参差不齐的道明> < / . . . . . . . .
0.0959 ms0.1405 ms578.1250 . 1800 * 500道明> < / < span style=" font - family:宋体;"道明> > w < / < span style=" font - family:宋体;">多道明> < / 3.079 ms0.2419 ms0.3621 ms3.43 MB
50.29 ms 4.882 ms 5937.50003375.0000 937.5000 2000 * 4000道明> < / < span style=" font - family:宋体;"道明> > w < / < span style=" font - family:宋体;">多道明> < / 2.690 ms 218.7500 218.7500 218.7500 2000 * 4000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">参差不齐的道明> < / 55.30 ms 3.066 ms4.589 ms5937.50003375.0000 937.5000 2000 * 4000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">多道明> < / 4.87 ms
11.18 ms0.5397 ms0.8078 ms1437.5000 578.1250 234.3750 1000 * 2000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">多道明> < / 6.62 ms 0.3238 ms210.9375210.9375210.9375 < span style=" font - family:宋体;"> < / th >大小 < span style=" font - family:宋体;"> rw < / th > < span style=" font - family:宋体;"> < / th方法> < span style=" font - family:宋体;">是< / th > < span style=" font - family:宋体;"> < / th >错误 < span style=" font - family:宋体;"> StdDev < / th > < span style=" font - family:宋体;">Gen 0/1k Op < span style=" font - family:宋体;">Gen 1/1k Op < span style=" font - family:宋体;">Gen 2/1k Op < span style=" font - family:宋体;">分配的内存/ Op < / th > < span style=" font - family:宋体;"> 1000 * 2000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">参差不齐的道明> < / . . < span style=" font - family:宋体;"> 1000 * 2000道明> < / < span style=" font - family:宋体;"> wr td > < / < span style=" font - family:宋体;">多道明> < / . . . .
3062.5000 1531.2500531.250015.31 MB
12.61 ms 1.018 ms156.2500156.2500156.2500
小开

交错数组是数组的数组，或者每一行包含一个自己的数组的数组。

这些数组的长度可以不同于其他行的长度。

声明和分配数组的数组

与常规多维数组相比，锯齿数组声明的唯一不同之处在于，我们不只有一对括号。对于锯齿状数组，每个维度都有一对括号。我们这样分配它们:

int[][] exampleJaggedArray;
jaggedArray = new int[2][];
jaggedArray[0] = new int[5];
jaggedArray[1] = new int[3];

初始化数组的数组

int[][] exampleJaggedArray = {
new int[] {5, 7, 2},
new int[] {10, 20, 40},
new int[] {3, 25}
};

内存分配

锯齿数组是引用的聚合。锯齿状数组不直接包含任何数组，而是有指向它们的元素。大小是未知的，这就是为什么CLR只保留对内部数组的引用。在我们为锯齿状数组的一个数组元素分配内存之后，引用开始指向动态内存中新创建的块。

变量exampleJaggedArray存储在程序的执行堆栈中，并指向动态内存中的一个块，该块包含对内存中其他三个块的三个引用序列;它们每个都包含一个整数数组——锯齿数组的元素:


提交答案