¿Calcular eficientemente la intersección de dos conjuntos en Java?

¿Cuál es la forma más eficiente de encontrar el tamaño de la intersección de dos conjuntos no dispersos en Java? Esta es una operación que realizaré en grandes series una gran cantidad de veces, por lo que la optimización es importante. No puedo modificar los conjuntos originales.

He observado Apache Commons CollectionUtils.intersection, que parece ser bastante lento. Mi enfoque actual es tomar el más pequeño de los dos conjuntos, clonarlo y luego llamar a .retainAll en el mayor de los dos conjuntos.

public static int getIntersection(Set set1, Set set2) { boolean set1IsLarger = set1.size() > set2.size(); Set cloneSet = new HashSet(set1IsLarger ? set2 : set1); cloneSet.retainAll(set1IsLarger ? set1 : set2); return cloneSet.size(); } 

Ejecute algunas pruebas con el enfoque publicado y contra la construcción de un nuevo HashSet. Es decir, deje que A sea ​​el más pequeño de los conjuntos y B el más grande y luego, para cada ítem en A , si también existe en B, luego agréguelo a C (un nuevo HashSet) – para solo contar, el intermedio El conjunto C se puede omitir.

Al igual que el enfoque publicado, este debería ser un costo O(|A|) ya que la iteración es O(|A|) y la sonda en B es O(1) . No tengo idea de cómo se comparará con el enfoque de clonar y eliminar.

Feliz encoding – y publicar algunos resultados 😉


En realidad, al seguir pensando, creo que esto tiene límites ligeramente mejores que el método en la publicación: O(|A|) frente a O(|A| + |B|) . No tengo idea si esto hará alguna diferencia (o mejora) en la realidad y solo esperaría que fuera relevante cuando |A| <<< |B| |A| <<< |B| .


De acuerdo, entonces estaba realmente aburrido. Al menos en JDK 7 (Windows 7 x64), parece que el método presentado en la publicación es más lento que el anterior , por un factor bueno (aunque aparentemente constante). Mi cálculo aproximado de eyeball dice que es cuatro veces más lento que la sugerencia anterior que solo usa un contador y el doble de lento que cuando se crea un nuevo HashSet. Esto parece ser "bastante consistente" en los diferentes tamaños de conjuntos iniciales.

( Tenga en cuenta que, como señaló Voo, los números anteriores y este micro-benchmark suponen que se está utilizando un HashSet! Y, como siempre, existen peligros con los micro-puntos de referencia. YMMV.)

