Философия Java

Выбор между списками (List)


Наиболее убедительный способ увидеть различия между реализациями List - это с помощью теста производительности. Следующий код создает внутренний базовый класс для использования в качестве тестовой структуры, затем создается массив анонимных внутренних классов, каждый из которых для различных тестов. Каждый из этих внутренних классов вызывается методом test( ). Этот метод позволяет вам легко добавлять и удалять новые виды тестов.

//: c09:ListPerformance.java

// Демонстрация разницы производительности разных списков.

import java.util.*; import com.bruceeckel.util.*;

public class ListPerformance { private abstract static class Tester { String name; int size; // Тест качества

Tester(String name, int size) { this.name = name; this.size = size; } abstract void test(List a, int reps); } private static Tester[] tests = { new Tester("get", 300) { void test(List a, int reps) { for(int i = 0; i < reps; i++) { for(int j = 0; j < a.size(); j++) a.get(j); } } }, new Tester("iteration", 300) { void test(List a, int reps) { for(int i = 0; i < reps; i++) { Iterator it = a.iterator(); while(it.hasNext()) it.next(); } } }, new Tester("insert", 5000) { void test(List a, int reps) { int half = a.size()/2; String s = "test"; ListIterator it = a.listIterator(half); for(int i = 0; i < size * 10; i++) it.add(s); } }, new Tester("remove", 5000) { void test(List a, int reps) { ListIterator it = a.listIterator(3); while(it.hasNext()) { it.next(); it.remove(); } } }, }; public static void test(List a, int reps) { // Отслеживание с помощью печати имени класса:

System.out.println("Testing " + a.getClass().getName()); for(int i = 0; i < tests.length; i++) { Collections2.fill(a, Collections2.countries.reset(), tests[i].size); System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(a, reps); long t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); } } public static void testArray(int reps) { System.out.println("Testing array as List"); // Можно выполнить только два первых теста из массива:


for(int i = 0; i < 2; i++) { String[] sa = new String[tests[i].size]; Arrays2.fill(sa, Collections2.countries.reset()); List a = Arrays.asList(sa); System.out.print(tests[i].name); long t1 = System.currentTimeMillis(); tests[i].test(a, reps); long t2 = System.currentTimeMillis(); System.out.println(": " + (t2 - t1)); } } public static void main(String[] args) { int reps = 50000; // Или выбираем число повторов

// из командной строки:

if(args.length > 0) reps = Integer.parseInt(args[0]); System.out.println(reps + " repetitions"); testArray(reps); test(new ArrayList(), reps); test(new LinkedList(), reps); test(new Vector(), reps); } } ///:~

Внутренний класс Tester является абстрактным для обеспечения базового класса специальными тестами. Он содержит String для печать, когда начнется тест, параметр size для использования тестом для определения количества элементов или количества повторов, конструктор для инициализации полей и абстрактный метод test( ), который выполняет работу. Все различные типы тестов собраны в одном месте, в массиве tests, который инициализируется различными анонимными внутренними классами, наследованными от Tester. Для добавления или удаления тестов просто добавьте или удалите определение внутреннего класса из массива, а все остальное произойдет автоматически.

Для сравнения доступа к массиву и доступа к контейнеру (первоначально с ArrayList), создан специальный тес для массивов, вложенный в List с помощью Arrays.asList( ). Обратите внимание, что только первые два теста могут быть выполнены в этом случае, потому что вы не можете вставлять или удалять элементы из массива.

List, обрабатываемый test( ), сначала заполняется элементами, затем пробуется каждый тест из массива tests. Результаты варьируются в зависимости от машины; они предназначены лишь дать сравнительный порядок между производительностями разных контейнеров. Вот сводный результат одного запуска:



Type Get Iteration Insert Remove
Массив 1430 3850 нет нет
ArrayList 3070 12200 500 46850
LinkedList 16320 9110 110 60
Vector 4890 16250 550 46850
<


Как и ожидалось, массивы быстрее контейнеров при доступе в случайном порядке и итерациях. Вы можете видеть, что случайный доступ (get( )) дешевле для ArrayList и дороже для LinkedList. (Странно, но итерации быстрее для LinkedList, чем для ArrayList, что немного противоречит интуиции.) С другой стороны, вставка и удаление из середины списка значительно дешевле для LinkedList, чем для ArrayList — особенно удаление. Vector обычно не так быстр, как ArrayList, и его нужно избегать; он остался в библиотеки только по соглашению о поддержке (объяснение того, что он работает в этой программе, в том, что он был адаптирован для List в Java 2). Лучший подход, вероятно, это выбор по умолчанию ArrayList и замена его на LinkedList, если вы обнаружите проблемы производительности при многочисленных вставках и удалениях из середины списка. И Конечно, если вы работаете с группой элементов фиксированного размера, используйте массив.


Содержание раздела