tec matrices lineal algorithm

algorithm - lineal - Algoritmo para saber si dos matrices tienen miembros idénticos



algebra lineal tec (16)

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

Supongamos 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

Puede usar una firma (una operación conmutativa sobre los miembros de la matriz) para optimizar aún más esto en el caso en que la matriz sea generalmente diferente, guardando 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 simple (suponiendo que el lado de la firma y gethashcode sean un buen identificador de objeto, si los objetos son, por ejemplo, enteros, entonces su valor es un mejor identificador, y algunas firmas serán más largas que largas)

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 (usando una operación de suma, use una operación conmutativa diferente si lo desea, p. ej. filtros de floración)

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

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 el n es tan pequeño que puede ignorarse.

Haciendo caso omiso de las formas integradas de hacer esto en C #, podrías 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; }

Ir a aguas profundas aquí, pero:

La clasificación ordenada de listas puede ser O(nlogn) como se indicó. 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)

Hash-tables: convertir la primera lista en una tabla hash es O (n) para leer + el costo de almacenamiento en la tabla hash, que supongo que se puede estimar como O (n), da O (n). Luego deberá 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 la Lista de Java define iguales ya que cada elemento correspondiente es igual.

Curiosamente, la definición de la interfaz de Java Collection casi desalienta la implementación de la función equals () .

Finalmente, la interfaz del conjunto de Java por documentación implementa 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. (recorriendo todos los elementos y buscándolos en tiempo constante en la tabla hash).

Por favor edita si sabes mejor para evitarme la vergüenza.

La mejor forma 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)

Las respuestas obvias serían:

  1. Ordene ambas listas, luego verifique cada elemento para ver si son idénticas
  2. Agregue los elementos de una matriz a una tabla hash, luego itere a través de la otra matriz, verificando que cada elemento esté en la almohadilla
  3. algoritmo de búsqueda iterativa de nickf

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

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; }

Puede cargar uno en una tabla hash, haciendo un seguimiento 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)).

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

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

Si encuentras un desajuste, puedes parar.

Esto se puede hacer de diferentes maneras:

1 - Fuerza bruta: para cada elemento en la matriz1, compruebe que ese elemento existe en la 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 un código muy complicado, ni siquiera lo pienses en absoluto ...

2 - Ordene ambas listas, luego verifique cada elemento para ver si son idénticas. 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 repita la otra matriz, verificando que cada elemento esté en la tabla hash y en ese caso recuento de decrementos si no es cero, de lo contrario elimínelo 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 - Lo mejor de lo mejor (Entre los anteriores): reste o tome la diferencia de cada elemento en el mismo índice de las dos matrices y, finalmente, resuma los valores a los que se ha hecho una subsección. 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 # se vería así:

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

Aquí hay otra opción, háganme saber lo que piensan. 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}

}

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;

Suponiendo que no desee alterar las matrices originales y el espacio es una consideración, otra solución O (n.log (n)) que utiliza menos espacio que la ordenación de ambas matrices es:

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

Si usa 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.

[Agregado después de revisar soluciones que sugieren búsquedas de diccionario / conjunto / hash:]

En la práctica, usaría 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.

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

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, hash o fuerza bruta (como la publicación de nickf ) será bastante similar. Como sabe que está tratando con valores enteros, puede obtener O (n) ordenar los tiempos (p. Ej. Ordenar por radix), y la tabla hash 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 lidiar con el tiempo de ejecución de O (n 2 ). Puedes elegir cuál es la mejor para tus propósitos.