algorithm - Operaciones de set más rápidas en el oeste
language-agnostic set-intersection (6)
El siguiente artículo presenta algoritmos de unión, intersección y diferencia en conjuntos ordenados que superan a O (Z) si la intersección es mayor que la diferencia (Z> n / 2):
No he podido encontrar ninguna cobertura satisfactoria de este tema en un solo lugar, así que me preguntaba: ¿Cuáles son los algoritmos de intersección, unión y separación más rápidos?
¿Hay alguna interesante con dominios limitados?
¿Puede alguien vencer a O (Z) donde Z es el tamaño real de la intersección?
Si su enfoque se basa en conjuntos ordenados, tenga en cuenta que, pero no lo considere un factor de descalificación. Me parece que debe haber un verdadero almacén de optimizaciones sutiles para compartir, y no quiero perder ninguna de ellas.
Algunos algoritmos que conozco se basan en operaciones bitwise más allá de la vainilla, por lo que puede asumir la presencia de SSE4 y el acceso a elementos intrínsecos como popcount. Tenga en cuenta esta suposición.
De interés: Una implementación de BY Intersect.
Actualizar
Tenemos algunas respuestas parciales realmente buenas, pero todavía espero algunos ataques más completos sobre el problema. Estoy particularmente interesado en ver un uso más articulado de los filtros de floración para atacar el problema.
Actualizar
He hecho algunos trabajos preliminares sobre la combinación de filtros bloom con una tabla de hash de cuco. Se ve casi desagradablemente prometedor, porque tienen demandas muy similares. Seguí adelante y acepté una respuesta, pero no estoy realmente satisfecho en este momento.
En resumen, un conjunto es algo que admite una operación, "¿X es un miembro?". Puede definir esa operación en la intersección A n B en términos de ello en A y B Una implementación se vería algo así como:
interface Set { bool isMember(Object X); };
class Intersection {
Set a, b;
public Intersection(Set A, Set B) { this.a = A; this.b = B; }
public isMember(Object X) {
return a.isMember(X) and b.isMember(Y);
}
}
A y B podrían implementarse utilizando un tipo de conjunto explícito, como un HashSet. El costo de esa operación en cada uno es bastante barato, aproximémoslo con O (1); por lo que el costo en la intersección es solo 2 O ( n ). ;-)
Es cierto que si crea una gran jerarquía de intersecciones como esta, la verificación de un miembro puede ser más costosa, hasta O ( n ) para n conjuntos en la jerarquía. Una optimización potencial para esto podría ser verificar la profundidad de la jerarquía contra un umbral y materializarlo en un HashSet si lo supera. Esto reducirá el costo de operación de los miembros, y tal vez amortizará el costo de construcción cuando se aplican muchas intersecciones.
Para conjuntos razonablemente densos, las listas de intervalos pueden superar a O (n) para las operaciones que especifique, donde n es el número de elementos en el conjunto.
Una lista de intervalos es esencialmente una lista estrictamente creciente de números, [a1, b1, a2, b2, ..., an, bn], donde cada par ai, bi denota el intervalo [ai, bi). La restricción estrictamente creciente garantiza que cada conjunto descriptible tenga una representación única. La representación de un conjunto como una colección ordenada de intervalos permite que sus operaciones de conjunto traten múltiples elementos consecutivos en cada iteración.
Si el conjunto es en realidad un conjunto hash y ambos conjuntos tienen la misma función de hash y el mismo tamaño de tabla, podemos omitir todos los grupos que existen solo en un conjunto. Eso podría limitar la búsqueda un poco.
Si está dispuesto a considerar estructuras similares a conjuntos, los filtros de floración tienen operaciones de unión e intersección triviales.
no hay una solución óptima que O (Z) porque si piensa en el problema de manera lógica, cada uno de los algoritmos de intersección, unión y separación deben al menos leer todos los elementos de entrada una vez, por lo que Z lee es una necesidad. Además, como el conjunto no está ordenado de forma predeterminada, no hay optimizaciones adicionales que puedan superar a O (Z)