php - postgre - ¿Cómo puedo comparar dos juegos de 1000 números uno contra el otro?

postgresql diferente a

Question

Debo verificar aproximadamente 1000 números contra otros 1000 números.

Cargué ambos y los comparé con el lado del servidor:

foreach( $numbers1 as $n1 ) {
foreach( $numbers2 as $n2 ) {
if( $n1 == $n2 ) {
doBla();
}
}
}

Esto llevó mucho tiempo, así que traté de hacer el mismo lado del cliente de comparación utilizando dos elementos div ocultos. Luego los comparó usando JavaScript. Todavía tarda 45 segundos en cargar la página (utilizando elementos div ocultos).

No necesito cargar los números que no son iguales.

¿Hay un algoritmo más rápido? Estoy pensando en comparar el lado de la base de datos y solo cargar los números de error, luego hacer una llamada Ajax para los números restantes sin error. Pero, ¿es una base de datos MySQL suficientemente rápida?

Answer 1

Fusionar, ordenar y luego contar

<?php
$first = array(''1001'', ''1002'', ''1003'', ''1004'', ''1005'');
$second = array(''1002'', ''1003'', ''1004'', ''1005'', ''1006'');
$merged = array_merge($first, $first, $second);
sort($merged);
print_r(array_count_values($merged));
?>

Salida / los valores con un conteo de tres son los que desea

Array
(
[1001] => 2
[1002] => 3
[1003] => 3
[1004] => 3
[1005] => 3
[1006] => 1
)

Answer 2

1. Cree dos colecciones duplicadas, preferiblemente aquellas con tiempos de búsqueda rápidos, como HashSet o quizás TreeSet. Evite las listas ya que tienen tiempos de búsqueda muy deficientes.

2. A medida que encuentre elementos, elimínelos de ambos conjuntos. Esto puede reducir los tiempos de búsqueda al tener menos elementos para examinar en búsquedas posteriores.

Answer 3

¿Sería posible poner estos números en dos tablas de bases de datos y luego hacer una INNER JOIN ? Esto será muy eficiente y solo proporcionará los números que están contenidos en ambas tablas. Esta es una tarea perfecta para una base de datos.

Answer 4

¿Tal vez solo intersecar los valores de la matriz para encontrar números existentes en ambas matrices?

$result = array_intersect($numbers1, $numbers2);
foreach ($result as $val)
doBla();

Answer 5

Crearé una interfaz GUI en Visual Basic, veré si puedo rastrear los números

Answer 6

Creo que sería mucho más fácil usar la función incorporada en array_intersect. Usando tu ejemplo, podrías hacer:

$results = array_intersect($numbers1, $numbers2);
foreach($results as $rk => $rv) {
doSomething($rv);
}

Answer 7

En términos de la base de datos esto puede unir de 1000 filas a otras 1000 filas. Cualquier sistema de base de datos moderno puede manejar esto.

select x from table1
inner join table2
on table1.x = table2.y

donde table1 y table2 son las filas afectadas y podrían ser la misma tabla.

Answer 8

Este código llamará a doBla() una vez por cada vez que se encuentre un valor en $numbers1 en $numbers2 :

// get [val => occurences, ...] for $numbers2
$counts = array_count_values($numbers2);
foreach ($numbers1 as $n1) {
// if $n1 occurs in $numbers2...
if (isset($counts[$n1])) {
// call doBla() once for each occurence
for ($i=0; $i < $counts[$n1]; $i++) {
doBla();
}
}
}

Si solo necesita llamar a doBla() una vez si se encuentra una coincidencia:

foreach ($numbers1 as $n1) {
if (in_array($n1, $numbers2))
doBla();
}

Si $numbers1 y $numbers2 solo contendrán valores únicos, o si el número de veces que un valor específico ocurre en ambas matrices no es importante, array_intersect() hará el trabajo:

$dups = array_intersect($numbers1, $numbers2);
foreach ($dups as $n)
doBla();

Estoy de acuerdo con varias publicaciones anteriores de que las llamadas a doBla() probablemente doBla() más tiempo que iterar sobre las matrices.

Answer 9

Este problema se puede dividir en 2 tareas. La primera tarea es encontrar todas las combinaciones (n ^ 2-n) / 2. Para n = 1000, la solución es x = 499500. La segunda tarea es recorrer todos los números x y compararlos con la función doBla ().

