Является ли дублирование ArrayList или использование ListIterator быстрее при попытке манипулировать ArrayList?

Question

У меня есть несколько ArrayListс большим количеством данных, и мне нужно быстро и эффективно манипулировать данными. Мой код в настоящее время делает копию оригинала ArrayList чтобы я мог внести изменения (избегая ConcurrentModificationException). Этот подход кажется несколько неэффективным.

Я смотрел в ListIteratorи они кажутся намного более "чистыми" и эффективными. Я провел быстрый тест, чтобы увидеть, что на самом деле быстрее, и, кажется, дублирует оригинал ArrayList может быть быстрее Это правда или мой тест каким-то образом ошибочен? Если это правда, это только для меньшего ArrayLists?

Тест, который я провел, ниже:

long startTime, stopTime;

ArrayList<ArrayList<String>> array = new ArrayList<>();

ArrayList<String> a1 = new ArrayList<>();
ArrayList<String> a2 = new ArrayList<>();
ArrayList<String> a3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    a1.add(Integer.toString(i));
    a2.add(Integer.toString(i));
    a3.add(Integer.toString(i));
}

array.add(a1);
array.add(a2);
array.add(a3);

startTime = System.nanoTime();

ArrayList<ArrayList<String>> arrayCopy = new ArrayList<>();
for (int i = 0; i < array.size(); i++) {
    ArrayList<String> line = array.get(i);
    arrayCopy.add(i, new ArrayList<>(line.size()));
    for (int j = 0; j < line.size(); j++) {
        arrayCopy.get(i).add(j, line.get(j));
    }
}

for (int j = 0; j < array.size(); j++) {
    for (int i = 0; i < array.get(j).size(); i++) {
        if (array.get(j).get(i).equals("2")) {
            arrayCopy.get(j).add(i, "1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(arrayCopy.get(0));
System.out.println(arrayCopy.get(1));
System.out.println(arrayCopy.get(2));

System.out.println(stopTime);

ArrayList<ArrayList<String>> brray = new ArrayList<>();

ArrayList<String> b1 = new ArrayList<>();
ArrayList<String> b2 = new ArrayList<>();
ArrayList<String> b3 = new ArrayList<>();

for (int i = 0; i < 5; i++) {
    b1.add(Integer.toString(i));
    b2.add(Integer.toString(i));
    b3.add(Integer.toString(i));
}

brray.add(b1);
brray.add(b2);
brray.add(b3);

startTime = System.nanoTime();
for (ArrayList<String> s : brray) {
    ListIterator<String> i = s.listIterator();
    while (i.hasNext()) {
        if (i.next().equals("1")) {
            i.add("1.5");
        }
    }
}

stopTime = System.nanoTime() - startTime;

System.out.println(b1);
System.out.println(b2);
System.out.println(b3);

System.out.println(stopTime);

Выполнение кода пять раз дало мне время (в нано секундах) 73307, 46916, 77705, 76606 and 82470 для дублирующего метода и 307888, 319984, 304590, 363235 and 280032 для ListIterator метод.

Answer 1

Я не уверен, не глядя на их реализацию, но из некоторых тестов:

Для больших размеров ListIterator выбьет метод ArrayList.

Для меньших размеров просто создание ListIterator занимает больше времени, чем метод ArrayList.

Кроме того, временные критерии являются своего рода сомнительными, потому что это намного больше, чем просто сама программа. Особенно те, что в 10^(-3) секунд.

Answer 2

Посмотрите на реализацию ArrayList. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.add%28java.lang.Object%29

Вам нужно гораздо больше предметов, чтобы сделать хороший тест. ArrayList использует массив внутри и по умолчанию создает массив из 10 элементов. Таким образом, ваши методы добавления / получения и т. Д. Имеют сложность O(1). Вы можете посмотреть в метод listIterator. Он использует тот же подход. Я думаю, вам не нужно использовать итератор, когда вы используете ArrayList явно, но когда вы используете интерфейс List, потому что реализация может отличаться.