При нахождении пересечения нескольких множеств, которые являются самым быстрым порядком использования 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.