数据结构与算法之美05

数据结构与算法之美05

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

数组看起来简单基础,但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号,而不是从1开始的问题,进入主题。

1. 数组如何实现随机访问
1) 数组是一种线性数据结构,用连续的存储空间存储相同类型数据
I) 线性表:数组、链表、队列、栈 非线性表:树 图
II) 连续的内存空间、相同的数据,所以数组可以随机访问,但对数组进行删除插入,为了保证数组的连续性,就要做大量的数据搬移工作
a) 数组如何实现下标随机访问。
引入数组再内存种的分配图,得出寻址公式
b) 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组,用二分查找,时间复杂度也是O(logn)。
正确表述:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

2. 低效的插入和删除
1) 插入:从最好O(1) 最坏O(n) 平均O(n)
2) 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。作者举例说明
3) 删除:从最好O(1) 最坏O(n) 平均O(n)
4) 多次删除集中在一起,提高删除效率
记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

3. 警惕数组的访问越界问题
用C语言循环越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过,很惭愧,看过但是现在也只有一丢丢印象。翻了下书,替作者加上一句话:如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存,那么内存中的i将会被置为0,则为死循环永远出不去。

4. 容器能否完全替代数组
相比于数字,java中的ArrayList封装了数组的很多操作,并支持动态扩容。一旦超过村塾容量,扩容时比较耗内存,因为涉及到内存申请和数据搬移。
数组适合的场景:
1) Java ArrayList 的使用涉及装箱拆箱,有一定的性能损耗,如果特别管柱性能,可以考虑数组
2) 若数据大小事先已知,并且涉及的数据操作非常简单,可以使用数组
3) 表示多维数组时,数组往往更加直观。
4) 业务开发容器即可,底层开发,如网络框架,性能优化。选择数组。

5. 解答开篇问题
1) 从偏移角度理解a[0] 0为偏移量,如果从1计数,会多出K-1。增加cpu负担。
2) 也有一定的历史原因 ,历史的惯性!

JVM标记清除算法:

大多数主流虚拟机采用可达性分析算法来判断对象是否存活,在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后,清理工作才会开始。

不足:1.效率问题。标记和清理效率都不高,但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

二维数组内存寻址:

对于 m * n 的数组,a [ i ][ j ] (i < m,j < n)的地址为:

address = base_address + ( i * n + j) * type_size

另外,对于数组访问越界造成无限循环,我理解是编译器的问题,对于不同的编译器,在内存分配时,会按照内存地址递增或递减的方式进行分配。老师的程序,如果是内存地址递减的方式,就会造成无限循环。

Java二维数组内存分配详解:

引用类型的默认值为null,定义二维数组时,会在堆内存为其分配内存空间(必须知道二维数组的行数,即一维数组的个数,才能够为其分配内存空间),首先给一个地址值0x001给arr,然后为二维数组里的一维数组分配内存空间,分别给一个地址值给一维数组,即0x0001给arr[0],0x0002给arr[1],0x0003给arr[2]。如果arr[3][]第二个元素值没有给出(相当于里面的一维数组的元素个数不知道),即以格式2定义二维数组,那么就无法为一维数组静态的分配内存空间了,即打印出来的arr[0],arr[1],arr[2]地址值是默认值null,可以动态的为其分配内存空间。

发表评论

电子邮件地址不会被公开。 必填项已用*标注