Data Structures and Algorithms DotNet － 2、数组和ArrayList

Created at 2016-09-15 Updated at 2018-05-01 Category Data Structures and Algorithms Tag Data Structures and Algorithms / DotNet

数据结构与算法－2、数组和ArrayList

1、数组

C#中数组是一个类对象，其源自System.Array。

1.1、数组元素的设置和存取访问

常见的有：

1 2	names[2]="Reinhar Hsu"; myName=names[2];

不常见的还有Set和Get方法：

1 2	names.SetValue("Reinhard Hsu",2); myname=names.GetValue(2);

1.2、检索数数组元数据的方法和属性

Length：返回所有维数内元素的总数量
GetLength：返回指定维数内元素的数量
GetUpperBound：返回指定维数内最大的索引号
Rank：返回数组的维数
GetType：返回数组实例的类型，如 System.Int32[]

1.3、多维数组

C#中数组最多可以达到32维。

int [,] grades=new int[4,5];

可以对多维数组使用Get方法：

grade=grades.GetValue(0,2);

但是不能使用Set方法，因为Set方法只接收两个参数，一个是值，一个是索引。
对于上面那个4行5列的二维数组，可以这样访问：

/*最后一门成绩的索引  */
int last_grade=grades.GetUpperBound(1);  

/*最后一个学生的索引  */
int last_student=grades.GetUppderBound(0);  

/*最有一个学生的最后一门成绩  */
grades[last_student,last_grade];

1.4、参数数组

这个我们平时很常见，怎么实现呢：

int Sum(params int[] nums)
{
	int sum=0;
	for(int i=0;i<=nums.GetUpperBound(0);i++)
	{
		sum+=nums[i];
	}
	return sum;
}

total=sum(1,2,3,4,5);

使用参数数组定义方法时，参数数组的参数，要放到方法的参数列表的最后，否则编译器不能正常处理。

1.5、锯齿数组

之前创建的多维数组，每一行都有相同的元素数。但是有些情况，如12个月中，每个月的天数从28天到31天不等。这时候可以使用锯齿数组，数据量庞大的时候，可以有效减少空间。

int[] Jan=new int[31];
int[] Feb=new int[29];
int[][] sales=new int[][]{Jan,Feb};
sales[0][0]=41;

这里sales是一个有着2个元素的整数数组，每个元素又是一个整数数组。

2、ArrayList类

当数组超出存储空间时，ArrayList可以自动调整自身的大小。

2.1、Capacity的初始值真的是16吗？

ArrayList的Capacity属性，存储着数组容量。很多地方说Capacity初始值是16，但是
Reinhard在测试的时候，发现并不是16。详情可以看DotNet 源代码。

2.2、ArrayList的内部实现

这里简单讲讲ArrayList内部实现。
ArrayList里面维护着一个默认起步容量，是4。
ArrayList里面维护着一个Object数组，使用无参数的构造函数初始化时，或者构造函数的参数Capacity为0初始化时，Object数组就会被初始化为Array.Empty

2.3、将ArrayList的Capacity设为1亿，性能会不会有所提升呢？

那我们再来测试下容量设为1亿，看性能是否会提升。

10s~13s之间

虽然提升了20%多，跟Array依然差距明显，看来Array.Copy()的效率还是蛮高的。

2.4、同样都是自动调整自身大小，List为什么就比ArraList快6倍？

那问题出在哪呢？并且List也是自动调整自身大小的，为什么就能比ArrayList快6倍？
Reinhard看了List的自动调整自身大小的实现，跟ArrayList差不多。但是，List与ArrayList不同的是，List是泛型的，避免了装箱／拆箱的操作。拆箱和装箱就这么影响性能么？

2.5、装箱/拆箱操作对性能的影响

那我们再来测试下，对1亿个整数进行装箱，看看耗时多少。

2.5s

而给整数赋值的耗时，和给数组赋值耗时是一样的。
装箱，是把一个值类型，放在一个未确定类型的引用对象中。这个新的引用类型（就是箱子），将存储于堆上，并且，值类型的一个副本，会存放在引用类型的内部。箱子里包含了值类型的副本，并且提供了值类型公有接口的功能。
拆箱，是从箱中取出值类型的副本。这个副本，是值类型的另一个副本。
也就是，关键之处在于，装箱时存放的是值类型的副本，获取箱中数据时，返回的是值类型的另一个副本。