Algoritmo para saber si dos matrices tienen miembros idénticos

Question

¿Cuál es el mejor algoritmo para comparar dos matrices para ver si tienen los mismos miembros?

Suponga que no hay duplicados, los miembros pueden estar en cualquier orden y ninguno está ordenado.

compare(
    [a, b, c, d], 
    [b, a, d, c] 
) ==> true 

compare(
    [a, b, e], 
    [a, b, c] 
) ==> false 

compare(
    [a, b, c], 
    [a, b] 
) ==> false 

Answer 1

respuestas obvias serían:

1. Ordenar ambas listas, a continuación, comprobar cada elemento para ver si son idénticos
2. añadir los elementos de una matriz a una tabla hash , a continuación, iterar a través de la otra matriz, comprobando que cada elemento está en el hash
iterativo algoritmo de búsqueda de
3. nickf

Cuál usarías dependerá de si primero puedes ordenar las listas y si tienes un buen algoritmo hash a mano.

Answer 2

Lo mejor que puedo pensar es O (n^2), supongo.

function compare($foo, $bar) { 
    if (count($foo) != count($bar)) return false; 

    foreach ($foo as $f) { 
     foreach ($bar as $b) { 
      if ($f == $b) { 
       // $f exists in $bar, skip to the next $foo 
       continue 2; 
      } 
     } 
     return false; 
    } 
    return true; 
} 

Answer 3

Puede cargar uno en una tabla hash, manteniendo un registro de cuántos elementos tiene. Luego, revise el segundo para verificar si cada uno de sus elementos está en la tabla hash y cuente cuántos elementos tiene. Si cada elemento en la segunda matriz está en la tabla hash, y las dos longitudes coinciden, son las mismas, de lo contrario no lo son. Esto debería ser O (N).

Para que esto funcione en presencia de duplicados, realice un seguimiento de cuántos elementos se han visto. Incremente al hacer un bucle sobre la primera matriz y disminuya mientras se repite la segunda matriz. Durante el ciclo sobre la segunda matriz, si no puede encontrar algo en la tabla hash, o si el contador ya está en cero, son desiguales. También compare los recuentos totales.

Otro método que funcionaría en presencia de duplicados es ordenar ambas matrices y hacer una comparación lineal. Esto debería ser O (N * log (N)).

Answer 4

Yo sugeriría usar un tipo primero y ordenar los dos primero. Luego, comparará el primer elemento de cada matriz, luego el segundo y así sucesivamente.

Si encuentra una discrepancia, puede detenerla.

Answer 5

Si ordena las dos matrices primero, obtendría O (N log (N)).

Answer 6

La mejor manera es probablemente usar hashmaps. Dado que la inserción en un hashmap es O (1), la construcción de un hashmap a partir de un array debería tomar O (n). Luego tiene n búsquedas, que cada una toma O (1), por lo que otra operación O (n). En general, es O (n).

en Python:

def comparray(a, b): 
    sa = set(a) 
    return len(sa)==len(b) and all(el in sa for el in b) 

Answer 7

ignorando el construido en maneras de hacer esto en C#, se podría hacer algo como esto:

Su O (1) en el mejor de los casos, O (N) (por lista) en el peor de los casos.

