middle

Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины ArrayList

Самый эффективный способ — использовать метод subList(fromIndex, toIndex).clear(). Внутри он вызывает System.arraycopy() один раз, перемещая все элементы правее удаляемого диапазона на нужное количество позиций влево.

Пример

// Удалить элементы с позиции 100 по 200 (не включая 200)
list.subList(100, 200).clear();

Наивный подход — вызывать remove(index) в цикле N раз — приводит к тому, что каждый remove выполняет свой сдвиг элементов. Это O(N * M), где N — количество удаляемых элементов, M — количество оставшихся справа. subList().clear() делает один сдвиг — O(M).

Пример с замером производительности

import java.util.ArrayList;

public class Main {
    private static final int SIZE = 1_000_000;

    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>(SIZE);
        for (int i = 0; i < SIZE; i++) list1.add(i);

        ArrayList<Integer> list2 = new ArrayList<>(list1);

        // Удаление через remove() — медленно
        long start = System.currentTimeMillis();
        for (int i = 0; i < 20_000; i++) {
            list1.remove(600_000);
        }
        System.out.println("remove() в цикле: " + (System.currentTimeMillis() - start) + " мс");

        // Удаление через subList().clear() — быстро
        start = System.currentTimeMillis();
        list2.subList(600_000, 620_000).clear();
        System.out.println("subList().clear(): " + (System.currentTimeMillis() - start) + " мс");
    }
}

На собеседовании: назовите subList().clear() как оптимальный подход. Объясните, почему он быстрее: один вызов System.arraycopy() вместо N.

#performance #best-practices #jcf