动态数组扩张策略

动态数组
- Java
- Go
- Rust
平摊复杂度
空间局部性
测试
- DynamicArray.java
- Main.java

动态数组

对某些应用程序，我们可能无法预知它会将多少个对象存储在数组中。我们为一个数组分配一定的内存空间，随后可能会发现不够用。于是必须为其重新分配更大的空间，并将所有对象从原数组中复制到新的空间中。Java，Go，Rust中都提供了一种灵活的内置类型：Java提供了ArrayList，Go提供了Slice，Rust提供了Vector，这些数据结构统称为

动态数组

。与数组相比动态数组的长度是不固定的，可以追加元素，在追加时可能使动态数组的容量扩张。

虽然Java，Go，Rust都提供了动态数组。但是当动态数组容量需要增大时，

扩张因子

不尽相同：

Java

如果不考虑边界情形，当ArrayList存储的对象数量达到容量上限时，Java会把ArrayList的容量扩张1.5倍。

int newCapacity = ArraysSupport.newLength(oldCapacity,
					minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);

Go

不考虑边界情形，当Slice存储的对象数量达到容量上限时，Go会把小Slice的容量扩张2倍，大Slice的容量扩张1.25倍。

newcap := oldCap
doublecap := newcap + newcap
if newLen > doublecap {
	newcap = newLen
} else {
	const threshold = 256
	if oldCap < threshold {
		newcap = doublecap
	} else {
		for 0 < newcap && newcap < newLen {
			newcap += (newcap + 3*threshold) / 4
		}
		if newcap <= 0 {
			newcap = newLen
		}
	}
}

Rust

同样不考虑边界情形，当Vector存储的对象数量达到容量上限时，Rust会把Vector的容量扩张2倍。

let cap = cmp::max(self.cap * 2, required_cap);

那么为什么不同语言的动态数组的扩充策略不同呢？或者说选择不同扩张策略有哪些考量呢？

平摊复杂度

虽然Java，Go，Rust的扩张策略的扩大倍数不同，但是就渐进意义而言，不管扩大多少倍，追加新元素也最多消耗常数时间。也就是说对于任意

x>1

$x > 1$

，采用扩张

x

$x$

倍的扩张策略使得
insert
操作的平摊计算复杂度总是

(

)

O(1)

$O (1)$

。

具体来说，如果动态数组的初始容量为

1

$1$

，那么执行足够多（视为无穷大）的

n

$n$

次
insert
操作的实际代价包括了两部分，第一是追加这

n

$n$

个元素的代价，也就是

n

$n$

，第二是每次扩张前复制这些元素的代价:

∑

log

⁡

−

log

⁡

−

1 +x^1 + x^2 + … + n = \sum_{i=0}^{\log_x n} x^i = \frac{1-x^{1+\log_x n}}{1-x}=\frac{1-nx}{1-x}

$1 + x^{1} + x^{2} + \dots + n = i = 0 \sum l o g_{x} n x^{i} = \frac{1 - x ^{1 + l o g_{x} n}}{1 - x} = \frac{1 - n x}{1 - x}$

设
insert
操作的平摊代价是

\hat{c}

$\overset{c}{^}$

，则

−

n+\frac{1-nx}{1-x}=n\hat{c}

$n + \frac{1 - n x}{1 - x} = n \overset{c}{^}$

解得

−

(

−

)

\hat{c}=\frac{2x-1}{x-1} +\frac{1}{n(1-x)}

$\overset{c}{^} = \frac{2 x - 1}{x - 1} + \frac{1}{n ( 1 - x )}$

既然

n

$n$

趋向无穷大，于是

−

\hat{c}=\frac{2x-1}{x-1}

$\overset{c}{^} = \frac{2 x - 1}{x - 1}$

可以看出当

n

$n$

足够大到可以忽略不计时，
insert
操作的平摊代价

\hat{c}

$\overset{c}{^}$

是

x

$x$

的函数。

(

)

\hat{c}(x)

$\overset{c}{^} (x)$

由反比例函数

y=\frac{1}{x}

$y = \frac{1}{x}$

经过平移变换得到，

(

)

\hat{c}(x)

$\overset{c}{^} (x)$

渐近线为

x=1

$x = 1$

和

y=2

$y = 2$

。

在这里插入图片描述

从

(

)

\hat{c}(x)

$\overset{c}{^} (x)$

的图象中可以看出平摊代价随着扩张因子增大而减小。扩张因子接近

1

$1$

时，平摊代价会非常大。当扩张因子很大时，平摊代价会接近下界

2

$2$

。

把整个过程看成一个经济行为：执行

n

$n$

次
insert
操作视为生产一个长度为

n

$n$

的数组，

x

$x$

和

\hat{c}

