HashSet вместо недостатка производительности ArrayList
В одном из своих проектов я использовал ArrayList<ArrayList<Integer>> в качестве структуры данных графа.
Итак, график:
будет эквивалентен списку ниже:
Но я изменил структуру данных с ArrayList<ArrayList<Integer>> на Map<Integer, Set<Integer>>, поэтому тот же график выше теперь будет эквивалентен карте:
Одна из причин, по которой я выбрал Set, заключается в том, что каждый список должен содержать только уникальные элементы.
Map был выбран из-за простоты управления структурой данных.
Проблема в том, что когда я изменил структуру данных, производительность упала почти в 2 раза.
Вот наиболее часто используемые операции в моем проекте:
В первой реализации:
int index = someIndex();
int v1 = listoflists.get(index).get(0);
int v2 = listoflists.get(index).get(1);
Во второй реализации:
int index = somIndex();
Set<Integer> sets = map.get(index);
Integer[] set = sets.toArray(new Integer[sets.size()]);
int v1 = set[0];
int v2 = set[1];
Иногда мне нужно получить один, два или максимум три элемента.
Есть идеи улучшить производительность второй реализации?
зачем вы переводите набор в массив? вам нужен произвольный доступ к элементам?
1. Я не уверен, зачем кому-то поощрять представление Graphs как List<List<Integer>> или даже Map<Integer, Set<Integer>>! 2. Поскольку ваши операции основаны на индексах, использование Set не имеет особого смысла, можете ли вы не использовать функцию limit и просто элементы 3 из Set и делать то, что вы делаете дальше.
@SharonBenAsher нет, это был мой способ получить эти элементы.
с вашим первым решением вы не обеспечивали уникальность, а во втором вы сделали. так что в основном вы изменили требования. обеспечение уникальности может иметь свою цену ...
Я подозреваю, что toArray() создает новый массив и копирует в него все элементы (это действительно зависит от реализации), почему бы не использовать iterator()?
@SharonBenAsher, я это проверю.
Я только что посмотрел на документация, и он довольно четко описывает создание нового массива, копирование и т. д.
Ответы 1
Integer[] set = sets.toArray(new Integer[sets.size()]);
Приведенная выше строка кода добавляет дополнительную сложность. Оптимизируйте его с помощью Итератора,
int index = somIndex();
Set<Integer> sets = map.get(index);
Iterator iterator = sets.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
Иногда вам требуется всего несколько значений, поэтому выполняйте итерацию соответственно.
Когда вы извлекаете элементы из
Set, выполняете ли вы одно и то же действие со всеми из них?