function getWayStr(curr) {
var nextAbove = -1;
for (var i = curr + 1; i < waypoints.length; ++i) {
if (nextAbove == -1) {
nextAbove = i;
} else {
wayStr.push(waypoints[i]);
wayStr.push(waypoints[curr]);
}
}
if (nextAbove != -1) {
wayStr.push(waypoints[nextAbove]);
getWayStr(nextAbove);
wayStr.push(waypoints[curr]);
}
}

Answer 10

Fusiona ambas listas, comienza al principio de ambas listas y luego busca en cada lista números similares al mismo tiempo.

Entonces, en pseudocódigo, sería algo así como ...

Mergesort (List A);
Mergesort (list B)
$Apos = 0;
$Bpos = 0;
while( $Apos != A.Length && $Bpos != B.length) // while you have not reached the end of either list
{
if (A[$Apos] == B[$Bpos])// found a match
doSomething();
else if (A[$Apos] > B[$Bpos]) // B is lower than A, so have B try and catch up to A.
$Bpos++;
else if (A[$Apos] < B[$Bpos]) // the value at A is less than the value at B, so increment B
$Apos++;
}

Si estoy en lo cierto, la velocidad de este algoritmo es O (n logn).

Answer 11

Lo que tienes no debe tomar tanto tiempo, ¿qué hace doBla ()? Sospecho que se está tomando el tiempo? Comparar dos juegos de 1000000 números con el mismo algoritmo no lleva mucho tiempo ...

Esto es hilarante, la cantidad de técnicas de optimización como respuestas, el problema no es su algoritmo, es lo que doBla () hace que tomar el tiempo en un factor muchas veces mayor que cualquier optimización lo ayudaría :) esp. dado que los sets tienen solo 1000 de largo y tienes que ordenarlos primero ...

Answer 12

No estoy seguro de por qué Mrk Mnl fue votado negativamente, pero la llamada a la función es la de arriba .

Elimine los números coincidentes en otra matriz y doBla () en ellos después de las comparaciones. Como una prueba // fuera doBla () y vea si está experimentando el mismo problema de rendimiento.

Answer 13

No soy un experto en PHP, por lo que puede necesitar alguna depuración, pero puede hacerlo fácilmente en el momento O (n):

// Load one array into a hashtable, keyed by the number: O(n).
$keys1 = [];
foreach($numbers1 as $n1) $keys1[$n1] = true;
// Find the intersections with the other array:
foreach($numbers2 as $n2) { // O(n)
if (isset($keys1[$n2]) { // O(1)
doBla();
}
}

De todos modos, la intersección no es hacia donde va tu tiempo. Incluso una mala implementación O (n ^ 2) como la que tiene ahora debería poder pasar por 1000 números en un segundo.

Answer 14

Ordena las listas primero. Luego puede subir las dos listas desde el principio, comparando a medida que avanza.

El ciclo se vería así:

var A = getFirstArray().sort(), B = getSecondArray().sort();
var i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] === B[j]) {
doBla(A[i]);
i++; j++;
}
else if (A[i] < B[j]) {
i++;
}
else
j++;
}

(Eso es JavaScript; podrías hacerlo también desde el servidor, pero no conozco PHP).

Editar - para ser justos con todos los fanáticos de las tablas de aciertos (a quienes respeto por supuesto), es bastante fácil hacerlo en JavaScript:

var map = {};
for (var i = 0; i < B.length; ++i) map[B[i]] = true; // Assume integers.
for (var i = 0; i < A.length; ++i) if (map[A[i]]) doBla(A[i]);

O si los números son o podrían ser flotantes:

