Effective C#: 2.以嵌套数组取代 多维数组
陈铭 Microsoft C#/.NET Asia MVP
难度：8/10 条款1
有些算法需要用到比一维数组更为复杂的数组结构，在C#中实现这样的算法有两种不同的选择：嵌套数组（Array of Array）或者多维数组（Multi-Dimensional Array）。顾名思义，嵌套数组是指那些以数组作为单个数据成员的数组。嵌套数组并不要求每个子数组具有相同的元素个数，因此其结构呈参差不齐的锯齿状，故而也称为齿状数组(Jagged Array)。与此对应，多维数组使用多个索引值来访问一块连续的内存中的元素，由于必须在定义阶段指明每一维索引的上下限，多维数组在布局上呈典型的多维矩阵构造。
从图中可以看出，嵌套数组中的元素无法被直接访问，而必须先根据元素每一维索引值找到相应的子数组，然后再在子数组中进行进一步的索引。例如，对于a[2][2]的访问必须先找到子数组a[2]，然后再在a[2]中访问下标为2的元素。而在多维数组当中，由于用于存储元素的内存空间是连续的，而且数组的每一维元素个数固定，所以可以轻易的根据元素各维的索引值计算出元素在数组内存中偏移量，这样我们就可以直接访问多维数组中的某个元素了。例如，在一个b[6,7]的数组中，b[2,2]元素的偏移量为2*7+2=16，那么b[2,2]实际上是在数组b的数据内存中的第16个元素。至此，直觉告诉我们使用多维数组应该能够获得比嵌套数组更好的性能，因为简单的数学计算要比间接内存访问高效的多。似乎已经可以把”使用多维数组而不是嵌套数组“写入我们的经验手册了。
但是，仅凭直觉得来的结论终究显得有点弱不禁风，在为这一结论竖碑立说之前，我们需要更多的判断依据。也许C#编译器生成的中介代码(MSIL)会有所帮助——况且.NET的“汇编”代码看上去也并不那么神秘。
下面的测试代码中，分别定义了嵌套数组和二维数组的实例，并对其中的一个元素进行累加操作:
//Jaggged array operation
int[][] ja = new int[3][];
…
ja[1][2] ++;
//Multi-Dimensional array operation
int[,] ma = new int[3,3];
…
ma[1,2] ++;
累加语句编译产生的MSIL指令如下所示：
//ja[1][2] ++;
IL_0000: ldloc.0 //ja
IL_0001: ldc.i4.1
IL_0002: ldelem.ref
IL_0003: dup
IL_0004: stloc.2
IL_0005: ldc.i4.2
IL_0006: ldloc.2
IL_0007: ldc.i4.2
IL_0008: ldelem.i4
IL_0009: ldc.i4.1
IL_000a: add
IL_000b: stelem.i4
//ma[1,2] ++;
IL_0000: ldloc.1 //ma
IL_0001: dup
IL_0002: ldc.i4.1
IL_0003: ldc.i4.2
IL_0004: ldc.i4.1
IL_0005: ldc.i4.2
IL_0006: call instance int32
int32[0...,0...]::Get(int32,
int32)
IL_000b: ldc.i4.1
IL_000c: add
IL_000d: call instance void
int32[0...,0...]::Set(int32,
int32,
也许你对MSIL并不那么熟悉，但即便如此也应该注意到两者实现上的一些显著的差别：嵌套数组的元素访问代码仅包含了一些简单的指令，而对于二维数组的元素访问居然包含了两个函数调用！看得更仔细些，会有更奇怪的发现：Get/Set应该是int32[0…,0…]类的成员函数，但int32[0…,0…]是什么类型？所有的数组都是从System.Array继承来的，但System.Array并不包含Get/Set函数的定义，而且在.NET Framework文档里，也找不到关于Get/Set这两个函数的任何相关信息！
我已经看见了你头顶上冉冉升起的巨大的问号，现在应该是介绍.NET对于各种数组类型的支持的时候了。
.NET运行系统(CLR)把数组分成两类：一种是以零为起始下标的一维数组，通常称为Vector或者SZArray；另外一种是数组起始下标非零的一维数组和所有的多维数组，通称为MDArray。由于C#不直接支持起始下标非零的数组，而且这种数组在实际应用中也很少见，所以在本章的讨论中将不会涉及这种特殊的数组类型。
Vector是最常用到的数组类型，所以CLR对Vector提供直接的MSIL指令支持以取得较好的性能。下表列出了CLR与数组操作有关的MSIL指令:
newarr
创建一个新的Vector型数组
ldelem
读取Vector中的一个元素
ldelema
读取Vector中一个元素的地址
ldlen
读取Vector中的元素个数
stelem
为数组中的一个元素赋值
其中，ldelem和stelem存在针对不同类型的数组的调用形式，比如ldelem.i4用于Int32类型的数组，而ldelem.ref则用于操作所有包含引用类型对象的数组。
嵌套数组在结构上仅仅是Vector的嵌套形式，所以这些MSIL指令同样可以用于嵌套数组的各种操作。在了解了这些指令的功能之后，相信读懂上面关于访问嵌套数组元素的MSIL代码片段并不困难。
相对Vector，MDArray的各种操作要略显复杂一些。为此，CLR实现MDArray的手法有些类似于C++中的泛型模版：系统首先根据多维数组的特性，归纳出Get、Set和Address等几种操作的成员函数模型，其中Get以数组下标作为参数，读取数组中的特定元素；Set则是设置数组中特定下标的元素的值；Address用于取得数组中特定元素的地址。例如，对于一个包含double数据的三维MDArray，以上三个函数的调用形式如下所示：
double Get(int d1, int d2, int d3);
void Set(int d1, int d2, int d3, double v);
double* Address(int d1, int d2, int d3);
但是由于这些函数的具体实现涉及到具体数组的元素类型（主要是用于数组中的偏移量计算），所以CLR不可能直接提供这些函数的实现。只有当程序中引用了包含某个具体类型的MDArray的时候，CLR才会真正定义一个具体的数组类，并且生成上面提到的几个函数的实际代码。前面见到的int32[0…,0…]就是CLR生成的MDArray的一个实例，而Get、Set和Address分别是这个类的三个成员函数。由于这些函数是由运行系统定义的，在类集文件中固然找不到他们的实现，即便是.NET Framework文档中也不见它们的踪影。
在了解了.NET中数组的实际实现之后，再回到我们关于性能的讨论上来：众所周知，函数调用本身是比较耗时的，因为它包含了参数的压栈出栈，以及程序控制流的转移。因此，诸如C++这样的语言需要提供函数内联(inline)的方式以提高函数调用的性能（关于.NET中对于函数内联的支持可以参考条款X）。而直接使用MSIL指令增加了在即时编译（JIT Compile）过程中进一步优化的机会。
看来这一次我们险些被自己的直觉所欺骗了，在.NET中应该是嵌套数组提供了更加优越的性能。但有些看过条款X的读者可能还心存疑问：你怎么知道像Get、Set这样的函数在JIT编译过程中不会采用内联形式编译呢？
很难证明一个函数确实以内联形式嵌入了调用的代码，尤其是在JIT环境下。但有一些简单的办法可以证明JIT编译器根本不会尝试将一些函数进行内联编译——比如采用类型反射(Refelection)：
int[,] mda = new int[3,3]; //定义MDArray
Type t = mda.GetType(); //取得对应的Type
MemberInfo[] minfo = t.GetMember(“Get”);
//我们知道MDArray有唯一的Get函数定义
MethodInfo method = minfo[0] as MethodInfo;
MethodImplAttributes miattr =
method. GetMethodImplementationFlags();
if (miattr & MethodImplAttributes.NoInlining) {
Console.WriteLine(“Oops, can’t be inlined!”);
}
上面的程序段可以取得Get函数的一些特定标志，其中包括告诉JIT编译器避免以内联形式处理该函数的NoInlining标志。如果你编译并运行上面的代码，运行的结果会清楚的告诉你，JIT编译器根本不会尝试以内联的形式处理这些函数。
阻止JIT编译器inline象数组的Get/Set这样的函数无论如何都算不上明智的选择，但实现者也有他们自己的困难——尤其是在系统架构和性能的两难选择上。微软已经表示在.NET Framework的后继版本中将会加入对泛型编程和模版的支持，CLR在MDArray上的努力应该可以看作是对泛型技术支持的一种架构性的尝试。只有在一个完整而优雅的系统架构之上，才有可能进一步完善功能和提高性能。
至此，我们应该已经有充分的理论依据证明嵌套数组具有比多维数组更优越的性能。但还有什么比一个实际的例子更有说服力的呢？
下面的函数用于计算两个字符串的“距离”（其相似程度），其中包含了非常密集的嵌套数组操作。由于将其中的嵌套数组替换为二维数组算不上什么复杂的工作，这里就不再罗列使用二维数组的代码了：
//compute the distance of two char[] strings
public static int StringDiff(char[] str1, char[] str2) {
int COST_INSERT = 1， COST_DELETE = 1；
int COST_REPLACE = 3， COST_MATCH = 0;
int i, j;
int[][] matrix = new int[str1.Length + 1][];
for(i = 0; i < str1.Length + 1; ++ i) {
matrix[i] = new int[str2.Length + 1];
}
matrix[0][0] = 0;
for(i = 1; i < str2.Length + 1; ++ i)
matrix[0][i] = matrix[0][i - 1] + COST_INSERT;
for(j = 1; j < str1.Length + 1; ++ j)
matrix[j][0] = matrix[j - 1][0] + COST_DELETE;
for(i = 1; i < str1.Length + 1; ++ i)
{
for(j = 1; j < str2.Length + 1; ++ j) {
int v1, v2, v3;
v1 = matrix[i][j - 1] + COST_INSERT;
v2 = matrix[i - 1][j] + COST_DELETE;
if (str1[i-1] == str2[j-1]) {
v3 = matrix[i - 1][j - 1] + COST_MATCH;
} else {
v3 = matrix[i - 1][j - 1] + COST_REPLACE;
}
int vmin = (v1 < v2) ? v1: v2;
matrix[i][j] = (vmin < v3) ? vmin: v3;
}
}
return matrix[str1.Length][str2.Length];
}
测试结果显示，在目前的CLR实现之上，使用嵌套数组的版本比使用二维数组要快大约40%。尽管嵌套数组需要更多的创建和初始化工作，但仅凭其性能上的明显优势就足以令我们相信应该尽量以嵌套数组取代多维数组。
最后，还有一个关于嵌套数组使用的需要注意的问题：虽然公共语言规范(CLS，参见条款X)明确规定只要数组中的元素类型与CLS兼容，嵌套数组和所有以零为起始下标的多维数组都是与CLS兼容的数据类型，但由于C#编译器实现的问题，任何包含嵌套数组作为共有成员的类都会被C#编译器认为不与CLS兼容。完全符合标准的代码惨遭编译器的无理拒绝似乎有些不尽情理，但是，怎么说呢，这就是现实。（完）
* 本文系原创作品，未经作者本人许可请勿转载。
