Предыстория
Автор топика, которому почти год, утверждает, что LinkedList целесообразно использовать в случае необходимости вставки элементов в список за постоянное время.
Да, действительно, есть такой теоретический момент. Его любят слушать на собеседованиях. С ним-то мы и будем разбираться.
В чем же суть?
Все в том же топике вы можете почитать разницу ArrayList и LinkedList. Здесь мне хотелось бы лишь вкратце напомнить, что ArrayList построен на базе массива, а LinkedList является связным списком, элементы которого представляют собой некие объекты, хранящие в себе сам хранимый объект, а также ссылки на следующий и предыдущий элементы.
Казалось бы, изменение двух ссылок соседних элементов это и есть выполнение операций добавления/удаления элементов списка за обещанное постоянное время. Это должно было бы быть быстрее, чем сдвигать все элементы после удаляемого или раздвигать их для вставки нового элемента, не так ли? Однако, почему-то, данная теория с крахом проваливается. Все дело в том, каким образом ArrayList осуществляет сдвиги элементов:
Arrays.copyOf(); Данная операция выполняется нативно, без надзора JRE над производимой операцией, что значительно повышает производительность операции.
«А что, если элементов будет много?» — спросите вы. И правильно сделаете. А вот это мы и будем проверять.
От теории к практике
Для проверки скорости работы двух списков был создан класс, который и будет заниматься тестированием. Каждый тест производился некоторое количество раз. Результатом является среднее значение времени выполнения всех тестов.
Общая структура класса
private List<T> list; private Integer numberOfTests; public Tester(List<T> list, Integer numberOfTests) { this.list = list; this.numberOfTests = numberOfTests; } На вход подается уже созданный и заполненный элементами список, а также количество тестов, которые необходимо осуществить.
Методы тестирования
В пример приведу один метод для тестирования времени добавления элемента в середину списка:
public Double testAddingElementsInList() { Integer positionToAdd = list.size() / 2; T elementToInsert = list.get(0); List<Long> listOfResultsInNanos = new ArrayList<>(); for (int i = 0; i < numberOfTests; i++) { Long startTime = System.nanoTime(); list.add(positionToAdd, elementToInsert); Long endTime = System.nanoTime(); listOfResultsInNanos.add(endTime - startTime); } return getAverageTimeInSeconds(listOfResultsInNanos); } Результатом является среднее время выполнения всех тестов в секундах.
Результат общего тестирования
Результатом работы класса является карта. Возвращается результат следующим методом:
public Map<String, Double> runTests() { Map<String, Double> result = new HashMap<>(); result.put("Average time of adding elements", testAddingElementsInList()); result.put("Average time of access to elements", testAccessToElementsInList()); result.put("Average time of searching elements", testSearchElementsInList()); result.put("Average time of removing elements", testRemoveElementsFromList()); return result; } Ну и само тестирование же
Один кусочек кода для тестирования одного из вариантов содержания списка:
List<Integer> arrayListOfIntegers = new ArrayList<>(NUMBER_OF_ELEMENTS_IN_LIST); fillListWithIntegers(arrayListOfIntegers, NUMBER_OF_ELEMENTS_IN_LIST); Tester<Integer> arrayListOfIntegersTester = new Tester<>(arrayListOfIntegers, NUMBER_OF_TESTS); Map<String, Double> arrayListOfIntegersResults = arrayListOfIntegersTester.runTests(); System.out.println("Results of tests of array list with simple integers:"); for (Map.Entry<String, Double> entry : arrayListOfIntegersResults.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } А что если …?
В какой-то момент времени мне пришла в голову мысль. Зачем упрощать жизнь? А что, если двигать более массивные структуры списка? Да, список все равно хранит ссылки на объекты и двигать будет тоже ссылки, но если бы не одно НО, я бы этого, наверное и не писал… Будем двигать список, состоящий из других списков:
List<List<Integer>> arrayListOfListsWithIntegers = new ArrayList<>(NUMBER_OF_ELEMENTS_IN_LIST); fillListWithSubListsOfIntegers(arrayListOfListsWithIntegers, NUMBER_OF_ELEMENTS_IN_LIST, NUMBER_OF_ELEMENTS_IN_SUBLIST); Tester<List<Integer>> arrayListOfListsWithIntegersTester = new Tester<>(arrayListOfListsWithIntegers, NUMBER_OF_TESTS); Map<String, Double> arrayListOfListsWithIntegersResults = arrayListOfListsWithIntegersTester.runTests(); System.out.println("\nResults of tests of array list with lists of integers:"); for (Map.Entry<String, Double> entry : arrayListOfListsWithIntegersResults.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } Результаты
Прежде, чем я выложу результаты тестов, правильно было бы предоставить информацию, скрытую за константами.
| Константа | Описание | Значение |
|---|---|---|
| NUMBER_OF_ELEMENTS_IN_LIST | Количество элементов в тестируемом списке | 10 000 000 |
| NUMBER_OF_ELEMENTS_IN_SUBLIST | Количество элементов, содержащихся в каждом из списков, являющихся элементом тестируемого |
4 |
| NUMBER_OF_TESTS | Количество повторений каждого теста | 100 |
Стоит, пожалуй, также сказать, что добавление, поиск и удаление производились из середины списка.
А что по времени?
Обращаю ваше внимание еще раз на то, что время указано в секундах.
| ArrayList<Integer> | LinkedList<Integer> | ArrayList<List<Integer>> | LinkedList<List<Integer>> | |
|---|---|---|---|---|
| Добавление | 0.03910219 | 0.49232187 | 0.0394498 | 2.13658592 |
| Доступ | 0.00000286 | 0.46187595 | 0.00000304 | 1.83328162 |
| Поиск | 0.00000357 | 0.00000665 | 0.00000261 | 0.00000581 |
| Удаление | 0.17358616 | 0.9823487 | 0.53520523 | 2.52271097 |
Выводы
Как видно из результатов тестов, нативное копирование элементов массива даже достаточно большого размера выполняется настолько быстро, что моментально перекрывает любые теоретические преимущества LinkedList.
Особое внимание можно обратить на тесты списков, хранящих в себе другие списки (или любую другую чуть более «тяжелую» структуру, нежели простое число). ArrayList работает со ссылками, поэтому результаты тестов мало чем отличаются от тестов с обычными числами, в то время, как LinkedList, работая с большими структурами (а 4 элемента в списке элемента это не большая структура), мало того, что не имеет даже теоретических преимуществ, так еще и работает крайне медленно.
Полные исходные коды вы сможете найти в репозитории. Не забудьте откомментировать тот кусок кода, который хотите запустить.
Спасибо за внимание.
ссылка на оригинал статьи http://habrahabr.ru/post/192734/
Добавить комментарий