Оптимизация скорости вставки в java.util.Map/Set

Question

Есть ли способ оптимизировать скорость вставки в java.util.Collection, указав порядок элементов?

Например

java.util.Set<String> set = java.util.TreeSet<String>();

будет ли это решение:

set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("E");

Быть быстрее, чем этот (случайный порядок)?

set.add("E");
set.add("D");
set.add("C");
set.add("A");
set.add("B");

(и тот же вопрос для других коллекций: HashMap, hastable ...)

Спасибо

Answer 1

Простой ответ: «время и посмотри».

Другой ответ: «Это не имеет значения». Кажется, это микрооптимизация, которая вряд ли стоит усилий. Я думаю, что это относится к категории "Печальная трагедия театра микрооптимизации" .

Answer 2

Нет для java.util.Map и java.util.Set, потому что это интерфейсы, и есть разные реализации.

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

Вставка 5000 случайных чисел в HashSet занимает около миллисекунды на обычном ноутбуке, так сколько миллионов элементов вы хотите вставить, чтобы такая оптимизация стояла?

Answer 3

Время вставки для красно-черного дерева (которое используется для реализации Java TreeSet / TreeMap ) гарантированно наихудшим случаем будет O (log n). Это может быть быстрее, если элементы находятся в определенном порядке, но я не уверен, что это будет (вероятно, предварительно отсортированные будут самые быстрые?).

Вставка в хеш-таблицу является операцией O (1) (с постоянным временем). Главное, что нужно сделать для вставки - это вычисление хеш-кода .

---

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

Answer 4

Естественно, существует огромная разница между коллекциями на основе хеша и коллекциями на основе дерева.

Древовидные извлекают выгоду из упорядочения элементов для вставки (например, сравнения между строками), поэтому, когда у вас есть сопоставимые объекты (например, строки), лучше использовать их. TreeSet / TreeMap / и т. Д. в стандартной коллекции предполагается сбалансированный (красно-черное дерево), поэтому порядок вставки не имеет большого значения. Если он не сбалансирован, то порядок вставки будет иметь значение, поскольку вы можете получить цепочку вместо дерева.

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

Если вам нужен набор строк для многих строк с перекрытиями, Trie может быть более эффективным с точки зрения памяти, но я не думаю, что он есть в библиотеке.

Answer 5

Будьте внимательны при рассмотрении характеристик вашей структуры данных при принятии мер по оптимизации. Для одного крайнего примера вставка элементов в двоичное дерево в отсортированном порядке приведет к созданию связанного списка.