самый быстрый способ вставить / обновить элемент в списке - PullRequest
Новая
       17

самый быстрый способ вставить / обновить элемент в списке

0 голосов
/ 01 октября 2019

Я хочу заменить один объект в предоставленном списке или добавить его, если его еще нет в этом списке. Мне нужен быстрый способ сделать эту вставку / обновление.

У меня есть две версии. Что быстрее или вы знаете более быстрый путь?

версия 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 не быстрее, чем описанные выше методы.

1 Ответ

2 голосов
/ 01 октября 2019

Вы должны сначала сосредоточиться на правильности, а не на производительности.

Ваш второй метод 

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);
    }
}
...