public bool MatchArrays(object[] array1, object[] array2) 
{ 
    if (array1.length != array2.length) 
     return false; 

    bool retValue = true; 

    HashTable ht = new HashTable(); 

    for (int i = 0; i < array1.length; i++) 
    { 
     ht.Add(array1[i]); 
    } 

    for (int i = 0; i < array2.length; i++) 
    { 
     if (ht.Contains(array2[i]) 
     { 
     retValue = false; 
     break; 
     } 
    } 

    return retValue; 
} 

Answer 8

asumiendo que no quiere molestar a las matrices originales y el espacio es una consideración, otra solución O (n.log (n)) que utiliza menos espacio que la clasificación de ambas matrices es:

1. Devuelve FALSE si matrices difieren en tamaño
2. Ordenar la primera matriz - O (n.log) (n) tiempo, el espacio extra que se requiere es el tamaño de una matriz
3. Para cada elemento de la segunda matriz, comprobar si está en la copia ordenada de la primera matriz usando una búsqueda binaria - O (n.log (n)) time

Si utiliza este enfoque, utilice una rutina de biblioteca para realizar la búsqueda binaria. La búsqueda binaria sorprendentemente es propensa a errores en el código de la mano.

[Añadido después de revisar las soluciones que sugiere búsquedas de diccionario/set/picadillo:]

En la práctica que haría uso de un hash. Varias personas han afirmado el comportamiento O (1) para hash, lo que les lleva a concluir que una solución basada en hash es O (N). Las inserciones/búsquedas típicas pueden estar cerca de O (1), y algunos esquemas de hashing garantizan la búsqueda O (1) en el peor de los casos, pero la inserción en el peor de los casos - al construir el hash - no es O (1). Dada cualquier estructura de datos hash particular, habría algún conjunto de entradas que produciría un comportamiento patológico. Sospecho que existen estructuras de datos hash con el peor caso combinado para [insertar-N-elementos y luego buscar-N-elementos] de O (N.log (N)) de tiempo y O (N) espacio.

Answer 9

Cuál es la "mejor" solución, obviamente, depende de las restricciones que tenga. Si se trata de un pequeño conjunto de datos, la comparación de clasificación, hashing o fuerza bruta (como nickf publicado) será bastante similar. Como sabe que está tratando con valores enteros, puede obtener O (n) ordenar los tiempos (por ejemplo, clasificación de raíz), y la tabla de dispersión también usará el tiempo O (n). Como siempre, existen inconvenientes en cada enfoque: la ordenación requerirá que duplique los datos o clasifique destructivamente su matriz (perdiendo el orden actual) si desea ahorrar espacio. Una tabla hash obviamente tendrá sobrecarga de memoria para crear la tabla hash. Si usa el método de nickf, puede hacerlo con una sobrecarga de memoria pequeña o nula, pero tiene que tratar con el tiempo de ejecución O (n). Puedes elegir cuál es la mejor para tus propósitos.

Answer 10

El ir en aguas profundas aquí, pero:

listas ordenadas clasificación puede ser O(nlogn) como se ha señalado. solo para aclarar, no importa que haya dos listas, porque: O(2*nlogn) == O(nlogn), luego comparar cada elemento es otro O (n), por lo que ordenar ambos y luego comparar cada elemento es O (n) + O (nlogn) que es: O(nlogn)

tablas hash: la conversión de la primera lista a una tabla hash es O (n) para la lectura + el coste de almacenar en la tabla hash, que supongo que puede ser estimada como O (n) , da O (n). Luego tendrá que verificar la existencia de cada elemento en la otra lista en la tabla hash producida, que es (¿al menos?) O (n) (suponiendo que la comprobación de la existencia de un elemento la tabla hash es constante). Con todo, terminamos con O(n) para el control.

La interfaz de lista de Java defines equals como cada elemento correspondiente es igual.

Curiosamente, la definición de interfaz almost discourages implementing the equals() función de Java Collection.

Por último, el Java Set interface per documentation implements este mismo comportamiento. La implementación debe ser muy eficiente, pero la documentación no menciona el rendimiento. (No se pudo encontrar un enlace a la fuente, es probable que tenga una licencia estricta. Descárgala y mírala tú mismo. Viene con el JDK) Al observar la fuente, el HashSet (que es una implementación comúnmente utilizada de Set) delega a los iguales() implementación en AbstractSet, que usa la función containsAll() de AbstractCollection usando de nuevo la función contains() desde hashSet. Entonces HashSet.equals() se ejecuta en O (n) como se esperaba. (Bucle a través de todos los elementos y mirando hacia arriba en un tiempo constante en la tabla hash.)

favor de edición si usted sabe mejor que me sobra el embarrasment.

Answer 11

En caso de colisión, un hashmap es O (n) en la mayoría de los casos porque utiliza una lista vinculada para almacenar las colisiones. Sin embargo, hay mejores enfoques y casi no deberías tener colisiones de todos modos porque si lo hicieras, el hashmap sería inútil. En todos los casos regulares es simplemente O (1). Además de eso, no es probable que tenga más de un pequeño n de colisiones en un hashmap único, por lo que el rendimiento no sería tan malo; puede decir con seguridad que es O (1) o casi O (1) porque la n es tan pequeña que puede ignorarse.

Answer 12

Esto se puede hacer de diferentes maneras:

1 - La fuerza bruta: para cada elemento de matriz1 comprobar existe ese elemento en matriz2. Tenga en cuenta que esto requeriría tener en cuenta la posición/índice para que los duplicados se puedan manejar correctamente. Esto requiere O (n^2) con la cantidad de código complicado, ni siquiera pensar en ello en absoluto ...

2 - Clasificar las dos listas, a continuación, comprobar cada elemento para ver si son idénticos. O (n log n) para ordenar y O (n) para verificar, básicamente, O (n log n), la ordenación se puede realizar in situ si el desorden de las matrices no es un problema, si no es necesario tener 2n de memoria de tamaño para copiar la lista ordenada

3 - Agregue los elementos y el recuento de una matriz a una tabla hash, luego itere a través de la otra matriz, verificando que cada elemento se encuentre en la tabla hash y en ese caso recuento de decrementos si no es cero; de lo contrario, quítelo de hashtable. O (n) para crear una tabla hash, y O (n) para comprobar los otros elementos de la matriz en la tabla hash, por lo O (n). Esto introduce una tabla hash con memoria como máximo para n elementos.

4 - Best of Best (Entre los anteriores): Restar o tomar diferencia de cada elemento en el mismo índice de las dos matrices y finalmente resumir los valores subtacted. Por ejemplo, A1 = {1,2,3}, A2 = {3,1,2} el Diff = {- 2,1,1} ahora resume el Diff = 0, lo que significa que tienen el mismo conjunto de enteros. Este enfoque requiere un O (n) sin memoria adicional. Un código C# vería como la siguiente:

public static bool ArrayEqual(int[] list1, int[] list2) 
    { 
     if (list1 == null || list2 == null) 
     { 
      throw new Exception("Invalid input"); 
     } 

     if (list1.Length != list2.Length) 
     { 
      return false; 
     } 

     int diff = 0; 

     for (int i = 0; i < list1.Length; i++) 
     { 
      diff += list1[i] - list2[i]; 
     } 

     return (diff == 0); 
    } 

4 no funciona en absoluto, es el peor

Answer 13

Puede utilizar una firma (una operación conmutativa lo largo de los miembros de la matriz) para optimizar aún más este en el caso en que la matriz generalmente sea diferente, guarde el o(n log n) o la asignación de memoria. Una firma puede tener la forma de un filtro (s) de floración, o incluso una operación conmutativa simple como "suma" o "xor".

Un ejemplo sencillo (suponiendo un largo como el lado firma y GetHashCode como un buen identificador de objeto; si los objetos son, por ejemplo, enteros, entonces su valor es una mejor identificador; y algunas firmas será mayor que de longitud)

public bool MatchArrays(object[] array1, object[] array2) 
{ 
    if (array1.length != array2.length) 
     return false; 
    long signature1 = 0; 
    long signature2 = 0; 
    for (i=0;i<array1.length;i++) { 
     signature1=CommutativeOperation(signature1,array1[i].getHashCode()); 
     signature2=CommutativeOperation(signature2,array2[i].getHashCode()); 
    } 

    if (signature1 != signature2) 
     return false; 

    return MatchArraysTheLongWay(array1, array2); 
} 

donde (mediante una operación de suma, el uso de una operación conmutativa diferente si se desea, por ejemplo, la floración filtros)

public long CommutativeOperation(long oldValue, long newElement) { 
    return oldValue + newElement; 
} 

Answer 14

Aquí es otra opción, que me haga saber lo que ustedes think.It debería ser T (n) = 2n * log2n -> O (nLogn) en el peor de los casos.

private boolean compare(List listA, List listB){ 
    if (listA.size()==0||listA.size()==0) return true; 
    List runner = new ArrayList(); 
    List maxList = listA.size()>listB.size()?listA:listB; 
    List minList = listA.size()>listB.size()?listB:listA; 
    int macthes = 0; 
    List nextList = null;; 
    int maxLength = maxList.size(); 
    for(int i=0;i<maxLength;i++){ 
     for (int j=0;j<2;j++) { 
      nextList = (nextList==null)?maxList:(maxList==nextList)?minList:maList; 
      if (i<= nextList.size()) { 
       MatchingItem nextItem =new MatchingItem(nextList.get(i),nextList) 
       int position = runner.indexOf(nextItem); 
       if (position <0){ 
        runner.add(nextItem); 
       }else{ 
        MatchingItem itemInBag = runner.get(position); 
        if (itemInBag.getList != nextList) matches++; 
        runner.remove(position); 
       } 
      } 
     } 
    } 
    return maxLength==macthes; 
} 

public Class MatchingItem{ 
private Object item; 
private List itemList; 
public MatchingItem(Object item,List itemList){ 
    this.item=item 
    this.itemList = itemList 
} 
public boolean equals(object other){ 
    MatchingItem otheritem = (MatchingItem)other; 
    return otheritem.item.equals(this.item) and otheritem.itemlist!=this.itemlist 
} 

public Object getItem(){ return this.item} 
public Object getList(){ return this.itemList} 

}

Answer 15

Pseudocódigo:

A:array 
B:array 
C:hashtable 

if A.length != B.length then return false; 

foreach objA in A 
{ 
H = objA; 
if H is not found in C.Keys then 
C.add(H as key,1 as initial value); 
else 
C.Val[H as key]++; 
} 

foreach objB in B 
{ 
H = objB; 
if H is not found in C.Keys then 
return false; 
else 
C.Val[H as key]--; 
} 

if(C contains non-zero value) 
return false; 
else 
return true; 

Answer 16

Si los elementos de una matriz se dan como distinta, a continuación, XOR (XOR bit a bit) todos los elementos tanto de las matrices, si la respuesta es cero, entonces ambas matrices tienen el mismo conjunto de números. La complejidad del tiempo es O (n)