在C#中,多维数组 double[,]
和数组的数组 double[][]
有什么区别?
如果有区别的话?
每种类型最适合的使用场景是什么?
在C#中,多维数组 double[,]
和数组的数组 double[][]
有什么区别?
如果有区别的话?
每种类型最适合的使用场景是什么?
数组的数组(不规则数组)比多维数组快,可以更有效地使用。多维数组具有更好的语法。
如果你编写一些简单的代码,使用不规则数组和多维数组,然后使用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也建议在分析项目时使用锯齿数组而非多维数组。
var jagged = new int[10][5]
中查找值 jagged[3][6]
的过程如下:
var mult = new int[10,30]
,该多维数组的Length
属性返回元素的总数,即10 * 30 = 300。不规则数组的Rank
属性始终为1,但是多维数组可以具有任何Rank。可以使用任何数组的GetLength
方法来获取每个维度的长度。在此示例中,该多维数组的mult.GetLength(1)
返回30。索引多维数组更快。例如,给定此示例中的多维数组,mult[1,7]
= 30 * 1 + 7 = 37,获取该索引37处的元素。这是更好的内存访问模式,因为只涉及一个内存位置,即数组的基地址。因此,多维数组分配连续的内存块,而不规则数组不一定是正方形,例如jagged [1] .Length
不必等于jagged [2] .Length
,这对于任何多维数组都是正确的。
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实现的差异,Windows环境下的性能表现有很大差异)。
在Windows上,不规则数组的时间统计要优于多维数组,与我的对多维数组查找方式的理解基本相同,参见“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();
}
}
简单来说,多维数组类似于DBMS中的表格。
数组的数组(不规则数组)允许您使每个元素保存另一个变长的相同类型的数组。
因此,如果您确定数据结构看起来像一个表格(固定行/列),则可以使用多维数组。不规则数组是固定元素,每个元素可以保存可变长度的数组。
例如,伪代码:
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
更新 .NET 6:
随着 .NET 6 的发布,我认为现在是重新审视这个话题的好时机。我重写了新的 .NET 测试代码,并要求每个部分至少运行一秒钟。基准测试是在 AMD Ryzen 5600x 上进行的。
结果?情况很复杂。单一数组对于小型和大型数组 (< ~25x25x25 & > ~200x200x200) 是最高效的,而交错数组则在两者之间最快。不幸的是,从我的测试来看,多维数组显然是最慢的选择。最快选项的性能不到其两倍。但是!这取决于你需要数组做什么,因为交错数组的初始化可能比单一维数组慢得多,在一个 50^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中,多维数组比锯齿形数组更快。我运行了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进行的某些优化有关。
前言: 这条评论旨在针对okutane提供的答案,讨论交错数组与多维数组之间性能差异的问题。
声称其中一种类型比另一种类型更慢,是因为方法调用而不正确。 其中一种类型比另一种类型更慢,是因为较复杂的边界检查算法。 您可以通过查看编译后的程序集,而不是查看IL代码来轻松验证这一点。 例如,在我的4.5安装中,使用存储在eax和edx中的索引通过ecx指向的二维数组中存储的元素(通过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
和jmp
,代码基本上就会简化为(x*y_max+y)*sizeof(ptr)+sizeof(array_header)
。这个计算速度非常快(一个乘法可以被移位替代,因为这正是我们选择字节大小为2的幂次方的原因),对于随机访问元素来说,它几乎与其他任何东西一样快。
另一个复杂性是,在遍历单维数组时,现代编译器通常会优化掉嵌套的边界检查以访问元素。结果是代码基本上只需在数组的连续内存上移动索引指针。而对多维数组进行朴素迭代通常涉及额外的嵌套逻辑,因此编译器不太可能优化操作。因此,尽管访问单个元素的边界检查开销相对于数组维度和大小而言是常数运行时间,但测试差异的简单案例可能需要更长的执行时间。
多维数组是(n-1)维矩阵。
因此,int[,] square = new int[2,2]
是一个2x2的方阵,int[,,] cube = new int [3,3,3]
是一个立方体 - 一个3x3的方阵。不需要成比例。
锯齿形数组只是一个数组的数组 - 每个单元格包含一个数组。
所以MDA是成比例的,JD可能不是!每个单元格可以包含任意长度的数组!
这个问题在之前的回答中可能已经提到,但没有明确说明:使用锯齿数组可以使用array[row]
来引用整行数据,但是对于多维数组不允许这样做。
我想从未来的角度介入一下,提供一些与.NET 5相关的性能结果,因为现在每个人都会使用这个平台。
这些测试与John Leidegren在2009年所用的测试相同。
我的结果(.NET 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机器上。
看起来性能比例仍然大致相同。我会说,除非你真的在努力优化,否则只需使用多维数组,因为语法稍微容易些。
<gcAllowVeryLargeObjects>
。这些数组的长度可以与其他行中的长度不同。
与常规的多维数组相比,声明锯齿状数组的唯一区别在于我们不只有一对方括号。 对于锯齿状数组,每个维度都有一对方括号。我们按照以下方式分配它们:
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存储在程序的执行堆栈中,并指向动态内存中的一个块,该块包含三个引用序列,分别指向另外三个内存块;每个内存块都包含一个整数数组——即锯齿数组的元素。
double[,]
是矩形数组,而double[][]
被称为“交错数组”。第一个数组的每一行都有相同数量的“列”,而第二个数组的每一行可能具有不同数量的“列”。 - GreatAndPowerfulOz