数组(Arrary),你真的了解吗?开篇我为什么要说这样一句话呢!因为有许多像我这种IT民工(非科班)可能只会用相应语言的一些高级封装的接口,对于底层还不是怎么了解。例如,Python底层就对数组进行了很好的封装,封装后的产物就是Python中的列表,列表的操作很简单。但是尽管如此,我们还是忽略了列表的本质它就是数组,数组可不像封装后的列表那么简单。
为什么在大多数语言中数组都是从0开始编号,而不是从1开始呢?
定义
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储相同类型的数据。
它的存储形式如下:
特性
数组是一种线性表数据结构,在内存中用一块连续的内存空间来存储相同类型的数据,正是因为这种限制让数组拥有了一个“杀手锏”的特性:“随机访问”。
实现随机访问
我们来实现一个长度为10 int类型的数组 int[] a = new int[10],计算机给数组a[10],分配了一组连续的内存空间1000-1039,内存块的首地址为:base_address = 1000。
计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当要访问数组中的某个元素时,将会通过寻址公式,来计算该元素在内存的存储地址:
a[i]_address = base_address + i * data_type_size
- a[i]_addres 元素地址
- base_address 数组内存块的首地址
- data_type_size 元素大小
低效的插入和删除
插入
数组为了保持内存数据的连续性会导致插入、删除这两个操作比较低效。
现有长度为n的数组,现在我们需要将一个数据插入到数组中的第k个位置。那么数组就必须将第k个位置腾出来,存储新的数据。怎么办?就必须将k~n这部分的元素顺序的往后挪一位。
如果在数组末尾插入数据,那么无需挪动数据,时间复杂度为O(1)。但是如果在数组开头插入数据,那么原先的所有数据都需要向后挪动一位,所以最坏的时间复杂度为O(n)。我们在数组的任何位置插入数据的概率都是一样的,所以平均时间复杂度为(1+2+…n)/n=O(n)。
还有一种情况就是,这个数组是用来存放有序的数据,那么我们在第k个位置插入新数据时就要像上边说的那样,挪动k之后的数据。但是如果这个数组仅仅是用来存放数据,只是一个数据集合,这种情况下插入,为了大规模挪动数据,我们可以直接将k位的数据移到数组的最后,把新的元素插入到k位即可。
如图:
利用这样的技巧,在特定情况下可以实现O(1)的插入
删除
与插入类似,如果我们需要删除k位的数据,为了内存的连续性,我们就需要挪动数据,不然数组中间就会出现断层,内存就不连续了。
与插入类似,删除末尾是最好的情况,时间复杂度是O(1)。最坏的情况是删除开头的数据,时间复杂度是O(n)。平均时间复杂度也是O(n)。
优化
那么在有些情况下,我们并不需要追求内存的连续性,我们将多次删除一起操作。
现在需要删除数组中的a,b,c,为了避免其他元素大规模的挪动,可以先记录下来已经删除的数据。每次的删除并不是真正的搬移数据,只是记录数据被删除。当数组没有更多的存储空间来存储数据时,可以再执行一次真正的删除操作,这样就大大减少了删除导致的数据挪动。
Python实现数组(列表)的操作
尽管官方已经为我们实现了插入(append,insert),删除(remove,pop),但是为了加深理解,我们还是来实现一下相关操作:
解答开篇
从数组存储模型上可以看出,实际上的下标可以理解为偏移(offset)。如果用a来表示数组的首地址,那么a[0]就是偏移为0的位置,也就是首地址,a[k]也就是偏移k个type_size 的位置,所以计算 a[k]的内存地址只需要用这个公式:
a[k]_address = base_address + k * type_size
那么我就想从1开始呢,计算公式就会变成这样:
a[k]_address = base_address + (k-1)*type_size
对比两个公式,不难发现,从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。
评论 (0)