Java 8 数组列表。哪个更快？在索引 0 处插入一项或使用一项创建新列表并将All 添加到新列表？

Question

假设我调用第三方 API 并返回一个可变的 N 多对象列表。该列表可以小到 10 个对象，大到几千个。然后我总是想在返回的列表的索引 0 处插入一个对象。我知道我可以轻松地在索引 0 处调用 add，但这将是 O(n)，因为它会移动插入的每个对象。我的问题是，使用我计划在开头插入的项目创建一个新列表，然后在该新列表上调用 addAll 并传入返回的第 3 方 N 多列表，平均而言(处理方面)会更快吗？

Answer 1

这取决于列表的实现。如果您确实无法了解第三方为您提供的列表实现，您所能做的就是进行实证测试和基准测试。

更有可能的是，他们返回了一种标准 Java 列表类型，而且您确实已经标记了您的问题 arraylist ——这就是您得到的吗？

ArrayList.add(index,element) 使用 System.arrayCopy() 将每个移位的元素从索引 n 复制到 n+1，然后将新元素写入其槽中。这是 O(n)，但它可能确实非常快，因为它将使用高度优化的系统 memmove 例程一次移动整个 RAM block 。 (参见Why are memcpy() and memmove() faster than pointer increments?)。

此外，如果您的额外元素将列表的大小微移到超过分配的支持数组的大小，Java 将创建一个新数组并将整个数组复制到其中。

请记住，您只是复制对象引用，而不是整个对象，因此对于 1000 个元素，您将复制(64 位计算机上最坏的情况)64 位 * 1000 == 8 KB RAM。

不过，对于非常大的列表，所花费的时间可能会变得很长。插入链表更便宜(在开始或结束时应该是 O(1))

您可以通过编写/查找一个仅是现有列表的包装器的 List 实现，使其对任意 List 实现执行 O(1) 操作。例如:

public class HeadedList<T> extends AbstractList<T> {

    private final List tail;

    public HeadedList(T head, List tail) {
       this.head = head;
       this.tail = tail;
    }

    public T get(int index) {
        return index == 0 ? head : tail.get(index - 1);
    }

    public int size() {
        return tail.size() + 1;
    }
}

(注意，如果您使用 Lisp/Clojure 等语言工作，您会非常习惯以这种方式思考列表)

但是，只有当基准测试显示真正的性能问题是由列表构建引起时才需要考虑这个问题。