数组结构

数组复制与比较、摊销常数

作者 QIFAN 日期 2017-01-05
数组结构

数组是算法里面最基础的一个数据结构了,大概的说一说。


扫盲

Array 如果具象化大概是这个样子。(source:javaTpoint
Array

数组的下标都是从 0 开始的。这是因为,数组里的相邻元素的地址在内存中是连续的。而通过保存首位元素的地址,计算机就可以通过下标定位数组中的任意元素,第 i 位地址 = 首位地址 + 下标 * 每个元素所占字节。 所以下标必须是从 0 开始。

一个数组通常有哪些属性与方法?

通过任意的 IDE ,我们可以很快知道(除了第一个,其余都是从 Object 继承来的):
Array Methods

  1. length 。数组的长度,是一个 immutable field ,一旦创建就不可改变。
  2. equals(Object obj) ,比较与另一个对象是否相等,通常就是比较 hashCode() 是否相等。。
  3. hashCode() ,将数组以内部方式 hash 为一个数字。
  4. clone() ,克隆一个数组,下文也会说。
  5. toString() ,数组的字符串表现形式。

数组操作花费

  1. 查找
    • 若知道下标,时间复杂度 $O(1)$
    • 若给定值,worst case 为 $O(n)$
    • 对于已排序的数组,我们可以用二分查找(见下文) ,时间复杂度为 $O(logn)$
  2. 增加
    不管在头部、中间、或末尾增加,都要经历 查找 + 移动 ,时间复杂度都为 $O(n)$
  3. 删除
    不管在头部、中间、或末尾增加,都要经历 查找 + 移动 ,时间复杂度都为 $O(n)$
  4. 遍历
    时间复杂度 $O(n)$

应用:二分查找(Binary Search)

基本思想:每次查看剩余区间的中点,排除一半元素。

设已排序(升序)的数组为 array ,要查看的区间为 (low, hi) ,要找的值为 target
中点位置 mid = low + (hi - low) / 2 (这里不用 (low + hi) / 2 是为了避免 overflow

if array[mid] == target:
return mid // 找到
if array[mid] > target:
hi = mid - 1 // 查找范围缩小为左半部分 (low, mid - 1)
else:
low = mid + 1 // 查找范围缩小为右半部分 (mid + 1, hi)
repeate find in range (low, hi)

时间优化到 $O(logn)$

很基础,代码在此:binarySearch.java

数组复制

Java 主要由四种数组复制的方法:

  • System.arraycopy()
  • 循环复制
  • Arrays.copyOf()
  • clone()

System.arraycopy() 没看源码,说是调用了底层 C ,整块内存进行复制,那快的。
for 循环虽然很方便,但是相当于“人为”的复制,进进出出可能会浪费不少时间。
Arrays.copyOf() 在底层调用了 System.arraycopy()
clone() 不清楚。

我通过实验(代码:ArrayCopy.java)大概看出来,System.arraycopy() 蜜汁最快, Arrays.copyOf()clone() 差不多,循环复制是最慢的。这也和网上的说法差不多。总之知道 System.arraycopy() 最快就好啦。

深复制与浅复制

既然有数组复制,那就顺便说一说。这个是我特别容易中枪的一块地方。

继承自 java.lang.Object 类的 clone() 方法是浅复制。
Object[] box = {"hello", new String[3], 4};
Object[] boxCopy = box.clone();

对于上述 box 与 boxCopy ,有如下关系:

  • box == boxCopy False
    clone() 生成了一个新的 box 所指对象的引用。
  • box.equals(boxCopy) False
    引用不是同一个。
  • box[0] == boxCopy[0] True
  • box[1] == boxCopy[1] True
  • box[2] == boxCopy[2] True
    浅复制,所以 box 中的元素都是同一个引用。
  • Arrays.equals(box, boxCopy) True
    数组比较比的就是每个元素是否满足 a[i].equals(b[i])

ArrayList

数组的优点是快速定位,缺点就是长度不自由。于是出现了 ArrayList 这个可以长度自由改变又保持了快速定位优点的神物。

但是 ArrayList 的还是数组实现的,只是 Java 爸爸替我们把 resizing 这一步给做了。若在添加操作时数组已满,ArrayList 能够自动扩充(Java 6 之前是增长一倍,之后变成了 (oldLength * 3 / 2 + 1))。方便起见,按照增长一倍来说明。

摊销常数花费

amortized constant cost ,这意味着不是 $O(1)$ ,别不管不顾的往 ArrayList 里添加。

假设有 ArrayList 原始长度为 a ,扩充 n 次后(假设满了),一共有 N 个元素。
总增加元素:$a * 2^n$
普通情况的操作时间: $a * 2^n - n$
resize 情况花费的时间: $(a+1)+(a*2+1)+(a*2^2+1)+…+(a*2^{n-1}+1)=a*(2^{n-1}-1)+n$
总时间: $a * 2^n - n + a*(2^{n-1}-1)+n = 3a(2^{n-1}-1) $ ~ $ 3N$

虽然平均花费保持在常数,但是还是有一次高峰,尤其当元素数量太多时,一次的 bad performance 就够焦虑了。所以在元素数量过多时,不要用 ArrayList

ArrayList 的增长花费为摊销常数

还有一种情况就是很多增加操作后有很多移除操作,那样会造成很多空间的闲置,此时可用 trimToSize() 将数组 resize 到一个合适的大小。



References
https://my.oschina.net/gavinjin/blog/102206



相关文章算法基础梳理



更新历史
+ 2017.01.05 第一版
+ 2017.01.06 新增「数组操作花费」