Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Выбор реализации

Теперь вы должны понимать, что на самом деле есть только три компоненты контейнера: Map, List и Set, и только два из трех реализуют каждый интерфейс. Если вам необходимо использовать функциональность, предлагаемую определенным интерфейсом, как вам решить какую именно реализацию использовать?

Для понимания ответа вы должны усвоить, что каждая из реализаций имеет свои особенности, странности и слабости. Например, вы можете увидеть на диаграмме, что эти “особенности” Hashtable, Vector и Stack являются допустимыми для класса ни не вредят старому коду. С другой стороны, лучше, если вы не используете этого для новый код (Java 2).

Различия между контейнерами часто исходят из того, что они “обслуживают”; то есть, структуры данных, которые физически реализуют необходимый интерфейс. Это означает, например, что ArrayList и LinkedList реализуют интерфейс List, поэтому ваша программа будет выдавать одинаковый результат независимо от того, что вы используете. Однако ArrayList обслуживается массивом, а LinkedList реализован обычным способом для списков с двойным связыванием, в котором есть индивидуальные объекты, каждый из которых содержит данные наряду со ссылками на предыдущий и следующий элемент списка. По этой причине, если вы хотите выполнять много вставок и удалений в середину списка, наиболее подходящим выбором будет LinkedList. (LinkedList также имеет дополнительную функциональность, которая основывается на AbstractSequentialList.) Если это не нужно, то ArrayList обычно быстрее.

В качестве другого примера, Set может быть реализован либо как TreeSet, либо как HashSet. TreeSet основывается на TreeMap и предназначается для производства постоянно упорядоченного множества. Однако, если вы будете использовать большой набор данных для вашего Set, производительность вставки в TreeSet уменьшится. Когда вы пишите программу, в которой нужен Set, вы должны выбрать по умолчанию HashSet и изменить на TreeSet, если более важной задачей является получение постоянного упорядочивания множества.

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

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

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

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

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

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

Выбор между множествами (Set)

Вы можете выбирать между TreeSet и HashSet, в зависимости от размера множества Set (если вам необходимо производить упорядоченную последовательность из Set, используйте TreeSet). Следующая тестовая программа дает оценить затраты:

Следующая таблица показывает результаты одного запуска. (Конечно они будут различаться в зависимости от компьютера и используемой JVM; вы должны запустить тест сами):

Производительность HashSet значительно отличается от TreeSet для всех операций (но обычно при добавлении и поиске, это две наиболее важные операции). Причина использования TreeSet в том, что он содержит се содержимое упорядоченным, так что используйте его только если вам нужно отсортированное множество.

Выбор между картами (Map)

Когда выбираете между реализациями Map, размер Map - это то, что сильно влияет на производительность и приведенная ниже программа показывает необходимые затраты:

Потому что размер карты является критичным, вы увидите, что время тестов, деленное на размер, нормализует каждое измерение. Здесь приведено множество результатов. (Ваши пробы будут отличаться.)

Как вы можете ожидать, производительность Hashtable примерно равна производительности HashMap. (Вы так же можете заметить, что HashMap в общем немного быстрее. HashMap предназначена заменить Hashtable.) TreeMap обычно медленнее, чем HashMap, так почему же вы должны использовать ее? Так как вы можете использовать ее не как Map, а как способ создания упорядоченного списка. Поведение дерева такое, что оно всегда упорядочено и не требует специального упорядочивания. Как только вы заполните TreeMap, вы можете вызвать keySet(), чтобы получить Set представление ключей, а затем toArray() для производства массива этих ключей. Затем вы можете использовать статический метод Arrays.binarySearch() (будет обсужден позже) для повторного поиска объектов в вашем сохраненном массиве. Конечно, вам, вероятно, нужно будет делать это, если, по каким-то причинам, поведение HashMap будет неприемлемым, так как HashMap предназначена для повторного поиска вещей. Так же вы можете легко создать HashMap из TreeMap путем создания единственного объекта. В конце концов, при использовании Map, вашим первым выбором должен быть класс HashMap, и только если вам нужно постоянно упорядоченная Map, вам нужен TreeMap.