Производительность класса Collection на Java

Question

All

Я просматривал множество сайтов, на которых публикуются сообщения о производительности различных классов Collection для различных действий, т. Е. Добавления элемента, поиска и удаления. Но я также замечаю, что все они предоставляют различные среды, в которых проводился тест, т. Е. О.С., память, работающие потоки и т. Д.

У меня вопрос: есть ли какой-либо сайт / материал, который предоставляет такую ​​же информацию о производительности в лучших условиях тестирования? то есть конфигурации не должны быть проблемой или катализатором для плохой работы какой-либо конкретной структуры данных.

[Обновлено]: Пример, HashSet и LinkedHashSet оба имеют сложность O (1) для вставки элемента. Тем не менее, тест Брюса Экеля утверждает, что для LinkedHashSet вставка займет больше времени, чем для HashSet [http://www.artima.com/weblogs/viewpost.jsp?thread=122295]. Так что мне все равно следует придерживаться обозначения Big-Oh?

Answer 1

Вот мои рекомендации:

1. Прежде всего, не оптимизируйте :) Не то, чтобы я говорил вам проектировать дрянное программное обеспечение, но просто сосредоточиться на дизайне и качестве кода больше, чем на преждевременной оптимизации. Предполагая, что вы сделали это, и теперь вам действительно нужно беспокоиться о том, какая коллекция лучше, чем чисто концептуальные соображения, давайте перейдем к пункту 2
2. Действительно, пока не оптимизируйте (грубо украдено у М. Джексона )
3. Fine. Итак, ваша проблема в том, что, хотя у вас есть теоретические формулы сложности времени для лучших, наихудших и средних случаев, вы заметили, что люди говорят разные вещи, и что практические настройки сильно отличаются от теории. Так что запустите свои собственные тесты! Вы можете только читать так много, и пока вы делаете это, ваш код не пишет сам. Как только вы закончите с теорией, напишите свой собственный тест - для вашего реального приложения, а не какое-то неуместное мини-приложение для целей тестирования - и посмотрите, что на самом деле происходит с вашим программным обеспечением и почему. Затем выберите лучший алгоритм. Это эмпирически, это можно считать пустой тратой времени, но это единственный способ, который действительно работает безупречно (пока вы не достигнете следующей точки).
4. Теперь, когда вы это сделали, у вас самое быстрое приложение за всю историю. До следующего обновления JVM. Или какого-либо базового компонента операционной системы, от которого зависит ваше конкретное узкое место в производительности. Угадай, что? Может быть, у ваших клиентов разные. Здесь начинается самое интересное: вам нужно быть уверенным, что ваш эталонный тест действителен для других или в большинстве случаев (или весело писать код для разных случаев). Вам нужно собирать данные от пользователей. МНОГО. И затем вам нужно делать это снова и снова, чтобы увидеть, что происходит, и если это все еще верно. А затем переписывайте ваш код соответственно снова и снова (* - теперь прекращено - Разработка блога Windows 7 на самом деле является хорошим примером того, как сбор пользовательских данных помогает принимать взвешенные решения для улучшения взаимодействия с пользователем.

Или вы можете ... вы знаете ... НЕ оптимизировать. Платформы и компиляторы изменятся, но хороший дизайн должен - в среднем - работать достаточно хорошо.

Другие вещи, которые вы также можете сделать:

• Посмотрите на исходный код JVM. Это очень познавательно, и вы обнаруживаете стадо скрытых вещей (я не говорю, что вы должны их использовать ...)
• Видите ту другую вещь в вашем списке TODO, над которой вам нужно поработать? Да, тот, что вверху, но который вы всегда пропускаете, потому что он слишком сложный или недостаточно увлекательный. Это прямо здесь. Хорошо, доберитесь до этого и оставьте оптимизацию в покое: это злое дитя Ящика Пандоры и группы Мебиуса. Вы никогда не выйдете из этого, и вы глубоко пожалеете, что пытались справиться с этим.

При этом , я не знаю, зачем вам повышение производительности, поэтому, возможно, у вас есть очень веская причина.

И я не говорю, что выбор правильной коллекции не имеет значения. Только те, которые вы знаете, какой выбрать для конкретной проблемы, и что вы рассматривали альтернативы, тогда вы сделали свою работу, не испытывая чувства вины. Коллекции обычно имеют смысловое значение, и если вы будете уважать его, у вас все будет хорошо.

Answer 2

По моему мнению, все, что вам нужно знать о структуре данных, это Big-O операций над ней, а не субъективные измерения от разных архитектур.Различные коллекции служат разным целям.

Map s являются словарями
Set s утверждают уникальность
List s обеспечивают группировку и сохраняют порядок итераций
Tree s обеспечивают дешевое упорядочениеи быстрый поиск по динамически изменяющемуся содержимому, для которого требуется постоянное упорядочение

Отредактировано , чтобы включить утверждение bwawok относительно варианта использования древовидных структур

Обновление
Из Javadoc на LinkedHashSet

Хеш-таблица и реализация связанного списка интерфейса Set с предсказуемым порядком итераций.

...

Производительность, вероятно, будет немного ниже производительности HashSet из-за дополнительных затрат на поддержание связанного списка, за одним исключением: для итерации по LinkedHashSet требуется время, пропорциональное размеру набора, независимо от его емкости.Итерация по HashSet, вероятно, будет более дорогой, требуя времени, пропорционального его емкости.

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

Answer 3

Что вам нужно знать о них и почему? Причина, по которой тесты показывают конкретный JDK и настройку оборудования, заключается в том, что они (теоретически) могут быть воспроизведены. То, что вы должны получить из тестов, это представление о том, как все будет работать. Чтобы получить АБСОЛЮТНЫЙ номер, вам нужно будет запустить его в сравнении с вашим собственным кодом, выполняя свое дело.

Самая важная вещь, которую нужно знать, - это Big O среды выполнения различных коллекций. Зная, что получить элемент из несортированного ArrayList - это O (n), но получить его из HashMap - это O (1) - HUGE .

Если вы уже используете правильный сбор для данной работы, вы на 90% пути туда. Времена, когда вам нужно беспокоиться о том, как быстро вы можете, скажем, извлечь элементы из HashMap, должны быть чертовски редкими.

После того, как вы покинете однопоточное пространство и перейдете в многопоточное пространство, вам нужно будет начать беспокоиться о таких вещах, как ConcurrentHashMap vs Collections.synchronized hashmap. Пока вы не являетесь многопоточным, вы можете просто не беспокоиться о таких вещах и сосредоточиться на том, какую коллекцию использовать.

Обновление до HashSet против LinkedHashSet

Я никогда не встречал сценарий использования, в котором мне нужен был связанный хэш-набор (потому что, если я забочусь о порядке, у меня, как правило, есть список, если я забочусь о O (1), я склонен использовать HashSet. Реально, большинство кода будет использовать ArrayList, HashMap или HashSet. Если вам нужно что-то еще, вы находитесь в «крайнем» случае.

Answer 4

Разные классы коллекций имеют разные характеристики big-O, но все, что вам говорит, это то, как они масштабируются по мере увеличения. Если ваш набор достаточно велик, набор с O (1) будет превосходить набор с O (N) или O (logN), но невозможно определить, какое значение N является точкой безубыточности, кроме как экспериментом.

Как правило, я просто использую простейшую вещь, и затем, если это становится «узким местом», о чем свидетельствуют операции с этой структурой данных, занимающие много процентов времени, я переключусь на что-то с лучшим рейтингом «большой». , Довольно часто либо количество элементов в коллекции никогда не приближается к точке безубыточности, либо существует другой простой способ решения проблемы производительности.

Answer 5

Оба HashSet и LinkedHashSet имеют производительность O (1). То же самое с HashMap и LinkedHashMap (фактически первые реализованы на основе более поздних). Это только говорит о том, как эти алгоритмы масштабируют , а не о том, как они на самом деле работают. В этом случае LinkHashSet выполняет ту же работу, что и HashSet, но также всегда должен обновлять предыдущий и следующий указатель для поддержания порядка. Это означает, что константа (это важное значение также при разговоре о фактической производительности алгоритма) для HashSet ниже, чем LinkHashSet.

Таким образом, поскольку эти два имеют один и тот же Big-O, они масштабируются по существу одинаково - то есть, поскольку n изменений, оба имеют одинаковое изменение производительности и с O (1) производительность, на средний, не меняется.

Так что теперь ваш выбор основан на функциональности и ваших требованиях (что в любом случае должно быть именно тем, что вы считаете первым). Если вам нужны только быстрые операции add и get , вы всегда должны выбрать HashSet. Если вам также необходимо согласованное упорядочение - например, последний доступ или порядок вставки - тогда вы должны также использовать Linked ... версию класса.

Я использовал «связанный» класс в производственных приложениях, ну LinkedHashMap. Я использовал это в одном случае для символа, такого как таблица, поэтому хотел быстрый доступ к символам и соответствующей информации. Но я также хотел вывести информацию по крайней мере в одном контексте в том порядке, в котором пользователь определил эти символы (порядок вставки). Это делает вывод более удобным для пользователя, поскольку они могут находить вещи в том же порядке, в котором они были определены.

Answer 6

Я создал свой собственный эксперимент с HashSets и LinkedHashSets. Для add () и содержит время выполнения O (1), не принимая во внимание множество коллизий. В методе add () для связанного хэш-набора я помещаю объект в созданную пользователем хеш-таблицу O (1), а затем помещаю объект в отдельный связанный список для учета порядка. Таким образом, во время выполнения для удаления элемента из связанного хэш-набора вы должны найти элемент в хеш-таблице и затем выполнить поиск в связанном списке, который имеет порядок. Таким образом, время выполнения составляет O (1) + O (n) соответственно, что составляет o (n) для remove ()

Answer 7

Если бы мне пришлось сортировать миллионы строк, я бы попытался найти другой способ. Возможно, я мог бы улучшить свой SQL, улучшить свой алгоритм или записать элементы на диск и использовать команду сортировки операционной системы.

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