Javascript: compare eficientemente dos matrices de integers

Tengo dos matrices enteras que contienen valores numéricos. Quiero mirar a través de ambas lists y verificar si hay algo en común (o falta de) entre las lists. Es decir, quiero iterar a través de la (s) matriz (es) y encontrar esos elementos que aparecen en ambas lists, mientras que en una function separada quiero ir a través de las matrices y encontrar elementos que están en la primera y no en la segunda.

La forma obvia de hacer esto es anidada para loops:

var containedInFirst = false; for (var primaryID = 0; primaryID < PrimaryArray.length; primaryID++) { containedInFirst = false; for (var secondaryID = 0; secondaryID < SecondaryArray.length; secondaryID++) { if (PrimaryArray [primaryID] === SecondaryArray[secondaryID]) { containedInFirst = true; break; } } //Do some more stuff based on the value of containedInFirst here } 

Pero dado que las lists pueden contener cientos o miles de loggings, esto es bastante iterativo y consume mucho procesador. Por lo tanto, me preguntaba si existe una forma más eficiente de ejecutar el código anterior. No solo la búsqueda real, sino algo más eficiente que una matriz de integers como contenedor de los valores, o simplemente no usar loops nesteds para atravesar y comparar el contenido.

¿Alguna idea sobre soluciones más eficientes o elegantes?

6 Solutions collect form web for “Javascript: compare eficientemente dos matrices de integers”

Ordénelos primero y déjelos pasar en paralelo.

 a.sort(); b.sort(); left = []; both = []; right = []; i = 0; j = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) { left.push(a[i]); ++i; } else if (b[j] < a[i]) { right.push(b[j]); ++j; } else { both.push(a[i]); ++i; ++j; } } while (i < a.length) { left.push(a[i]); ++i; } while (j < b.length) { right.push(b[j]); ++j; } 

Todo el mundo está complicando demasiado esto. Aquí hay un trazador de líneas:

 var isEqual = (JSON.stringify(arr1.sort()) === JSON.stringify(arr2.sort())); 

Al usar dos loops nesteds, la complejidad será O (n * n). La orderación de ambas matrices se puede hacer en complejidad O (n log n).

AS Marcelo Cantos declaró pato-paleta 🙂 a través de ambos en paralelo tiene complejidad O (n) que conduce a una complejidad general de O (n log n) + O (n) que es O (n log n).

Creo que tengo una solución con eficiencia de O (N) (no es necesario ningún tipo), aquí está:

 var firstNotSecond; function CompareIntArrays(arr1, arr2) { firstNotSecond = new Array(); var arr3 = new Array(); //appear in both var arrTemp = new Array(); //used for firstNotSecond var usedNumbers = new Array(); for (var i = 0; i < arr1.length; i++) { var key = arr1[i]; usedNumbers[key] = true; arrTemp[key + ""] = true; } for (var i = 0; i < arr2.length; i++) { var key = arr2[i]; if (usedNumbers[key]) { arr3[arr3.length] = key; arrTemp[key] = false; } } for (var key in arrTemp) if (arrTemp[key]) firstNotSecond[firstNotSecond.length] = parseInt(key); return arr3; } 

La function devolverá una nueva matriz con los elementos que existen en ambas matrices y asignará una matriz global con todos los elementos existentes en la primera matriz que no existen en la segunda matriz.

Este código se basa en el hecho de que ambas matrices contienen solo numbers integers.

Ejemplo de uso:

 alert(CompareIntArrays([15, 551, 25, 910, 11], [25, 11, 785, 880, 15])); alert(firstNotSecond); 

Probado con matrices con 100.000 elementos: less de un segundo. Probado con arreglos que tienen 200,000 elementos cada uno: less de 2 segundos.

Otra posibilidad podría ser orderar esas matrices mientras las creas. No estoy seguro si puedes hacer eso. Pero si puede, boostá un poco la complejidad de agregar un elemento a la matriz (O (log n) en lugar de O (1)) pero disminuirá la complejidad de su algorithm de comparación a O (n)

Ordene ambas matrices, que el bucle solo una vez y compare:

 function diff(arrayToCompareTo, companetworkingArray) { Sort(arrayToCompareTo); Sort(companetworkingArray); var difference = [], same = []; for(var i = 0; i < arrayToCompareTo.length; ++i) { if (arrayToCompareTo[i] != companetworkingArray[i]) difference.push(companetworkingArray[i]); else same.push(companetworkingArray[i]); } if (companetworkingArray.length > arrayToCompareTo.length) for(var i = arrayToCompareTo.length; i < companetworkingArray.length; ++i) difference.push(companetworkingArray[i]); } 

Esto no se testing, así que si algo está mal, por favor avíseme.
De todos modos, esto debería orientarte en la dirección correcta ya que es O (N) en el mejor de los casos y O (M) en el peor de los casos companetworkingArray.length > arrayToCompareTo.length , es mucho más eficiente que O (N ^ 2). Tenga en count que la sorting toma O (N log N).

  • Compruebe si un elemento está presente en una matriz
  • array.length vs. array.length> 0
  • Mover el elemento de matriz al frente mediante la tecla de object
  • ¿Cómo acceder a un elemento de una matriz sin usar el indexador (javascript)?
  • ¿Cómo ordenar elementos de matriz por longitud latitud distancia en javascripts?
  • Eliminar objects de la matriz: dos enfoques diferentes, dos resultados diferentes al consultar la longitud de cada matriz
  • Javascript: dividir cadena en 2d matriz
  • JS cómo reformar este object irregular
  • Compruebe si 3 en una fila el valor de la matriz es el mismo
  • "Concat" no se une a las matrices de JavaScript juntas?
  • Cómo dividir una matriz grande en una matriz más pequeña en function de valores de índice dados,
  • Devuelve un elemento único que no tiene duplicates en una matriz
  • Javascript: ¿Cómo get la key padre dentro de una function?
  • Javascript tiene muchos buenos JS marco (como Node.js AngularJS Vue.js React.js) es el mejor lenguaje de script.