晨聊数组,温故知新

晨聊数组,温故知新

文章内容参考极客时间《数据结构与算法之美》专栏

数组的随机访问

数组是一种很常见的线性表,其他常见的线性表还包括队列、链表、栈等

计算机会给每个内存单元分配一个地址,当需要访问某个地址单元的数据时,通过下面的寻址公式进行计算:

a[i]_address = base_address + i * data_type_size

这里有一个需要注意的地方,平时说起数组和链表的区别时,我们总是说的朗朗上口:链表适合插入、删除,时间复杂度为O(1),数组适合查找,时间复杂度为O(1),这种说法不是很准确,一个排序好的数组你进行查找的时间复杂度还是O(logn)呢,严谨的说法应该是这样:数组支持随机访问,通过下标进行随机访问的复杂度是O(1)

我们对数组的印象一直是插入和删除操作非常费事,没错,确实是这样,在数组中元素要求严格有序的情况下,每插入一个元素最好的情况是直接插在末尾,最坏的情况是插在头部,需要移动原来的整个数组,平均时间复杂度是O(n),但是当我们的数组中的元素不严格要求有序时,我们是不是可以采用交换的方法呢?

img

如图,当我们要在下表为2的位置插入X时,如果这个数组不要求有序,那么我们可以采用图中的方法,将原来的c放到数组的尾部,然后将x覆盖在c的位置,这样就不需要耗时的移动数组了,实际上,快排中的交换就是使用了这种做法

再来看看删除,这同样是一个需要大量移动元素的操作,那么如何做出优化呢?实际上,我们可以将多次删除操作累计到一起执行,当要删除一个数据时,并不是真正的进行删除,而是标记为已经被删除,当数组中插入元素没有空闲位置时,再执行一次真正的删除操作,这样可以节约移动成本,越说越有内味儿了,实际上JVM中的标记清除算法不就是这种做法嘛

image-20200624101945973

所以我的思考就是,虽然我们工作或者学习中可能接触不到太多算法相关的知识,但确实会在一些设计中都会看到他的身影,这是真正不变的东西,就像我们读过的书,已经印在思维里面

除此之外,我们需要警惕数组的越界问题,这个问题在Java里面还好,如果越界直接抛异常,但是在C语言里面编译器是不会报出错误的,这就可能会出现很多未知的问题,越界问题需要程序员来控制,所以想起一句话,使用Java语言写出来的程序,新手和老手可能差别不是很明显,但是C语言的菜鸡和高手写出来的代码比起来,真的是天差地别

容器

每个语言中都有自己的容器,因为Java主要强调的是封装,所以说对于容器也是非常看重,拿ArrayList来说,容器最大的好处就是将数组的操作封装起来,并且支持动态扩容,需要注意的一个细节就是,ArrayList扩容时的性能问题,扩容时创建出一个原来数组1.5倍大小的新数组,并完成原数组的拷贝工作,这是非常消耗性能的,所以说我们在使用之前最好明确数组的大小,直接分配

那么既然容器这么香,数组还在哪里有用武之地呢?

1.ArrayList无法存储基本数据类型,int、double都要封装为Integer、Double类,而自动装箱和自动拆箱都是有性能损耗的,当数组量比较小的可能不会很明显,但是当性能的要求比较高就可以选用数组

2.如果数组大小已知,并且基本用不到什么集合的操作,也可以使用数组

3.还有一个是我个人的喜好,当要表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList > array。

总结起来就是,平时我们的业务开发使用容器是完全可以的,但是当开发对性能要求比较高的框架时,数组性能会优于容器。

最后一个问题,不知道大家有没有想过,数组的下标为什么是从0开始的呢,而不是1?

还是回到我们最开始的计算机寻址公式上面:

a[i]_address = base_address + i * data_type_size

从公式的角度出发,这个下标不如理解为偏移量,第一个位置是从起始位置开始,偏移量为0,第二个数据是从起始位置开始,偏移量为1

如果要是下标从1开始,那么计算公式就是这样:

a[k]_address = base_address + (k-1)*type_size

每次进行随机访问的时候多了一次减法运算,对于CPU来说,多了一次减法指令

但是我个人觉得,人家CPU还真不在意这一个指令,现在的计算机性能强大到无法想象,我想更多的原因还是习惯问题,因为C语言最开始就是以0开始的, 并且C语言出现的比较早,并且很权威,所以后面就一直这样延用了,也有一些不墨守成规的,例如MatLab,就是从1开始,Python甚至支持负下标