Estos son los resultados desagradables (tiempos en milisegundos):

  Ejecutando pruebas para 1x1
 IntersectTest $ PostMethod @ 6cc2060e tomó 13.9808544 recuento = 1000000
 IntersectTest $ MyMethod1 @ 7d38847d tomó 2.9893732 recuento = 1000000
 IntersectTest $ MyMethod2 @ 9826ac5 tomó 7.775945 recuento = 1000000
 Ejecutando pruebas para 1x10
 IntersectTest $ PostMethod @ 67fc9fee tomó 12.4647712 recuento = 734000
 IntersectTest $ MyMethod1 @ 7a67f797 tomó 3.1567252 recuento = 734000
 IntersectTest $ MyMethod2 @ 3fb01949 tomó 6.483941 recuento = 734000
 Ejecutando pruebas para 1x100
 IntersectTest $ PostMethod @ 16675039 tomó 11.3069326 recuento = 706000
 IntersectTest $ MyMethod1 @ 58c3d9ac tomó 2.3482693 recuento = 706000
 IntersectTest $ MyMethod2 @ 2207d8bb tomó 4.8687103 recuento = 706000
 Ejecutando pruebas para 1x1000
 IntersectTest $ PostMethod @ 33d626a4 tomó 10.28656 recuento = 729000
 IntersectTest $ MyMethod1 @ 3082f392 tomó 2.3478658 recuento = 729000
 IntersectTest $ MyMethod2 @ 65450f1f tomó 4.109205 recuento = 729000
 Ejecutando pruebas para 10x2
 IntersectTest $ PostMethod @ 55c4d594 tomó 10.4137618 recuento = 736000
 IntersectTest $ MyMethod1 @ 6da21389 tomó 2.374206 recuento = 736000
 IntersectTest $ MyMethod2 @ 2bb0bf9a tomó 4.9802039 recuento = 736000
 Ejecutando pruebas para 10x10
 IntersectTest $ PostMethod @ 7930ebb tomó 25.811083 recuento = 4370000
 IntersectTest $ MyMethod1 @ 47ac1adf tomó 6.9409306 recuento = 4370000
 IntersectTest $ MyMethod2 @ 74184b3b tomó 14.2603248 recuento = 4370000
 Ejecutando pruebas para 10x100
 IntersectTest $ PostMethod @ 7f423820 tomó 25.0577691 recuento = 4251000
 IntersectTest $ MyMethod1 @ 5472fe25 tomó 6.1376042 recuento = 4251000
 IntersectTest $ MyMethod2 @ 498b5a73 tomó 13.9880385 recuento = 4251000
 Ejecutando pruebas para 10x1000
 IntersectTest $ PostMethod @ 3033b503 tomó 25.0312716 recuento = 4138000
 IntersectTest $ MyMethod1 @ 12b0f0ae tomó 6.0932898 recuento = 4138000
 IntersectTest $ MyMethod2 @ 1e893918 tomó 13.8332505 recuento = 4138000
 Ejecutando pruebas para 100x1
 IntersectTest $ PostMethod @ 6366de01 tomó 9.4531628 recuento = 700000
 IntersectTest $ MyMethod1 @ 767946a2 tomó 2.4284762 recuento = 700000
 IntersectTest $ MyMethod2 @ 140c7272 tomó 4.7580235 recuento = 700000
 Ejecutando pruebas para 100x10
 IntersectTest $ PostMethod @ 3351e824 tomó 24.9788668 recuento = 4192000
 IntersectTest $ MyMethod1 @ 465fadce tomó 6.1462852 recuento = 4192000
 IntersectTest $ MyMethod2 @ 338bd37a tomó 13.1742654 recuento = 4192000
 Ejecutando pruebas para 100x100
 IntersectTest $ PostMethod @ 297630d5 tomó 193.0121077 recuento = 41047000
 IntersectTest $ MyMethod1 @ e800537 tomó 45.2652397 recuento = 41047000
 IntersectTest $ MyMethod2 @ 76d66550 tomó 120.8494766 recuento = 41047000
 Ejecutando pruebas para 100x1000
 IntersectTest $ PostMethod @ 33576738 tomó 199.6269531 recuento = 40966000
 IntersectTest $ MyMethod1 @ 2f39a7dd tomó 45.5255814 recuento = 40966000
 IntersectTest $ MyMethod2 @ 723bb663 tomó 122.1704975 recuento = 40966000
 Ejecutando pruebas para 1x1
 IntersectTest $ PostMethod @ 35e3bdb5 tomó 9.5598373 recuento = 1000000
 IntersectTest $ MyMethod1 @ 7abbd1b6 tomó 2.6359174 recuento = 1000000
 IntersectTest $ MyMethod2 @ 40c542ad tomó 6.1091794 recuento = 1000000
 Ejecutando pruebas para 1x10
 IntersectTest $ PostMethod @ 3c33a0c5 tomó 9.4648528 recuento = 733000
 IntersectTest $ MyMethod1 @ 61800463 tomó 2.302116 recuento = 733000
 IntersectTest $ MyMethod2 @ 1ba03197 tomó 5.4803628 recuento = 733000
 Ejecutando pruebas para 1x100
 IntersectTest $ PostMethod @ 71b8da5 tomó 9.4971057 recuento = 719000
 IntersectTest $ MyMethod1 @ 21f04f48 tomó 2.2983538 recuento = 719000
 IntersectTest $ MyMethod2 @ 27e51160 tomó 5.3926902 recuento = 719000
 Ejecutando pruebas para 1x1000
 IntersectTest $ PostMethod @ 2fe7106a tomó 9.4702331 recuento = 692000
 IntersectTest $ MyMethod1 @ 6ae6b7b7 tomó 2.3013066 recuento = 692000
 IntersectTest $ MyMethod2 @ 51278635 tomó 5.4488882 recuento = 692000
 Ejecutando pruebas para 10x2
 IntersectTest $ PostMethod @ 223b2d85 tomó 9.5660879 recuento = 743000
 IntersectTest $ MyMethod1 @ 5b298851 tomó 2.3481445 recuento = 743000
 IntersectTest $ MyMethod2 @ 3b4ac99 tomó 4.8268489 recuento = 743000
 Ejecutando pruebas para 10x10
 IntersectTest $ PostMethod @ 51c700a0 tomó 23.0709476 recuento = 4326000
 IntersectTest $ MyMethod1 @ 5ffa3251 tomó 5.5460785 recuento = 4326000
 IntersectTest $ MyMethod2 @ 22fd9511 tomó 13.4853948 recuento = 4326000
 Ejecutando pruebas para 10x100
 IntersectTest $ PostMethod @ 46b49793 tomó 25.1295491 recuento = 4256000
 IntersectTest $ MyMethod1 @ 7a4b5828 tomó 5.8520418 recuento = 4256000
 IntersectTest $ MyMethod2 @ 6888e8d1 tomó 14.0856942 recuento = 4256000
 Ejecutando pruebas para 10x1000
 IntersectTest $ PostMethod @ 5339af0d tomó 25.1752685 recuento = 4158000
 IntersectTest $ MyMethod1 @ 7013a92a tomó 5.7978328 recuento = 4158000
 IntersectTest $ MyMethod2 @ 1ac73de2 tomó 13.8914112 recuento = 4158000
 Ejecutando pruebas para 100x1
 IntersectTest $ PostMethod @ 3d1344c8 tomó 9.5123442 recuento = 717000
 IntersectTest $ MyMethod1 @ 3c08c5cb tomó 2.34665 recuento = 717000
 IntersectTest $ MyMethod2 @ 63f1b137 tomó 4.907277 cómputo = 717000
 Ejecutando pruebas para 100x10
 IntersectTest $ PostMethod @ 71695341 tomó 24.9830339 recuento = 4180000
 IntersectTest $ MyMethod1 @ 39d90a92 tomó 5.8467864 recuento = 4180000
 IntersectTest $ MyMethod2 @ 584514e9 tomó 13.2197964 recuento = 4180000
 Ejecutando pruebas para 100x100
 IntersectTest $ PostMethod @ 21b8dc91 tomó 195.1796213 recuento = 41060000
 IntersectTest $ MyMethod1 @ 6f98c4e2 tomó 44.5775162 recuento = 41060000
 IntersectTest $ MyMethod2 @ 16a60aab tomó 121.1754402 recuento = 41060000
 Ejecutando pruebas para 100x1000
 IntersectTest $ PostMethod @ 20b37d62 tomó 200.973133 recuento = 40940000
 IntersectTest $ MyMethod1 @ 67ecbdb3 tomó 45.4832226 recuento = 40940000
 IntersectTest $ MyMethod2 @ 679a6812 tomó 121.791293 recuento = 40940000
 Ejecutando pruebas para 1x1
 IntersectTest $ PostMethod @ 237aa07b tomó 9.2210288 recuento = 1000000
 IntersectTest $ MyMethod1 @ 47bdfd6f tomó 2.3394042 recuento = 1000000
 IntersectTest $ MyMethod2 @ a49a735 tomó 6.1688936 recuento = 1000000
 Ejecutando pruebas para 1x10
 IntersectTest $ PostMethod @ 2b25ffba tomó 9.4103967 recuento = 736000
 IntersectTest $ MyMethod1 @ 4bb82277 tomó 2.2976994 recuento = 736000
 IntersectTest $ MyMethod2 @ 25ded977 tomó 5.3310813 recuento = 736000
 Ejecutando pruebas para 1x100
 IntersectTest $ PostMethod @ 7154a6d5 tomó 9.3818786 recuento = 704000
 IntersectTest $ MyMethod1 @ 6c952413 tomó 2.3014931 recuento = 704000
 IntersectTest $ MyMethod2 @ 33739316 tomó 5.3307998 recuento = 704000
 Ejecutando pruebas para 1x1000
 IntersectTest $ PostMethod @ 58334198 tomó 9.3831841 recuento = 736000
 IntersectTest $ MyMethod1 @ d178f65 tomó 2.3071236 recuento = 736000
 IntersectTest $ MyMethod2 @ 5c7369a tomó 5.4062184 recuento = 736000
 Ejecutando pruebas para 10x2
 IntersectTest $ PostMethod @ 7c4bdf7c tomó 9.4040537 recuento = 735000
 IntersectTest $ MyMethod1 @ 593d85a4 tomó 2.3584088 recuento = 735000
 IntersectTest $ MyMethod2 @ 5610ffc1 tomó 4.8318229 recuento = 735000
 Ejecutando pruebas para 10x10
 IntersectTest $ PostMethod @ 46bd9fb8 tomó 23.004925 recuento = 4331000
 IntersectTest $ MyMethod1 @ 4b410d50 tomó 5.5678172 recuento = 4331000
 IntersectTest $ MyMethod2 @ 1bd125c9 tomó 14.6517184 recuento = 4331000
 Ejecutando pruebas para 10x100
 IntersectTest $ PostMethod @ 75d6ecff tomó 25.0114913 recuento = 4223000
 IntersectTest $ MyMethod1 @ 716195c9 tomó 5.798676 recuento = 4223000
 IntersectTest $ MyMethod2 @ 3db0f946 tomó 13.8064737 recuento = 4223000
 Ejecutando pruebas para 10x1000
 IntersectTest $ PostMethod @ 761d8e2a tomó 25.1910652 recuento = 4292000
 IntersectTest $ MyMethod1 @ e60a3fb tomó 5.8621189 recuento = 4292000
 IntersectTest $ MyMethod2 @ 6aadbb1c tomó 13.8150282 recuento = 4292000
 Ejecutando pruebas para 100x1
 IntersectTest $ PostMethod @ 48a50a6e tomó 9.4141906 conteo = 736000
 IntersectTest $ MyMethod1 @ 4b4fe104 tomó 2.3507252 recuento = 736000
 IntersectTest $ MyMethod2 @ 693df43c tomó 4.7506854 recuento = 736000
 Ejecutando pruebas para 100x10
 IntersectTest $ PostMethod @ 4f7d29df tomó 24.9574096 recuento = 4219000
 IntersectTest $ MyMethod1 @ 2248183e tomó 5.8628954 recuento = 4219000
 IntersectTest $ MyMethod2 @ 2b2fa007 tomó 12.9836817 recuento = 4219000
 Ejecutando pruebas para 100x100
 IntersectTest $ PostMethod @ 545d7b6a tomó 193.2436192 recuento = 40987000
 IntersectTest $ MyMethod1 @ 4551976b tomó 44.634367 recuento = 40987000
 IntersectTest $ MyMethod2 @ 6fac155a tomó 119.2478037 recuento = 40987000
 Ejecutando pruebas para 100x1000
 IntersectTest $ PostMethod @ 7b6c238d tomó 200.4385174 recuento = 40817000
 IntersectTest $ MyMethod1 @ 78923d48 tomó 45.6225227 recuento = 40817000
 IntersectTest $ MyMethod2 @ 48f57fcf tomó 121.0602757 recuento = 40817000
 Ejecutando pruebas para 1x1
 IntersectTest $ PostMethod @ 102c79f4 tomó 9.0931408 recuento = 1000000
 IntersectTest $ MyMethod1 @ 57fa8a77 tomó 2.3309466 recuento = 1000000
 IntersectTest $ MyMethod2 @ 198b7c1 tomó 5.7627226 recuento = 1000000
 Ejecutando pruebas para 1x10
 IntersectTest $ PostMethod @ 8c646d0 tomó 9.3208571 recuento = 726000
 IntersectTest $ MyMethod1 @ 11530630 tomó 2.3123797 recuento = 726000
 IntersectTest $ MyMethod2 @ 61bb4232 tomó 5.405318 recuento = 726000
 Ejecutando pruebas para 1x100
 IntersectTest $ PostMethod @ 1a137105 tomó 9.387384 recuento = 710000
 IntersectTest $ MyMethod1 @ 72610ca2 tomó 2.2938749 recuento = 710000
 IntersectTest $ MyMethod2 @ 41849a58 tomó 5.3865938 recuento = 710000
 Ejecutando pruebas para 1x1000
 IntersectTest $ PostMethod @ 100001c8 tomó 9.4289031 recuento = 696000
 IntersectTest $ MyMethod1 @ 7074f9ac tomó 2.2977923 recuento = 696000
 IntersectTest $ MyMethod2 @ fb3c4e2 tomó 5.3724119 recuento = 696000
 Ejecutando pruebas para 10x2
 IntersectTest $ PostMethod @ 52c638d6 tomó 9.4074124 recuento = 775000
 IntersectTest $ MyMethod1 @ 53bd940e tomó 2.3544881 recuento = 775000
 IntersectTest $ MyMethod2 @ 43434e15 tomó 4.9228549 recuento = 775000
 Ejecutando pruebas para 10x10
 IntersectTest $ PostMethod @ 73b7628d tomó 23.2110252 recuento = 4374000
 IntersectTest $ MyMethod1 @ ca75255 tomó 5.5877838 recuento = 4374000
 IntersectTest $ MyMethod2 @ 3d0e50f0 tomó 13.5902641 recuento = 4374000
 Ejecutando pruebas para 10x100
 IntersectTest $ PostMethod @ 6d6bbba9 tomó 25.1999918 recuento = 4227000
 IntersectTest $ MyMethod1 @ 3bed8c5e tomó 5.7879144 recuento = 4227000
 IntersectTest $ MyMethod2 @ 689a8e0e tomó 13.9617882 recuento = 4227000
 Ejecutando pruebas para 10x1000
 IntersectTest $ PostMethod @ 3da3b0a2 tomó 25.1627329 recuento = 4222000
 IntersectTest $ MyMethod1 @ 45a17b4b tomó 5.8319523 recuento = 4222000
 IntersectTest $ MyMethod2 @ 6ca59ca3 tomó 13.8885479 recuento = 4222000
 Ejecutando pruebas para 100x1
 IntersectTest $ PostMethod @ 360202a5 tomó 9.5115367 recuento = 705000
 IntersectTest $ MyMethod1 @ 3dfbba56 tomó 2.3470254 recuento = 705000
 IntersectTest $ MyMethod2 @ 598683e4 tomó 4.8955489 recuento = 705000
 Ejecutando pruebas para 100x10
 IntersectTest $ PostMethod @ 21426d0d tomó 25.8234298 recuento = 4231000
 IntersectTest $ MyMethod1 @ 1005818a tomó 5.8832067 recuento = 4231000
 IntersectTest $ MyMethod2 @ 597b933d tomó 13.3676148 recuento = 4231000
 Ejecutando pruebas para 100x100
 IntersectTest $ PostMethod @ 6d59b81a tomó 193.676662 recuento = 41015000
 IntersectTest $ MyMethod1 @ 1d45eb0c tomó 44.6519088 recuento = 41015000
 IntersectTest $ MyMethod2 @ 594a6fd7 tomó 119.1646115 recuento = 41015000
 Ejecutando pruebas para 100x1000
 IntersectTest $ PostMethod @ 6d57d9ac tomó 200.1651432 recuento = 40803000
 IntersectTest $ MyMethod1 @ 2293e349 tomó 45.5311168 recuento = 40803000
 IntersectTest $ MyMethod2 @ 1b2edf5b tomó 120.1697135 recuento = 40803000 

