** 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];
}
测试结果显示，在目前的 <SPAN style=