数组和链表（Java & PHP）插入性能比较

开发调优
1

PHP8.1 Array VS SplDoublyLinkedList

// 头部插入
$start = microtime(true);
$arr = [];
$loop = 10000;
for ($i = 0; $i < $loop; $i++) {
    array_unshift($arr, $i);
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->unshift($i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.24384785
链表消耗时间: 0.00041199

// 尾部插入
$start = microtime(true);
$arr = [];
$loop = 1000000;
for ($i = 0; $i < $loop; $i++) {
    $arr[] = $i;
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->push($i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.02418399
链表消耗时间: 0.05259395

// 中间插入
$start = microtime(true);
$arr = [];
$loop = 100000;
for ($i = 0; $i < $loop; $i++) {
    $arr[max(0, $i - 1000)] = $i;
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->add(max(0, $i - 1000), $i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.00508404
链表消耗时间: 8.30184579

Java17 ArrayList VS LinkedList

// 头部插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 100000;
for (int i = 0; i < loop; i++) {
        arrayList.add(0, i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);
        
start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(0, i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 468
链表消耗时间: 6

// 尾部插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 1000000;
for (int i = 0; i < loop; i++) {
        arrayList.add(i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);
        
start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 30
链表消耗时间: 106

// 中间插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 100000;
for (int i = 0; i < loop; i++) {
        arrayList.add(Math.max(0, i - 1000), i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);

start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(Math.max(0, i - 1000), i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 17
链表消耗时间: 161

结论

头部插入链表比数组快，尾部插入和中间插入数组比链表快

分析

  1. 头部插入，数组每次都需对数组扩容（ArrayList可变数组的特点，如果容量不够，会新建一个容量更大的数组，并把老数组的元素copy过去），链表改变各指针指向
  2. 中间插入，数组直接对某个索引设置值，容量不够时才扩容，链表改变各指针指向
  3. 尾部插入，数组直接对某个索引设置值，容量不够时才扩容，链表改变各指针指向
/* jdk ArrayList.add源码 */
// 指定索引插入
public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
		// 头部插入必定扩容，中间插入容量不够时才扩容
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
}
// 尾插
public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
}
private void add(E e, Object[] elementData, int s) {
        //  尾部插入容量不够时才扩容
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
}

/* jdk LinkedList.add源码 */
// 指定索引插入
public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
		    // 头/尾插
            linkLast(element);
        else
		    // 中间插，可以看到这里多了查询节点
            linkBefore(element, node(index));
}
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
}
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
}
Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}
// 尾插
public boolean add(E e) {
        linkLast(e);
        return true;
}

思考

  1. 阅读JDK源码对提升自己有很大的帮助，PHP对应的函数实现应该是大同小异的，但是首先要具备阅读C代码的能力
  2. 目前的状态是换了Java CURD，有些Javaer写的代码也是shit一样，但是生态真的太强大了
  3. 个人渐渐对编程失去了兴趣，后面可能学习前端和python，刺激一下撸码的欲望，另外也好好复习英语，为以后转型做准备吧