Diferencia de conjunto de cómputo entre dos conjuntos grandes

14

Tengo dos grandes conjuntos de enteros y . Cada conjunto tiene aproximadamente un millón de entradas, y cada entrada es un entero positivo que tiene como máximo 10 dígitos de largo. BAB

¿Cuál es el mejor algoritmo para calcular y ? En otras palabras, ¿cómo puedo calcular eficientemente la lista de entradas de que no están en y viceversa? ¿Cuál sería la mejor estructura de datos para representar estos dos conjuntos y hacer que estas operaciones sean eficientes?B A A BABBAAB

El mejor enfoque que se me ocurre es almacenar estos dos conjuntos como listas ordenadas y comparar cada elemento de con cada elemento de , de forma lineal. ¿Podemos hacerlo mejor?BAB

usuario917279
fuente
Si está dispuesto a almacenarlo de manera diferente, podría obtener mejores resultados.
Realz Slaw
Además, si está dispuesto a obtener los resultados como una estructura de datos implícita; simplemente puede hacer una estructura tal que consulte los dos conjuntos para responder cada una de sus propias consultas.
Realz Slaw
1
@ user917279 Un gran punto es: generalmente puede intercambiar el tiempo de preprocesamiento / construcción, el tiempo de consulta y el uso de memoria entre sí. ¿Edita la estructura raramente, pero consulta mucho? ¿Al revés? ¿Es la memoria una preocupación o no? Dichas preguntas pueden responderse desde un punto de vista práctico e informar la elección del constructo "teórico" "correcto".
Raphael
1
@Raphael ¿Sugiere que uno podría hacerlo mejor que los conjuntos confluentemente persistentes (en términos de complejidad) al usar más memoria y / o dedicar más tiempo a la preparación. Solo tengo curiosidad si crees que es posible. No veo tablas de búsqueda como una opción para conjuntos de entrada de este tamaño.
Smossen
1
@ user917279 Si considera el ejemplo de dos conjuntos enormes que son idénticos, cualquier estructura de datos creada utilizando hash-consing admitiría pruebas de igualdad en O (1) ya que estructuras iguales se fusionarán cuando se creen y, por lo tanto, compartirán la misma ubicación de memoria. Los conjuntos con persistencia confluente aprovechan el hash-consing también cuando dos estructuras son casi iguales. La complejidad es la mejor que he visto hasta ahora para conjuntos ordenados.
Smossen

Respuestas:

9

Si está dispuesto a almacenar los conjuntos en una estructura de datos especializada, puede obtener algunas complejidades interesantes.

Sea I=O(min(|A|,|B|,|AΔB|))

