时间戳

首页 > 解决方案 > 在列表中插入/更新元素的最快方法

java - 在列表中插入/更新元素的最快方法

问题描述

我想替换提供的列表中的一个对象，或者如果不在此列表中，则添加它。我需要最快的方法来执行此插入/更新。

我有两个版本。哪个更快或者你知道更快的方法吗？

版本 1：

void update(List<Task> orderedTask, Task task) {
        int idx = Collections.binarySearch(orderedTask, task);
        if (idx >= 0) {
            orderedTask.remove(idx);
            orderedTask.add(idx, task);
        } else {
            orderedTask.add(-idx - 1, task);
        }
    }

版本 2：

void update2(List<Task> orderedTask, Task task) {
        var idx = orderedTask.indexOf(task);
        if(idx >= -1) {
            orderedTask.remove(idx);
            orderedTask.add(idx, task);
        }
        else {
            orderedTask.add(-idx - 1, task);
        }
    }

我猜，java流并不比上面的方法快..

标签： javacollectionsjava-stream

解决方案

您应该首先关注正确性而不是性能。

你第二种方法

void update2(List<Task> orderedTask, Task task) {
    var idx = orderedTask.indexOf(task);
    if(idx >= -1) {
        orderedTask.remove(idx);
        orderedTask.add(idx, task);
    }
    else {
        orderedTask.add(-idx - 1, task);
    }
}

已损坏，由于某些未知原因，您将idx >= 0第一个变体的条件更改为，因此当列表中没有匹配元素时idx >= -1，代码将尝试更改无效索引处的元素。-1

当您使用 修复此问题时idx >= 0，您将面临找不到匹配元素时indexOf总是返回的问题-1，这不允许派生插入位置。该公式-idx - 1仅适用于在其合同中指定它的搜索方法，例如binarySearch，但不适用于indexOf。

由于indexOf返回-1不在列表中的元素，因此公式将始终计算为零，因此您始终在列表的开头插入新元素。如果您的合同是要保持列表排序，那么您就没有履行它。除此之外，总是在开头插入对于ArrayList.

如果您的合同是您收到一个排序列表并且必须保持排序，那么这binarySearch是履行合同的唯一方法，而且它比其他方法更有效indexOf。但是当您在处理 时关心性能时ArrayList，您不应该使用orderedTask.remove(idx); orderedTask.add(idx, task);来替换元素。remove(int index)必须复制后备数组中的所有剩余元素，而add(int index, …)必须将它们复制回其原始位置。只需使用该set方法即可。

void update(List<Task> orderedTask, Task task) {
    int idx = Collections.binarySearch(orderedTask, task);
    if (idx >= 0) {
        orderedTask.set(idx, task);
    } else {
        orderedTask.add(-idx - 1, task);
    }
}

推荐阅读