3

使用此 Java 代码：

    // create the items list
    List<Item> items = new ArrayList<Item>();
    // ... (add some elements into the list so that it is not empty)

    // iterating ArrayList<Item> from right to left we find the position
    // based on the `if` condition satisfied for an item property
    int pos = 0;
    for (int j = items.size() - 1; j >= 0; j--) {
        Item item = items.get(j);
        if (item.property <= 7) {
            pos = j + 1; break;
        }
    }

    // add new item on the found above position
    Item it = new Item();
    if (pos == items.size()) {
        items.add(it);
    } else {
        items.add(pos, it);
    }

我想知道这个语句Item item = items.get(j);是否会因为使用而需要一些额外的时间来执行ArrayList。例如，假设我们需要将新项目添加到末尾，然后通过调用get()项目列表将仅从左侧迭代它，这是多余的。我希望使用Deque结构而不是ArrayList.

您能推荐什么，也许我完全错了，因为新元素也可以在开始时添加，尽管目标是从右侧迭代到左侧。

4

3 回答 3

9

Get在 ArrayList 中以恒定时间运行。证明：javadoc。

size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。

所以不用担心get性能。ArrayList不是链表。我认为它是由一个普通的 java 数组支持的。

于 2012-07-22T09:59:04.883 回答
1

对于 an ， （右）端ArrayList的操作、迭代和添加/删除是便宜的（基本上 O(1) 或摊销 O(1)）。get(i)但是，在另一端（左）添加/删除元素非常昂贵，并且每次都涉及复制整个后备数组。

因此，如果您需要在两端添加和删除，请务必使用ArrayDeque. 这基本上与ArrayList所有操作一样便宜，但支持以便宜的方式在两端添加。

请注意，如果您只想在列表的开头而不是末尾添加/删除，您仍然可以使用 anArrayList并且只是“向后”（因此，当您想在开头添加某些内容时，只需将其添加到最后，当你想从右到左迭代时，你实际上是从左到右迭代）。

使用该方法插入元素add(Object, int)对于两种数据结构都是 O(n) （插入元素右侧的所有元素都需要在数组中移动）。

另一种方法是使用LinkedList（也实现Deque）。您只需要确保不使用get(int)或任何其他将索引作为 int 传递的方法，因为这是 O(n)。但是，添加/删除/插入操作在列表中的所有位置都是 O(1)（只要您已经有一个指向该位置的迭代器）。因此，对于代码中的循环，调用.listIterator()列表，适当地迭代并使用ListIterator.add(Object)方法插入元素。对于您的代码而言，这将是最便宜的解决方案。

编辑

我没有注意到它ArrayDeque不提供在中间插入元素的方法（尽管它可以，就像ArrayList）。（谢谢啊）所以如果你真的需要所有这些操作（在开头、中间和结尾插入），请使用LinkedListand ListIterator。

于 2012-07-22T10:15:17.683 回答
0

不，可能不是。你的 for 循环从右到左迭代，如果可能是最快的实现。

如果您使用的是 LinkedList，那么答案是肯定的 - 您应该使用 listIterator() 向后迭代，因为 LinkedList 上的 .get(i) 很慢。ArrayList 也有 listIterator()，但使用它和使用简单的 for 循环向后迭代可能没有什么不同。

如果你真的关心每一个毫秒，你应该把人们对这个问题所说的一切以及你在互联网上阅读的基准测试加一点盐，并运行大量负载测试并使用 VisualVM 进行大量分析，以告知你真正的性能在哪里您的系统中的瓶颈是。

于 2012-07-22T10:41:49.860 回答