Diferença do conjunto de computação entre dois conjuntos grandes

Eu tenho dois grandes conjuntos de números inteiros e . Cada conjunto possui cerca de um milhão de entradas e cada entrada é um número inteiro positivo com no máximo 10 dígitos. $A$$B$

Qual é o melhor algoritmo para calcular e ? Em outras palavras, como posso calcular com eficiência a lista de entradas de que não estão em e vice-versa? Qual seria a melhor estrutura de dados para representar esses dois conjuntos e tornar essas operações eficientes?B ∖ A A $A\setminus B$$B\setminus A$$A$$B$

A melhor abordagem que posso encontrar é armazenar esses dois conjuntos como listas classificadas e comparar todos os elementos de com todos os elementos de , de maneira linear. Podemos fazer melhor?$A$$B$

Se você estiver disposto a armazenar os conjuntos em uma estrutura de dados especializada, poderá obter algumas complexidades interessantes.

$I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Em seguida, você pode definir as operações e , cada uma em tempo esperado. Então, basicamente, você obtém o tamanho mínimo dos dois conjuntos ou o tamanho da diferença simétrica, o que for menor. Isso é melhor que linear, se a diferença simétrica for pequena; ie se eles tiverem um grande cruzamento. De fato, para as duas operações de diferença de conjunto que você deseja, isso é praticamente sensível à saída, pois juntas elas compõem o tamanho da diferença simétrica.Um Δ B O ( I ⋅ log | A | + | B $A\cup B, A\cap B,A\setminus B$$A\Delta B$$\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$

Consulte Conjuntos e mapas confluentemente persistentes de Olle Liljenzin (2013) para obter mais informações.

Uma varredura linear é a melhor que eu sei fazer, se os conjuntos forem representados como listas vinculadas classificadas. O tempo de execução é .$O(|A| + |B|)$

Observe que você não precisa comparar todos os elementos de com todos os elementos de B , em pares. Isso levaria a um tempo de execução de O ( | A | × | B | ) , que é muito pior. Em vez disso, para calcular a diferença simétrica desses dois conjuntos, você pode usar uma técnica semelhante à operação "mesclar" no mergesort, modificada adequadamente para omitir valores comuns a ambos os conjuntos.$A$$B$$O(|A| \times |B|)$

Mais detalhadamente, você pode criar um algoritmo recursivo como o seguinte para calcular , assumindo que A e B sejam representados como listas vinculadas com seus valores em ordem classificada:$A \setminus B$$A$$B$

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:])

Eu representei isso em pseudo-Python. Se você não lê Python, A[0]é o chefe da lista vinculada A, A[1:]é o restante da lista e +representa a concatenação de listas. Por motivos de eficiência, se você estiver trabalhando em Python, provavelmente não deseja implementá-lo exatamente como acima - por exemplo, talvez seja melhor usar geradores, para evitar a criação de muitas listas temporárias - mas eu queria mostre as idéias da forma mais simples possível. O objetivo deste pseudocódigo é apenas ilustrar o algoritmo, não propor uma implementação concreta.

Eu não acho que seja possível melhorar, se seus conjuntos forem representados como listas classificadas e você desejar que a saída seja fornecida como uma lista classificada. Você fundamentalmente tem que olhar para cada elemento de e B . Esboço informal da justificativa: se houver algum elemento que você não tenha examinado, não poderá produzi-lo; portanto, o único caso em que você pode omitir a observação de um elemento é se souber que ele está presente em A e B , mas como você poderia saber que ele está presente se não analisou seu valor?$A$$B$$A$$B$

Se A e B são de tamanho igual, disjuntos e intercalados (por exemplo, números ímpares em A e números pares em B), a comparação entre pares de itens em tempo linear provavelmente é ideal.

Se A e B contiverem blocos de itens que estão exatamente em um de A ou B, ou em ambos, é possível calcular a diferença de conjunto, união e interseção em tempo sub linear. Por exemplo, se A e B diferem em exatamente um item, a diferença pode ser calculada em O (log n).

http://arxiv.org/abs/1301.3388

$n$$A-B$$a \wedge \overline b$$a,b$