algorithm - intersection array c

Eficiente algoritmo de intersección de listas

Question

Dadas dos listas (no necesariamente ordenadas), ¿cuál es el algoritmo no recursivo más eficiente para encontrar la intersección de esas listas?

Answer 1

¿Por qué no implementar su propia tabla hash simple o conjunto de hash? Vale la pena evitar nlogn intersection si tus listas son grandes como dices.

Como sabe un poco sobre sus datos de antemano, debería poder elegir una buena función hash.

Answer 2

Aquí hay otra posible solución que surgió con O (nlogn) en complejidad de tiempo y sin ningún almacenamiento adicional. Puedes verlo aquí https://gist.github.com/4455373

Así es como funciona: suponiendo que los conjuntos no contengan ninguna repetición, combine todos los conjuntos en uno y oriéntelos. Luego recorra el conjunto combinado y en cada iteración cree un subconjunto entre el índice actual i e i + n donde n es el número de conjuntos disponibles en el universo. Lo que buscamos mientras bucleamos es una secuencia repetitiva de tamaño n igual al número de conjuntos en el universo.

Si ese subconjunto en i es igual a ese subconjunto en n, esto significa que el elemento en i se repite n veces, que es igual al número total de conjuntos. Y dado que no hay repeticiones en ningún conjunto, esto significa que cada uno de los conjuntos contiene ese valor, así que lo agregamos a la intersección. Luego cambiamos el índice por i + lo que queda entre él y n porque definitivamente ninguno de esos índices formará una secuencia repetitiva.

Answer 3

De la definición de notación Big-Oh:

T (N) = O (f (N)) si hay constantes positivas c y n 0 tales que T (N) ≤ cf (N) cuando N ≥ n 0.

Lo que en la práctica significa que si las dos listas son relativamente pequeñas, digamos que algo menos de 100 elementos en cada dos para bucles funciona bien. Pasa la primera lista y busca objetos similares en el segundo. En mi caso, funciona bien porque no tendré más de 10-20 elementos máximos en mis listas. Sin embargo, una buena solución es ordenar el primer O (n log n), ordenar el segundo también O (n log n) y fusionarlos, otro O (n log n) aproximadamente speeking O (3 n log n), decir que las dos listas son del mismo tamaño.

Answer 4

Desde la lista de características eviews parece que admite fusiones y uniones complejas (si esto es ''join'' como en la terminología DB, calculará una intersección). Ahora profundiza en tu documentación :-)

Además, eviews tiene su propio foro de usuarios, ¿por qué no preguntar allí?

Answer 5

El uso de punteros de salto y las instrucciones de SSE puede mejorar la eficacia de la intersección de listas.

Answer 6

En PHP, algo así 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;
}

Answer 7

Es posible que desee echar un vistazo a los filtros Bloom. Son vectores de bits que dan una respuesta probabilística si un elemento es miembro de un conjunto. La intersección de conjuntos se puede implementar con una operación AND a nivel de bits simple. Si tiene una gran cantidad de intersecciones nulas, el filtro Bloom puede ayudarlo a eliminarlas rápidamente. Sin embargo, tendrá que recurrir a uno de los otros algoritmos mencionados aquí para calcular la intersección real. http://en.wikipedia.org/wiki/Bloom_filter

Answer 8

Obtuve algunas buenas respuestas de this que puede aplicar. No he tenido la oportunidad de probarlos todavía, pero dado que también cubren las intersecciones, puede que les resulten útiles.

Answer 9

Podrías poner todos los elementos de la primera lista en un conjunto de hash. Luego, itere el segundo y, para cada uno de sus elementos, verifique el hash para ver si existe en la primera lista. Si es así, déjelo salir como un elemento de la intersección.

Answer 10

Primero, ordene ambas listas usando quicksort: O (n * log (n). Luego, compare las listas examinando primero los valores más bajos y agregue los valores comunes. Por ejemplo, en 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

que es O(max(n, m)) donde n y m son los tamaños de las listas.

EDITAR: quicksort es recursivo, como se dice en los comentarios, pero parece que hay codeguru.com/forum/archive/index.php/t-333288.html non-recursive

Answer 11

Si hay un soporte para sets (como los llama en el título) como incorporado generalmente hay un método de intersección.

De todos modos, como alguien dijo que podías hacerlo fácilmente (no voy a publicar el código, alguien ya lo hizo) si tienes las listas ordenadas. Si no puede usar la recursión, no hay problema. Hay implementaciones rápidas sin recursión .

Answer 12

Yo secundo la idea de "conjuntos". En JavaScript, puede usar la primera lista para completar un objeto, usando los elementos de la lista como nombres. Luego usa los elementos de la lista de la segunda lista y ve si esas propiedades existen.

Answer 13

con el conjunto 1 construir un árbol de búsqueda binaria con O(log n) e iterar set2 y buscar el BST m XO(log n) tan total O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

Answer 14

en C ++, se puede intentar con el mapa STL

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> 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;
}

Answer 15

sin hash, supongo que tienes dos opciones:

• La forma ingenua será comparar cada elemento con cualquier otro elemento. O (n ^ 2)
• Otra forma sería ordenar primero las listas, luego iterar sobre ellas: O (n lg n) * 2 + 2 * O (n)