Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

ArrayList и LinkedList в цифрах либо отчего тривиальные теоретические результаты не соответствуют практике

Anna | 4.06.2014 | нет комментариев

Добрый день, уважаемые програчитатели. У меня есть один вопрос — вы помните, когда конечный раз применяли LinkedList в вашей практике? Я вот не помню. И на то есть поводы. Не непременно теоретические, но и фактические. В данной статье мне хотелось бы в числах показать, что в 99.9% случаев применение LinkedList легко необоснованно.

Предыстория

Автор топика, которому примерно год, заявляет, что LinkedList уместно применять в случае необходимости вставки элементов в список за непрерывное время.

Да, подлинно, есть такой теоретический момент. Его любят слушать на собеседованиях. С ним-то мы и будем разбираться.

В чем же суть?

Все в том же топике вы можете почитать разницу ArrayList и LinkedList. Тут мне хотелось бы лишь лаконично напомнить, что ArrayList построен на базе массива, а LinkedList является связным списком, элементы которого представляют собой некие объекты, хранящие в себе сам хранимый объект, а также ссылки на дальнейший и предшествующий элементы.

Казалось бы, метаморфоза 2-х ссылок соседних элементов это и есть выполнение операций добавления/удаления элементов списка за обещанное непрерывное время. Это должно было бы быть стремительней, чем сдвигать все элементы позже удаляемого либо раздвигать их для вставки нового элемента, не так ли? Впрочем, отчего-то, данная теория с крахом проваливается. Все дело в том, каким образом ArrayList осуществляет сдвиги элементов:

Arrays.copyOf();

Данная операция выполняется нативно, без надзора JRE над изготавливаемой операцией, что гораздо повышает продуктивность операции.

«А что, если элементов будет много?» — спросите вы. И верно сделаете. А вот это мы и будем проверять.

От теории к практике

Для проверки скорости работы 2-х списков был сделан класс, тот, что и будет заниматься тестированием. Всякий тест производился некоторое число раз. Итогом является среднее значение времени выполнения всех тестов.

Всеобщая конструкция класса

 

	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 элемента в списке элемента это не огромная конструкция), немного того, что не имеет даже теоретических превосходств, так еще и работает весьма медлительно.

Полные начальные коды вы сумеете обнаружить в репозитории. Не позабудьте откомментировать тот кусок кода, тот, что хотите запустить.

Спасибо за внимание.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB