Algoritmo de interseção de lista eficiente

Dadas duas listas (não necessariamente classificadas), qual é o algoritmo não-recursivo mais eficiente para encontrar a interseção dessas listas?

Você poderia colocar todos os elementos da primeira lista em um conjunto de hash. Em seguida, repita o segundo e, para cada um dos seus elementos, verifique o hash para ver se ele existe na primeira lista. Em caso afirmativo, imprima como um elemento da interseção.

Você pode querer dar uma olhada nos filtros Bloom. São vetores de bits que fornecem uma resposta probabilística se um elemento é um membro de um conjunto. A interseção do conjunto pode ser implementada com uma operação E bit a bit simples. Se você tiver um grande número de interseções nulas, o filtro Bloom poderá ajudá-lo a eliminá-las rapidamente. Você ainda terá que recorrer a um dos outros algoritmos mencionados aqui para calcular a interseção real, no entanto. http://en.wikipedia.org/wiki/Bloom_filter

sem hashing, suponho que você tem duas opções:

  • O caminho ingênuo será comparar cada elemento a todos os outros elementos. O (n ^ 2)
  • Outra maneira seria classificar as listas primeiro, depois iterar sobre elas: O (n lg n) * 2 + 2 * O (n)

Na lista de resources do eviews , parece que ele suporta mesclagens e junções complexas (se isso for ‘join’, como na terminologia do database, ele irá calcular uma interseção). Agora cave sua documentação 🙂

Além disso, eviews tem seu próprio fórum de usuários – por que não perguntar?

com o conjunto 1, construa uma tree de busca binária com O(log n) e itere o conjunto2 e pesquise o BST m XO(log n) forma que O(log n) + O(m)+O(log n) ==> O(log n)(m+1) total O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

em C ++ o seguinte pode ser tentado usando o mapa STL

 vector set_intersection(vector s1, vector s2){ vector ret; map store; for(int i=0; i < s1.size(); i++){ store[s1[i]] = true; } for(int i=0; i < s2.size(); i++){ if(store[s2[i]] == true) ret.push_back(s2[i]); } return ret; } 

Aqui está outra solução possível que eu tirei O (nlogn) em complexidade de tempo e sem nenhum armazenamento extra. Você pode conferir aqui https://gist.github.com/4455373

Veja como funciona: Supondo que os conjuntos não contenham nenhuma repetição, mescle todos os conjuntos em um e classifique-o. Em seguida, percorra o conjunto mesclado e, em cada iteração, crie um subconjunto entre o índice atual i e i + n, onde n é o número de conjuntos disponíveis no universo. O que procuramos enquanto fazemos loop é uma sequência repetitiva de tamanho n igual ao número de conjuntos no universo.

Se esse subconjunto em i for igual a esse subconjunto em n, isso significa que o elemento em i é repetido n vezes, o que é igual ao número total de conjuntos. E como não há repetições em nenhum conjunto, isso significa que cada um dos conjuntos contém esse valor, portanto, o adicionamos à interseção. Então, deslocamos o índice por i +, o que fica entre ele e n, porque definitivamente nenhum desses índices formará uma sequência repetitiva.

Primeiro, classifique as duas listas usando quicksort: O (n * log (n). Em seguida, compare as listas navegando primeiro pelos valores mais baixos e adicione os valores comuns. Por exemplo, em lua):

 function findIntersection(l1, l2) i, j = 1,1 intersect = {} while i < #l1 and j < #l2 do if l1[i] == l2[i] then i, j = i + 1, j + 1 table.insert(intersect, l1[i]) else if l1[i] > l2[j] then l1, l2 = l2, l1 i, j = j, i else i = i + 1 end end return intersect end 

qual é O(max(n, m)) onde n e m são os tamanhos das listas.

EDIT: quicksort é recursivo, como dito nos comentários, mas parece que existem implementações não-recursivas

Por que não implementar sua própria tabela de hash simples ou hash set? Vale a pena evitar a interseção de nlogn se as suas listas forem grandes como você diz.

Como você sabe um pouco sobre seus dados de antemão, você deve ser capaz de escolher uma boa function de hash.

Eu segundo a ideia de “sets”. Em JavaScript, você pode usar a primeira lista para preencher um object, usando os elementos da lista como nomes. Em seguida, use os elementos da lista da segunda lista e veja se essas propriedades existem.

Se houver um suporte para conjuntos (como você os chama no título) como embutido, geralmente há um método de interseção.

De qualquer forma, como alguém disse que você poderia fazer isso facilmente (eu não vou postar código, alguém já fez isso) se você tiver as listas ordenadas. Se você não pode usar a recursion, não há problema. Existem implementações sem recursion de ordenação rápida .

No PHP, algo como

 function intersect($X) { // X is an array of arrays; returns intersection of all the arrays $counts = Array(); $result = Array(); foreach ($X AS $x) { foreach ($x AS $y) { $counts[$y]++; } } foreach ($counts AS $x => $count) { if ($count == count($X)) { $result[] = $x; } } return $result; } 

Da definição da notação de Big-Oh:

T (N) = O (f (N)) se houver constantes positivas c e n 0 tais que T (N) ≤ cf (N) quando N ≥ n 0.

O que na prática significa que, se as duas listas são relativamente pequenas, digamos que algo menos de 100 elementos em cada dois loops funciona bem. Repetir a primeira lista e procurar por object semelhante no segundo. No meu caso, funciona muito bem, porque não terei mais de 10 a 20 elementos max nas minhas listas. No entanto, uma boa solução é a ordenação do primeiro O (n log n), ordenar o segundo também O (n log n) e mesclá-los, outro O (n log n) mais ou menos O (3 n log n), dizer que as duas listas são do mesmo tamanho.

O uso de pointers de salto e instruções SSE pode melhorar a eficiência da interseção da lista.

Eu tenho algumas boas respostas que você pode aplicar. Eu não tenho a chance de experimentá-los ainda, mas desde que eles também cobrem interseções, você pode encontrá-los úteis.