将元素添加到有限大小列表

Question

我有以下方法可以将元素添加到大小受限 ArrayList。如果 ArrayList 的大小超过，则删除前面的元素（如 FIFO =“先进先出”）（版本 1）：

// adds the "item" into "list" and satisfies the "limit" of the list
public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            for (var i = 0; i < exeeded; i++) {
                list.remove(0);
            }
        }
        list.add(item);
    }

“版本 1”方法有效。但是，我想通过使用 subList (version 2):

来改进这个方法

public static <T> void add(List<T> list, final T item, int limit) {
    var size = list.size() + 1;
    if (size > limit) {
        var exeeded = size - limit;
        list.subList(0, exeeded).clear();
    }
    list.add(item);
}

两种方法都有效。但是，我想知道“版本 2”是否也比“版本 1”性能更高。

编辑： 改进了“版本 3”：

public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            if (exeeded > 1) {
                list.subList(0, exeeded).clear();
            } else {
                list.remove(0);
            }
        }
        list.add(item);
    }

Answer 1

问题一：问题出在这一行：

list = list.subList(exeeded, list.size());

您正在重新分配变量 list，它不会更改为作为参数传递的对象，而只会更改为本地对象。

问题 2：子列表（在数组列表上）仍然需要在某个时候重新创建数组。如果你不想这样，你可以使用 LinkedList。但作为一般规则，ArrayList 总体上仍会表现更好。由于底层数组仅在超过最大容量时才需要重新创建，因此通常无关紧要。您也可以尝试实际移动数组，将每个元素移动到数组中的下一个插槽。这样你就必须在添加新元素时移动所有元素，但不需要重新创建数组。因此，您可以避免访问通常对性能影响最大的堆。

Answer 2

您似乎想到了 ArrayList 实现，其中 remove(0) 强加了复制后备数组中所有剩余元素的成本，如果您重复调用 remove(0) 则重复。

在这种情况下，使用 subList(0, number).clear() 是一项重大改进，因为您只需支付一次复制元素的费用，而不是 number 次。

由于 remove(0) 和 subList(0, number).clear() 的复制成本在 number 为 1 时相同，因此第三个变体将节省为子列表创建临时对象的成本案件。然而，这是一个微小的影响，不依赖于列表的大小（或输入的任何其他方面），通常不值得使用更复杂的代码。另请参阅以了解有关单个临时对象成本的讨论。甚至有可能 JVM 的运行时优化器消除了构建子列表的成本。因此，只有当您遇到实际性能问题时才应使用这样的条件，分析器将问题追溯到这一点，和基准测试证明更复杂的代码具有积极的效果。

但是当您改用 ArrayDeque 时，这一切都没有实际意义。这个 class 在删除它的头元素时没有复制成本，因此你可以简单地在循环中删除多余的元素。

将元素添加到有限大小列表

add element to limited size list

java

collections