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. B
¿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 B
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?B
algorithms
data-structures
sets
usuario917279
fuente
fuente
Respuestas:
Si está dispuesto a almacenar los conjuntos en una estructura de datos especializada, puede obtener algunas complejidades interesantes.
SeaI=O(min(|A|,|B|,|AΔB|))
Entonces puede hacer operaciones de conjunto y A Δ B , cada una en O ( I ⋅ log | A | + | B |A∪B,A∩B,A∖B AΔB tiempo 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(I⋅log|A|+|B|I)
Consulte Conjuntos y mapas con persistencia confluente por Olle Liljenzin (2013) para obtener más información.
fuente
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.A B O(|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:A∖B A B
Lo he representado en pseudo-Python. Si no lee Python,
A[0]
es el encabezado de la lista vinculadaA
,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?A B A B
fuente
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
fuente
fuente
long
puede almacenar 32 elementos o 1byte
, 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 ...