Entonces puede hacer operaciones de conjunto y A Δ B , cada una en O ( I log | A | + | B |AB,AB,ABAΔBtiempo esperado. Entonces, esencialmente, obtienes el tamaño mínimo de los dos conjuntos, o, el tamaño de la diferencia simétrica, el que sea menor. Esto es mejor que lineal, si la diferencia simétrica es pequeña; es decir. si tienen una gran intersección De hecho, para las dos operaciones de diferencia de conjuntos que desea, esto es prácticamente sensible a la salida, ya que juntas conforman el tamaño de la diferencia simétrica.O(Ilog|A|+|B|I)

Consulte Conjuntos y mapas con persistencia confluente por Olle Liljenzin (2013) para obtener más información.

Ensalada Realz
fuente
Los treaps en el papel son árboles de búsqueda ordenados. No los consideraría como estructuras de datos no ordenadas.
Smossen
@smossen es cierto, lo edité.
Realz Slaw
6

Una exploración lineal es lo mejor que sé hacer, si los conjuntos se representan como listas enlazadas ordenadas. El tiempo de ejecución es .O(|A|+|B|)

Tenga en cuenta que no necesita comparar cada elemento de con cada elemento de B , en pares. Eso llevaría a un tiempo de ejecución de O ( | A | × | B | ) , que es mucho peor. En cambio, para calcular la diferencia simétrica de estos dos conjuntos, puede usar una técnica similar a la operación "fusionar" en mergesort, modificada adecuadamente para omitir valores que son comunes a ambos conjuntos.ABO(|A|×|B|)

Con más detalle, puede crear un algoritmo recursivo como el siguiente para calcular , suponiendo que A y B se representen como listas vinculadas con sus valores en orden ordenado:ABAB

difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

Lo he representado en pseudo-Python. Si no lee Python, A[0]es el encabezado de la lista vinculada A, A[1:]es el resto de la lista y +representa la concatenación de listas. Por razones de eficiencia, si está trabajando en Python, probablemente no quiera implementarlo exactamente como se indicó anteriormente; por ejemplo, podría ser mejor usar generadores para evitar la creación de muchas listas temporales, pero quería mostrarle las ideas de la forma más simple posible. El propósito de este pseudocódigo es solo ilustrar el algoritmo, no proponer una implementación concreta.

No creo que sea posible hacerlo mejor, si sus conjuntos se representan como listas ordenadas y desea que la salida se proporcione como una lista ordenada. Usted fundamentalmente tiene que mirar todos los elementos de y B . Bosquejo informal de justificación: si hay algún elemento que no ha visto, no puede generarlo, por lo que el único caso en el que puede omitir mirar un elemento es si sabe que está presente tanto en A como en B , pero, ¿cómo podría saber que está presente si no ha analizado su valor?ABAB

DW
fuente
fantástico, ¿tenemos otras opciones si se elimina la restricción de que los conjuntos se almacenen como listas ordenadas?
user917279
2

Si A y B son del mismo tamaño, disjuntos e intercalados (por ejemplo, números impares en A y números pares en B), entonces la comparación por pares de elementos en tiempo lineal es probablemente óptima.

Si A y B contienen bloques de elementos que están exactamente en uno de A o B, o en ambos, es posible calcular la diferencia, la unión y la intersección del conjunto en tiempo sub lineal. Como ejemplo, si A y B difieren exactamente en un elemento, entonces la diferencia se puede calcular en O (log n).

http://arxiv.org/abs/1301.3388

Smossen
fuente
1
Él dice que los conjuntos están ordenados, lo que podría significar que se almacenan como listas, árboles de búsqueda u otra cosa. Si los datos tienen que almacenarse como listas, es bastante interesante pedir "el mejor algoritmo para calcular AB" cuando ningún algoritmo podría hacerlo mejor que escanear las listas en tiempo lineal (para el cual ya encontró un algoritmo).
Smossen
1
Dios, vinculaste el mismo documento que yo (yo, igual que tú, más bien) ... nombra tus enlaces la próxima vez: D
Realz Slaw
@smossen fantástico, a cualquier conocimiento (?) que tengo, los representé como listas ordenadas, pero agradecería humildemente otras sugerencias también.
user917279
2

nABab¯a,b

vzn
fuente
1010
1
R., pierde el punto. un solo longpuede almacenar 32 elementos o 1 byte, 8 elementos. ¡así que las entradas de 1M pueden almacenarse en solo ~ 125K RAM! el almacenamiento puede ser significativamente más eficiente que otras representaciones dependiendo de cómo se implemente el problema ...
vzn
Por lo tanto, necesitaría más de 12 MB para los conjuntos en los que el OP está interesado. Eso arruina todos los cachés (actualmente) y será horrible para los conjuntos dispersos. En particular, la creación de un conjunto vacío domina todas las demás operaciones (para conjuntos dispersos). Knuth aborda este problema en TAoCP, por cierto.
Raphael
12MB? eh? El cartel dijo que solo tiene 2 sets. El póster no especificaba la escasez / densidad de su conjunto. Esto se señala en mi respuesta. ¿Estás asumiendo que tiene conjuntos escasos? no hay una respuesta correcta, el enfoque se señala como una opción alternativa que puede ser útil según las circunstancias. no se usa con
poca
10101061010b1.15GB