关于数组

为什么大多数编程语言中,数组要从 0 开始编号,而不是从 1 开始呢?

其实拿到这个问题的时候,我都很惊讶,为啥我接触数组这么久,自己完全没思考过相关的问题?
于是就更有兴趣看接下来的课程了。

数组

首先,我们得知道数组的访问机制,数组的一大特性就是可以做到任意访问
什么意思呢?

// if 我们有一个这样的数组,是不是可以通过 
const arr = [1,2,3,4]
arr[0] 
arr[3] 

我们就可以通过下标去任意访问任意一个item。

为什么可以做到这样?
因为数组是一种线性表数据结构。他是用一组连续的内存空间来存储具有相同数据类型的一组数据。

  • 关于线性表数据结构
    对之对应概念就是非线性表数据结构
    线性表数据结构的意思就是:数据之间,像排成一条线一样,每个item 只有前或者后两个方向。如数组。链表队列,栈,都是线性表结构。
    非线性表数据结构呢:就类似于树那种,有很多的关系。

这只是一个概念而已,不用太深究。

  • 连续的内存空间和相同的数据类型

当我们const 一个数组的时候,内存会为我们分配一块连续的空间,来存储我们的数组。单位内存是固定的。当计算机需要任意访问数组中的某个元素的时候,它会首先通过下面的的寻址公式计算出这个元素在内存中对应的地址。

const arr = [...]
arr[n]_address = base_address + n * unit_type_size

回到开始的那个问题:

数组下标为何是从0开始的?
从数组的存储模型上看, 下标其实就是数据相对于首地址的偏移量。a[0]就是0个偏移量,
a[n]就是n个偏移量,他的地址就是 首地址 + n * 单位地址。

// 从1开始
arr[n]_address = base_address + (n-1) * unit_type_size
// 从0开始
arr[n]_address = base_address + n* unit_type_size

所以如果从1开始排序的话,是要多一次减法操作的,对于CPU 来说就需要多执行一次指令。在很复杂又很频繁的场景下,可能效率就不那么高了。so,从0开始,优化觉得问题。

所以我们知道了,数组是有序的,那么如果要在数组中插入元素,删除元素,我们需要做什么呢?

  • 插入元素
    还是刚刚那个例子,比如,我们想插入一个元素到arr 中的第二位。因为是arr 是有序的,那么我们必须要先把原有的第二位开始到n的数据,给往后挪一个位置,把第二位给空出来,我才能把数据给塞进去。这时候时间复杂度就是o(n)。
    不过这里也有一个简便一点的方法,把原先第二位的数据,先挪到最后一位去,再把数据塞到第二位。

    这样时间复杂度就是o(1)。但是这里会改变数组里的数据顺序。需谨慎使用。
    关于数组_第1张图片
    移动到最后.jpg
  • 删除元素

其实删除元素类型。在刚刚那个例子中,要删除元素的话,也是需要搬运被删除元素背后的所有数据。这时候时间复杂度也是o(n)。这里有一个场景。如果组 a[10]中存储了 8 个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除 a,b,c 三个元素。
为了避免d,e,f,g,h被搬运三次,那么我们是否可以尝试每次在单个删除的时候,先不去执行实际的操作,只是做一个标记,然后在最后一次操作的时候,一次性去把带有删除标记的三个元素个删除,这样剩下的元素只会被搬运一次。提高了操作效率。

由此我想到,在react 里面,setState 的思想不就是这样的吗?在所有的setState 会合并,到最后才一次性的去执行,就是同样的道理。学习了哈哈哈哈

以上都还只是

你可能感兴趣的