При нахождении пересечения нескольких множеств, которые являются самым быстрым порядком использования keepAll()

Я пытаюсь найти пересечение трех хэш-множеств разного размера. Есть ли разница в скорости, с которой пересечение можно найти, изменяя порядок пересечения множеств. Пример программы:

public class RetainTest { static Set<integer> large =new HashSet<>(); static Set<integer> medium =new HashSet<>(); static Set<integer> small =new HashSet<>(); static int largeSize=10000; static int midSize=5000; static int smallSize=1000; public static void main(String[] args){ preamble() large.retainAll(medium); large.retainAll(small); System.out.println(large.size()); } public static void preamble(){ large =new HashSet<>(); medium =new HashSet<>(); small =new HashSet<>(); Random rnd=new Random(15); for(int i=0;i</integer></integer></integer>
2 ответа

Стоимость запросов в хэш-наборах не зависит от размера набора. setA.retainAll(setB) - это итерация через setA с запросами на setB (см. реализацию AbstractCollection.retainAll()). Общая стоимость этой операции линейно зависит от размера setA. Поэтому вы должны всегда перебирать наименьший набор:

small.retainAll(medium);
small.retainAll(large);

Этот тест подтвердил Ричард Тингл. EDIT Ах, Ричард Тингл тоже автор вопроса :)

Если у вас ровно три набора и производительность действительно важна, попробуйте найти пересечение во время одной итерации:

Iterator<e> it = small.iterator();
while (it.hasNext()) { E e = it.next(); if (!medium.contains(e) || !large.contains(e)) it.remove();
}
</e>

Поскольку Java 8:

small.removeIf(e -> !medium.contains(e) || !large.contains(e));


Профилирование предполагает, что самый быстрый способ объединить несколько наборов состоит в том, чтобы retainAll все большие множества в меньшем множестве. Более того, порядок этих сохранений также должен быть наименьшим по величине. Так

small.retainAll(medium); small.retainAll(large);

Профилирование предполагает, что разница существенна: для этого набора данных самый медленный порядок занял примерно в 10 раз больше, чем самый медленный порядок

Тестовая программа

Эти результаты создаются с использованием следующей тестовой программы, которую оставляли работать в течение 20 минут

public class RetainTest { static Set<integer> large =new HashSet<>(); static Set<integer> medium =new HashSet<>(); static Set<integer> small =new HashSet<>(); static int largeSize=10000; static int midSize=5000; static int smallSize=1000; public static void main(String[] args){ while(true){ preamble(); int size1=largeMediumSmall().size(); preamble(); int size2=largeSmallMedium().size(); preamble(); int size3=smallMediumLarge().size(); preamble(); int size4=smallLargeMedium().size(); preamble(); int size5=mediumSmallLarge().size(); preamble(); int size6=mediumLargeSmall().size(); //sanity check + ensuring the JIT can't optimise out if (size1!=size2 || size1!=size3 || size1!=size4 || size1!=size5 || size1!=size6){ System.out.println("bad"); } } } public static Set<integer> largeMediumSmall(){ large.retainAll(medium); large.retainAll(small); return large; } public static Set<integer> smallMediumLarge(){ small.retainAll(medium); small.retainAll(large); return small; } public static Set<integer> smallLargeMedium(){ small.retainAll(large); small.retainAll(medium); return small; } public static Set<integer> mediumSmallLarge(){ medium.retainAll(small); medium.retainAll(large); return medium; } public static Set<integer> mediumLargeSmall(){ medium.retainAll(large); medium.retainAll(small); return medium; } public static Set<integer> largeSmallMedium(){ large.retainAll(small); large.retainAll(medium); return large; } public static void preamble(){ large =new HashSet<>(); medium =new HashSet<>(); small =new HashSet<>(); Random rnd=new Random(15); for(int i=0;i</integer></integer></integer></integer></integer></integer></integer></integer></integer>

licensed under cc by-sa 3.0 with attribution.