var map = {};
for (var i = 0; i < B.length; ++i) map['''' + B[i]] = true; // Assume integers.
for (var i = 0; i < A.length; ++i) if (map['''' + A[i]]) doBla(A[i]);

Dado que los números son bastante baratos para el hash (incluso en JavaScript, la conversión a cadenas antes del hashing es sorprendentemente barato), esto sería bastante rápido.

Answer 15

Ordenarlos primero.

Answer 16

Ordene ambas listas, luego recorra ambas listas al mismo tiempo usando el patrón de actualización secuencial de maestros nuevos antiguos . Siempre que pueda ordenar los datos, es la manera más rápida, ya que realmente solo recorre la lista una vez, hasta la longitud más larga de la lista más grande.

Answer 17

Puedes hacerlo en el tiempo O (n) si usas el tipo de clasificación. Suponiendo que conozca el valor máximo que pueden tomar los números (aunque hay formas de evitarlo).

http://en.wikipedia.org/wiki/Bucket_sort

Answer 18

Quizás no estoy viendo algo aquí, pero parece un caso clásico de intersección fija. Aquí hay algunas líneas en Perl que lo harán.

foreach $ e (@a, @b) {$ union {$ e} ++ && $ isect {$ e} ++}

@union = keys% union; @isect = keys% isect;

Al final de estas líneas de código, @isect contendrá todos los números que están en @a y @b. Estoy seguro de que esto es traducible a php más o menos directamente. FWIW, esta es mi pieza favorita de código del Perl Cookbook.

Answer 19

Si clasifica list2 primero y luego realiza una búsqueda binaria para cada número en list1, verá un aumento de velocidad enorme.

No soy PHP, pero esto debería darte la idea:

sort($numbers2);
foreach($numbers1 as $n1)
{
if (BinarySearch($numbers2, $n1) >= 0) {
doBla();
}
}

Obviamente, al no ser un tipo de PHP, no conozco la biblioteca, pero estoy seguro de que la clasificación y la búsqueda binaria deberían ser fáciles de encontrar.

Nota: en caso de que no esté familiarizado con una búsqueda binaria; está ordenando list2 porque las búsquedas binarias deben operar en listas ordenadas.

Answer 20

Si intenta obtener una lista de números sin ningún duplicado, puede usar un hash:

$unique = array();
foreach ($list1 as $num) {
$unique[$num] = $num;
}
foreach ($list2 as $num) {
$unique[$num] = $num;
}
$unique = array_keys($unique);

Va a ser un poco (muy levemente) más lento que el método de paseo de la matriz, pero es más limpio en mi opinión.

Answer 21

Su código es simplemente más complicado que lo que necesita ser.

Asumiendo que lo que está buscando es que los números en cada posición coincidan (y no solo que la matriz contenga los mismos números), puede aplanar su bucle a una sola.

<?php
// Fill two arrays with random numbers as proof.
$first_array = array(1000);
$second_array = array(1000);
for($i=0; $i<1000; $i++) $first_array[$i] = rand(0, 1000);
for($i=0; $i<1000; $i++) $second_array[$i] = rand(0, 1000);
// The loop you care about.
for($i=0; $i<1000; $i++) if ($first_array[$i] != $second_array[$i]) echo "Error at $i: first_array was {$first_array[$i]}, second was {$second_array[$i]}<br>";
?>

Usando el código anterior, solo se repetirá 1000 veces, en lugar de repetir 1000000 veces.

Ahora, si solo necesita comprobar que aparece un número o no aparece en las matrices, use array_diff y array_intersect de la siguiente manera:

<?php
// Fill two arrays with random numbers as proof.
$first_array = array(1000);
$second_array = array(1000);
for($i=0; $i<1000; $i++) $first_array[$i] = rand(0, 1000);
for($i=0; $i<1000; $i++) $second_array[$i] = rand(0, 1000);
$matches = array_intersect($first_array, $second_array);
$differences = array_diff($first_array, $second_array);
?>

Answer 22

Una mejor manera sería hacer algo como esto:

// 1. Create a hash map from one of the lists.
var hm = { };
for (var i in list1) {
if (!hm[list1[i]]) {
hm[list1[i]] = 1;
} else { hm[list1[i]] += 1; }
}
// 2. Lookup each element in the other list.
for (var i in list2) {
if (hm[list2[i]] >= 1) {
for (var j = 0; j < hm[list2[i]]; ++j) {
doBla();
}
}
}

Esto está garantizado O (n) [suponiendo que la inserción de una búsqueda en un mapa hash es O (1) amortizado].

Actualización: el peor caso de este algoritmo sería O (n ² ) y no hay forma de reducirlo, a menos que cambie la semántica del programa. Esto se debe a que, en el peor de los casos, el programa llamará a doBla () n ² veces si todos los números en ambas listas son los mismos. Sin embargo, si ambas listas tienen números únicos (es decir, generalmente únicos dentro de una lista), entonces el tiempo de ejecución tenderá hacia O (n).

Answer 23

Use WebAssembly en lugar de JavaScript.

Answer 24

Detente , ¿por qué estás haciendo esto?

Si los números ya están en una base de datos SQL, haga una combinación y deje que el DB encuentre la ruta más eficiente.

Si no están en una base de datos, entonces apuesto a que se ha desviado de su camino y realmente debería reconsiderar cómo llegó aquí.

Answer 25

$same_numbers = array_intersect($numbers1, $$numbers2);
foreach($same_numbers as $n)
{
doBla();
}

Answer 26

• array_intersect() devuelve coincidencias
• array_diff() devuelve diffs