数据结构与算法之美 王争 学习笔记-2 [MD]

博文地址

我的GitHub 我的博客 我的微信 我的邮箱
baiqiantao baiqiantao bqt20094 baiqiantao@sina.com

目录

目录

基础篇 (38讲)

05 | 数组:为什么很多编程语言中数组都从0开始编号?

为什么数组要从 0 开始编号,而不是从 1 开始呢?

如何实现随机访问?

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

线性表

顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组,链表队列等也是线性表结构。

而与它相对立的概念是非线性表,比如二叉树等。在非线性表中,数据之间并不是简单的前后关系。

数据结构与算法之美 王争 学习笔记-2 [MD]

数据结构与算法之美 王争 学习笔记-2 [MD]

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

第二个是连续的内存空间和相同类型的数据。正是因为这两个限制,它才有了一个堪称杀手锏的特性:随机访问

这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

数组是如何实现根据下标随机访问数组元素的

例如数组 int[] a = new int[10],计算机给数组分配了一块连续内存空间:

数据结构与算法之美 王争 学习笔记-2 [MD]

计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址

a[i]_address = base_address + i * data_type_size

这里我要特别纠正一个错误。我在面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)

低效的插入和删除

插入操作的优化

如果数组中存储的数据并没有任何规律(即:无序),数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。

利用这种处理技巧,在特定场景下,在第 k 个位置插入一个元素的时间复杂度就会降为 O(1)。这个处理思想在快排中也会用到。

正常情况,不会使用这种操作,

删除操作的优化

在某些特殊场景下,我们并不一定非得追求数组中数据的连续性。我们可以先记录下已经删除的数据,每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

这其实就是 JVM 标记清除垃圾回收算法的核心思想。

警惕数组的访问越界问题

数组越界在 C 语言中是一种未决行为,并没有规定数组访问越界时编译器应该如何处理。因为,访问数组的本质就是访问一段连续内存,只要数组通过偏移计算得到的内存地址是可用的(非受限的内存),那么程序就可能不会报任何错误。

容器能否完全替代数组?

ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,就是支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间

因为扩容操作涉及内存申请和数据搬移,是比较耗时的。所以,如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定容器大小

对于业务开发,直接使用容器就足够了,省时省力。毕竟损耗一丢丢性能,完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发,比如开发网络框架,性能的优化需要做到极致,这个时候数组就会优于容器,成为首选。

解答开篇

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

从数组存储的内存模型上来看,下标最确切的定义应该是偏移(offset)。如果用 a 来表示数组的首地址,a[0] 就是偏移为 0 的位置,也就是首地址,a[k] 就表示偏移 k 个 type_size 的位置。

如果从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从 0 开始编号,而不是从 1 开始。

不过,上面解释得再多其实都算不上压倒性的证明,我觉得最主要的原因可能是历史原因。C 语言设计者用 0 开始计数数组下标,之后的 Java、JavaScript 等高级语言都效仿了 C 语言,或者说,为了在一定程度上减少 C 语言程序员学习 Java 的学习成本,因此继续沿用了从 0 开始计数的习惯。实际上,很多语言中数组也并不是从 0 开始计数的,比如 Matlab。甚至还有一些语言支持负数下标,比如 Python。

06 | 链表(上):如何实现LRU缓存淘汰算法?

上一篇:springboot 集成markdown 编辑器


下一篇:1.网页结构分析与xpath分析.md