34

的文档ArrayDeque说：

这个类在作为栈使用时可能比 Stack 快，作为队列使用时比 LinkedList 快。

没有提到使用 anArrayDeque作为堆栈和使用ArrayList. 您可以将 anArrayList用作堆栈，如下所示。

list.add(object);                      // push
object = list.remove(list.size() - 1); // pop

我发现当我ArrayList只用这种方式时，它的性能比ArrayDeque. 造成这种差异的原因是什么？当然，它不能只是调用size()? 在内部，两者ArrayList和ArrayDeque都是Object[]在需要时使用更大的数组替换的，所以性能肯定应该差不多吗？

4

2 回答 2

34

两种实现之间的主要区别是调整大小策略

  • ArrayList被调整为 的新大小oldCapacity + (oldCapacity >> 1)，导致增加约 50%。默认容量为 10，调整后的容量为 15、22、33、49、73、109、163、244、366...

  • ArrayDeque总是调整为 2 的幂。调整大小时，容量会翻倍。从默认值 16 开始，resize 后的结果容量为 32、64、128、256、...

因此 ArrayDeque 以更少的调整大小操作达到更高的容量，由于数组复制而代价高昂。即在默认大小的 ArrayList 中存储 256，它需要 9 次调整大小调用，而 ArrayDeque 只需要 4 次。数组复制可能很快，但除了内存之外，还可能需要 GC 为新数据集释放一些空间复制成本（ArrayDeque 也可能因为它与 2 的幂对齐而表现得更好）。

两种数据结构都具有 O(1) 的最佳情况复杂度，用于通过直接访问head& tail(ArrayDequeue) 分别添加和删除 (Last) size(ArrayList)进行推送和弹出

于 2017-08-21T09:07:29.880 回答
0

为了回答这个问题，我们来比较一下 ArrayList 和 ArrayDeque 类的 remove 方法。

ArrayList 移除方法

public E remove(int index) {
    this.rangeCheck(index);
    ++this.modCount;
    E oldValue = this.elementData(index);
    int numMoved = this.size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(this.elementData, index + 1, this.elementData, index, numMoved);
    }

    this.elementData[--this.size] = null;
    return oldValue;
}

ArrayDeque removeLast 方法

 public E removeLast() {
    E x = this.pollLast();
    if (x == null) {
        throw new NoSuchElementException();
    } else {
        return x;
    }
}

ArrayDeque removeLast 方法调用 pollLast 方法

    public E pollLast() {
    int t = this.tail - 1 & this.elements.length - 1;
    E result = this.elements[t];
    if (result == null) {
        return null;
    } else {
        this.elements[t] = null;
        this.tail = t;
        return result;
    }
}

下面一步步解释ArrayList的remove方法：

  1. 检查输入的索引是否在数组的范围内
  2. 将 ModCount 变量加一。
  3. 存储要删除的值。
  4. 确定要移动多少个数字（在我们的示例中，找到 numMoved 0 因为最后一个元素将被删除）。
  5. 如果要移动的数字大于 0，则复制数组（因为找到了 numMoved 0，所以不会执行复制）。
  6. 将 null 分配给数组的最后一个元素。
  7. 返回删除的值。

让我们一步一步解释 ArrayDeque removeLast 方法（解释 pollLast 方法就足够了）：

  1. 查找数组的最后一个索引
  2. 返回数组最后一个元素的值。
  3. 如果最后一个元素的值等于 null，则返回 null。
  4. İ如果最后一个元素的值不为null（如果不为null，则会发生以下步骤）。
  5. 将 null 分配给最后一个元素
  6. 更新尾部变量的值
  7. 返回结果

当我们比较这些步骤时，在性能方面没有明显差异。在我们的示例中，ArrayList's System.copyarray 方法将不起作用，因为我们删除了最后一个元素。如果这种方法行得通，就会有性能差异。总之，除了@Gerald Mücke 的回答之外，没有其他需要考虑的区别。如果要删除的元素是列表的第一个元素，那么就会有性能差异。当我们要删除第一个元素时，可以使用类的removeFirst方法ArrayDeque。（该removeFirst方法的工作原理与该方法类似removeLast）。当我们想删除 ArrayList 中的第一个元素时，我们可以使用remove(0)方法。当我们删除索引为 0 的 ArrayList 时，这一次数组 copy( System.copyarray) 将完成。我们过去常说ArrayList由于数组复制过程而速度较慢。

于 2022-02-19T00:10:22.037 回答