数组和链表(Java & PHP)插入性能比较

23-07-23 00:06 字数 5423 阅读 1995 已编辑

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,刺激一下撸码的欲望,另外也好好复习英语,为以后转型做准备吧
1人点赞>
关注 收藏 改进 举报
0 条评论
排序方式 时间 投票
快来抢占一楼吧
请登录后发表评论