$\overset{c}{^}$

看视为生产这个数组消耗的计算资源，

x

$x$

代表空间更像是资本

K

$K$

，而

\hat{c}

$\overset{c}{^}$

代表时间更像是劳动

L

$L$

，

x

$x$

和

\hat{c}

$\overset{c}{^}$

之间存在明显的

边际技术替代率递减规律

。当

x<2

$x < 2$

时，空间

x

$x$

的增长是有限的，需要有更频繁的复制操作来生产出这个长度为

n

$n$

的数组，这时只需要稍微提高

x

$x$

，就可以使得

\hat{c}

$\overset{c}{^}$

快速减少。

x>2

$x > 2$

时，继续提高扩张因子所带来在平摊代价上的减少已经相当有限。同时就算有再大的空间，也必须做好至少复制一次数组的准备，这也说明了为什么

\hat{c}

$\overset{c}{^}$

的下界是

2

$2$

。特别地，当

x = 2

$x = 2$

时，

MRTS = 1

$MRTS = 1$

，即经过

)

(2, 3)

$(2, 3)$

的切线斜率为

-1

$- 1$

，这代表在计算资源

x

$x$

和

\hat{c}

$\overset{c}{^}$

均等的情况下进行运算。

空间局部性

空间局部性

指的是最近引用过的内存位置以及其周边的内存位置容易再次被使用。数组通常被认为是具有空间局部性的数据结构，因为数组“元素连续存储”，由此带来一个误区就是数组衍生的列数据结构也必然具有空间局部性，比如动态数组，栈，二叉堆等。其实连续存储是局部性的一个必要条件，而非充要条件。数组的局部性充要条件是：

元素连续存储
整体位置固定

其中“整体位置固定”经常被忽略，如果数组的位置经常发生变化，那么就算元素连续存储，整个数组也未必存储在固定的几个

块

中。因此空间局部性无法确保，程序也未必能利用缓存机制。

可以证明，对于任何动态数组，随着扩张因子的增大，空间局部性会逐渐减小，直至超过一个临界值后，空间局部性不复存在。也就是说如果扩张因子比较小，那么数组存在于比较少的块中；如果扩张因子比较大，那么数组存在于比较多的块中；如果如果扩张因子非常大，那么数组的位置会一直变化。

举个栗子，设动态数组

A

$A$

的初始容量为

C

$C$

，扩张因子为

2

$2$

，并且从地址

0

$0$

开始存储，那么

A

$A$

所占地址空间

)

[0,C)

$[0, C)$

。

第
第
第
第
$C2^n C 2 n ， A A A 新数组所占地址空间 [ C ( 2 n − 1 ) , C ( 2 n + 1 − 1 ) ) [C(2^n-1), C(2^{n+1}-1)) [ C ( 2 n − 1 ) , C ( 2 n + 1 − 1 )) ，所有原数组释放空间 [ 0 , C ( 2 n − 1 − 1 ) ) [0,C(2^{n-1}-1)) [ 0 , C ( 2 n − 1 − 1 )) 比 C 2 n C2^n C 2 n 小 C ( 2 n − 1 + 1 ) C(2^{n-1}+1) C ( 2 n − 1 + 1 ) ，故无法用于分配新空间。释放 [ C ( 2 n − 1 − 1 ) , C ( 2 n − 1 ) ) [C(2^{n-1}-1), C(2^n-1)) [ C ( 2 n − 1 − 1 ) , C ( 2 n − 1 )) ，形成内存碎片。$

可以看出，如果扩张因子为

2

$2$

，在每一次扩张中，新数组无法复用所有原数组释放空间的总和，所以必须在更后的位置分配新的空间。这样一来数组的位置在不断变化，随着元素的追加，数组会一直在内存上游走，空间局部性荡然无存。

但是如果扩张因子为

1.25

$1.25$

可以发现，每

3

$3$

次扩张，程序就可以从地址

0

$0$

开始存储动态数组，从而一定程度保证了动态数组的空间局部性。

那么反过来如果要达到每

3

$3$

次扩张就可以从地址

0

$0$

开始存储动态数组的目标，扩张因子又需要满足什么条件呢？

动态数组第

3

$3$

次扩张后的容量为

Cx^3

$C x^{3}$

，所有原数组释放的空间为

C+Cx

$C + C x$

，这时新容量必须小于所有原数组释放空间的和：

Cx^3<C+Cx

$C x^{3} < C + C x$

x^3<1+x

$x^{3} < 1 + x$

解得

1.32471796

x<1.32471796

$x < 1.32471796$

。

类似地，如果要达到每

4

$4$

次扩张就可以从地址

0

$0$

开始存储动态数组的目标，扩张因子应该满足：

