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).

  • Combinar matrices con elementos comunes y múltiples puntos de datos
  • Javascript agrega text al comienzo de cada elemento de la matriz
  • ¿Por qué usar el operador unario + en una matriz da resultados inconsistentes en javascript?
  • ¿Qué significa _ en esta callback del filter?
  • Convierte Uint8Array a Array en Javascript
  • ¿Cómo encontrar el primer elemento de la matriz que coincida con una condición booleana en JavaScript?
  • ¿Cómo sumr elementos en el mismo índice en una matriz de matrices en una sola matriz?
  • ¿La mejor manera de consultar los valores de atributo únicos en una matriz de objects javascript?
  • ¿Cómo orderar una matriz asociativa por sus valores en Javascript?
  • ¿Cómo definir una matriz con elementos condicionales?
  • ¿Cómo funciona javascript foreach con matrices multidimensionales?
  • Todos los elementos de una matriz se actualizan en lugar de solo uno
  • cómo eliminar el object si todos los valores están vacíos en javascript?
  • Javascript tiene muchos buenos JS marco (como Node.js AngularJS Vue.js React.js) es el mejor lenguaje de script.