Comment puis-je comparer deux séries de 1000 numéros l'une par rapport à l'autre ?

Question

Je dois vérifier environ 1000 numéros par rapport à 1000 autres numéros.

J'ai chargé les deux et les ai comparés côté serveur :

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

Cela a pris beaucoup de temps, alors j'ai essayé d'effectuer la même comparaison côté client en utilisant deux fichiers cachés. div éléments. Puis on les a comparés en utilisant JavaScript. Il faut toujours 45 secondes pour charger la page (en utilisant des éléments cachés). div éléments).

Je n'ai pas besoin de charger les chiffres qui ne sont pas les mêmes.

Existe-t-il un algorithme plus rapide ? Je pense les comparer dans la base de données et ne charger que les numéros d'erreur, puis faire un appel Ajax pour les autres numéros sans erreur. Mais une base de données MySQL est-elle assez rapide ?

Answer 1

Trier d'abord les listes. Ensuite, vous pouvez parcourir les deux listes depuis le début, en comparant au fur et à mesure.

La boucle ressemblerait à quelque chose comme ceci :

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

(C'est du JavaScript ; vous pourriez aussi le faire côté serveur, mais je ne connais pas le PHP).

Modifier - Pour être juste envers tous les fans de hashtable (que je respecte bien sûr), il est assez facile de faire cela 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]);

Ou si les chiffres sont ou pourraient être des flottants :

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]);

Étant donné que le hachage des nombres est assez bon marché (même en JavaScript, la conversion en chaîne de caractères avant le hachage est étonnamment bon marché), cette opération serait assez rapide.

Answer 2

• array_intersect() renvoie des correspondances
• array_diff() renvoie les différences

Answer 3

En termes de base de données, il s'agit d'une jointure de 1000 lignes à 1000 autres lignes. N'importe quel système de base de données moderne peut gérer cela.

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

donde table1 y table2 sont les lignes concernées et pourraient être la même table.

Answer 4

Ce que vous avez ne devrait pas prendre autant de temps - que fait doBla() ? Je pense que c'est ce qui prend le temps ? Comparer deux ensembles de 1000000 nombres avec le même algorithme ne prend pas de temps du tout

C'est hilarant - le nombre de techniques d'optimisation comme réponses - le problème n'est pas votre algorithme - c'est ce que doBla() fait qui prend le temps par un facteur beaucoup plus grand que n'importe quelle optimisation vous aiderait :) en particulier étant donné que les ensembles ne font que 1000 et que vous devez les trier en premier

Answer 5

Peut-être qu'il suffit de croiser les valeurs des tableaux pour trouver les nombres existant dans les deux tableaux ?

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