x^4<1+x+x^2

$x^{4} < 1 + x + x^{2}$

解得

1.46557123

x<1.46557123

$x < 1.46557123$

。

每一个

n

$n$

都对应了一个最大扩张因子

x_m

$x_{m}$

，即

(

)

x_m=x_m(n)

$x_{m} = x_{m} (n)$

是

n

$n$

的一个隐函数。从

(

)

x_m(n)

$x_{m} (n)$

的图象中看出，随着

n

$n$

增大，

x_m

$x_{m}$

也随之增大，但并不会超过一个上限。也就是说如果扩张因子超过这个上限，不管

n

$n$

有多大，空间局部性都没办法实现。那么这个上限又是多少呢？

在这里插入图片描述

对于任意的

n

$n$

，如果要每

n

$n$

次扩张就可以从地址

0

$0$

开始存储动态数组，那么

−

x^n<1+x+…+x^{n-2}

$x^{n} < 1 + x + \dots + x^{n - 2}$

x^2<1+x

$x^{2} < 1 + x$

解得

x<\frac{1+\sqrt5}{2}

$x < \frac{1 + 5}{2}$

所以只要扩张因子小于黄金比例

\phi

$ϕ$

，动态数组就有一定空间局部性！

测试

经过测试，在实际摸鱼中，扩张因子的取值（常用范围内）对实际
insert
操作的耗时没有显著影响。

下图显示不同扩张因子的动态数组执行
insert
操作的次数
N
和单次
insert
操作耗时的关系。从图中可以看出，单次
insert
操作耗时20到25纳秒不等，在这种时间尺度内，曲线的波动不能有效解释理论。如果确实存在一个明显优于其他的扩张因子，那大多编程语言便只会用这一个最优的扩张因子，就不会出现不同语言的动态数组扩张因子不尽相同的情形。

在这里插入图片描述

DynamicArray.java

public class  DynamicArray<T> {

    private T[] data;
    private int size;
    private int capacity;
    private final double expansionFactor;

    public DynamicArray(double expansionFactor) {
        this.expansionFactor = expansionFactor;
        size = 0;
        capacity = 1;
        data = (T[]) new Object[capacity];
    }

    public long insert(T element) {
        long tic = System.nanoTime();
        if (size == capacity) { expand(); }
        data[size++] = element;
        long toc = System.nanoTime();
        return toc - tic;
    }

    public void expand() {
        capacity = (int) Math.ceil(expansionFactor * capacity);
        T[] newData = (T[]) new Object[capacity];
        System.arraycopy(data, 0, newData, 0, data.length);
        data = newData;
    }
}

Main.java

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.List;
import java.util.Map;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Map<String, Double> expansionFactors = Map.of(
                "1.25", 1.25,
                "1.5", 1.5,
                "Phi", (1 + Math.sqrt(5)) / 2,
                "1.75", 1.75,
                "2.0", 2.0
        );
        final int STEP = 90;
        final int START1 = 1000;
        final int STOP1 = 10000;
        List<Integer> ns = IntStream
                .iterate(START1, n -> n < STOP1 + 1, n -> n + STEP)
                .boxed()
                .toList();
        final int MAX_ITER = 32;
        insertionStatistics(expansionFactors, ns, MAX_ITER, "DynamicArray.csv");
    }

    public static void insertionStatistics(Map<String, Double> expansionFactors,
                                         List<Integer> ns,
                                         int maxIter,
                                         String fileName) throws FileNotFoundException {

        try (PrintWriter out = new PrintWriter(fileName)) {
            out.println(String.join(",", "ExpansionFactor", "N", "RunningTimeNano"));
            expansionFactors.forEach((expansionFactorString, expansionFactorDouble) ->
                    ns.forEach(n ->
                            out.println(String.join(",",
                                    expansionFactorString,
                                    String.valueOf(n),
                                    String.valueOf(runningTimeNano(expansionFactorDouble, n, maxIter))))));
        }
    }

    public static long runningTimeNano(double expansionFactor, int n, int maxIter) {
        return (long) IntStream
                .range(0, maxIter)
                .mapToLong(__ -> runningTimeNano(expansionFactor, n))
                .summaryStatistics()
                .getAverage();
    }

    public static long runningTimeNano(double expansionFactor, int n) {
        DynamicArray<Integer> data = new DynamicArray<>(expansionFactor);
        return (long) IntStream
                .range(0, n)
                .mapToLong(data::insert)
                .summaryStatistics()
                .getAverage();
    }
}

原文链接：https://blog.csdn.net/LJJ634340797/article/details/131619158

动态数组扩张策略

动态数组

Java

Go

Rust

平摊复杂度

空间局部性

测试

DynamicArray.java

Main.java

你可能也喜欢