数组(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)