Y aquí está el micro-benchmark feo (y posiblemente defectuoso):

 import java.util.*; public class IntersectTest { static Random rng = new Random(); static abstract class RunIt { public long count; public long nsTime; abstract int Run (Set s1, Set s2); } // As presented in the post static class PostMethod extends RunIt { public int Run(Set set1, Set set2) { boolean set1IsLarger = set1.size() > set2.size(); Set cloneSet = new HashSet(set1IsLarger ? set2 : set1); cloneSet.retainAll(set1IsLarger ? set1 : set2); return cloneSet.size(); } } // No intermediate HashSet static class MyMethod1 extends RunIt { public int Run (Set set1, Set set2) { Set a; Set b; if (set1.size() <= set2.size()) { a = set1; b = set2; } else { a = set2; b = set1; } int count = 0; for (Long e : a) { if (b.contains(e)) { count++; } } return count; } } // With intermediate HashSet static class MyMethod2 extends RunIt { public int Run (Set set1, Set set2) { Set a; Set b; Set res = new HashSet(); if (set1.size() <= set2.size()) { a = set1; b = set2; } else { a = set2; b = set1; } for (Long e : a) { if (b.contains(e)) { res.add(e); } } return res.size(); } } static Set makeSet (int count, float load) { Set s = new HashSet(); for (int i = 0; i < count; i++) { s.add((long)rng.nextInt(Math.max(1, (int)(count * load)))); } return s; } // really crummy ubench stuff public static void main(String[] args) { int[][] bounds = { {1, 1}, {1, 10}, {1, 100}, {1, 1000}, {10, 2}, {10, 10}, {10, 100}, {10, 1000}, {100, 1}, {100, 10}, {100, 100}, {100, 1000}, }; int totalReps = 4; int cycleReps = 1000; int subReps = 1000; float load = 0.8f; for (int tc = 0; tc < totalReps; tc++) { for (int[] bound : bounds) { int set1size = bound[0]; int set2size = bound[1]; System.out.println("Running tests for " + set1size + "x" + set2size); ArrayList allRuns = new ArrayList( Arrays.asList( new PostMethod(), new MyMethod1(), new MyMethod2())); for (int r = 0; r < cycleReps; r++) { ArrayList runs = new ArrayList(allRuns); Set set1 = makeSet(set1size, load); Set set2 = makeSet(set2size, load); while (runs.size() > 0) { int runIdx = rng.nextInt(runs.size()); RunIt run = runs.remove(runIdx); long start = System.nanoTime(); int count = 0; for (int s = 0; s < subReps; s++) { count += run.Run(set1, set2); } long time = System.nanoTime() - start; run.nsTime += time; run.count += count; } } for (RunIt run : allRuns) { double sec = run.nsTime / (10e6); System.out.println(run + " took " + sec + " count=" + run.count); } } } } } 

Simplemente use el método de Sets#intersection(Set, Set) Google Guava .

Puede evitar todo el trabajo manual utilizando el método Set retainAll ().

De documentos:

s1.retainAll (s2) – transforma s1 en la intersección de s1 y s2. (La intersección de dos conjuntos es el conjunto que contiene solo los elementos comunes a ambos conjuntos).

¿Pueden los miembros de los conjuntos mapearse fácilmente en un rango relativamente pequeño de números enteros? Si es así, considere usar BitSets. La intersección es solo bitwise y es: 32 miembros potenciales a la vez.

Si se pueden ordenar ambos conjuntos, como TreeSet ejecutar ambos iteradores podría ser una manera más rápida de contar la cantidad de objetos compartidos.

Si realiza esta operación a menudo, puede aportar mucho si puede envolver los conjuntos para que pueda almacenar en caché el resultado de la operación de intersección manteniendo una bandera dirty para rastrear la validez del resultado en caché, calculando nuevamente si es necesario.

Usando la secuencia de Java 8:

 set1.stream().filter(s -> set2.contains(s)).collect(Collectors.toList()); 

Si está calculando la intersección solo por el hecho de contar cuántos elementos hay en el conjunto, le sugiero que solo necesite contar la intersección directamente en lugar de construir el conjunto y luego llamar al size() .

Mi función para contar:

 /** * Computes the size of intersection of two sets * @param small first set. preferably smaller than the second argument * @param large second set; * @param  the type * @return size of intersection of sets */ public  int countIntersection(Set small, Set large){ //assuming first argument to be smaller than the later; //however double checking to be sure if (small.size() > large.size()) { //swap the references; Set tmp = small; small = large; large = tmp; } int result = 0; for (T item : small) { if (large.contains(item)){ //item found in both the sets result++; } } return result; } 

Ese es un buen enfoque. Debería obtener el rendimiento O (n) de su solución actual.

Para su información, si cualquier conjunto de conjuntos se clasifica utilizando la misma relación de comparación, entonces puede iterar su intersección en el tiempo N * M, donde N es el tamaño del conjunto más pequeño y M es el número de conjuntos.

Implementación dejada como ejercicio al lector . Aquí hay un ejemplo .