Как я могу сравнить два набора из 1000 чисел друг против друга?

Question

Я должен проверить примерно 1000 номеров против 1000 других номеров.

Я загрузил оба и сравнил их на стороне сервера:

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

Это заняло много времени, поэтому я попытался сделать то же самое на стороне клиента, используя два скрытых div элементов. Затем сравнил их, используя JavaScript. Загрузка страницы все еще занимает 45 секунд (с использованием скрытых div элементов).

Мне не нужно загружать числа, которые не совпадают.

Есть ли более быстрый алгоритм? Я подумываю сравнить их на стороне базы данных и просто загрузить номера ошибок, а затем выполнить Ajax-вызов для оставшихся номеров ошибок. Но достаточно ли быстро работает база данных MySQL?

Answer 1

Сначала отсортируйте списки. Затем вы можете просмотреть оба списка с самого начала, сравнивая их по ходу.

Цикл будет выглядеть примерно так:

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

(Это JavaScript; вы могли бы сделать это и на стороне сервера, но я не знаю PHP.)

Изменить & mdash; просто чтобы быть справедливым по отношению ко всем фанатам хэширования (которых я, конечно, уважаю), это довольно легко сделать в 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]);

Или, если числа являются или могут быть числами с плавающей точкой:

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

Поскольку числа довольно дешевы для хэширования (даже в JavaScript преобразование в строку до хэширования удивительно дешево), это будет довольно быстро.

Answer 2

• array_intersect() возвращает совпадения
• array_diff() возвращает различия

Answer 3

В терминах базы данных это может объединять 1000 строк в 1000 строк. Любая современная система баз данных может справиться с этим.

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

, где table1 и table2 - соответствующие строки и могут быть одной и той же таблицей.

Answer 4

Что у вас не должно быть так долго - что делает doBla ()? Я подозреваю, что это занимает время? Сравнение двух наборов 1000000 чисел с одним и тем же алгоритмом совсем не требует времени ..

Это забавно - количество методов оптимизации в качестве ответов - проблема не в вашем алгоритме, а в том, что делает doBla (), что занимает время во много раз больше, чем любая оптимизация, поможет вам :) esp. учитывая, что наборы имеют длину только 1000, и вы должны сначала отсортировать их ..

Answer 5

Может быть, просто пересечь значения массива, чтобы найти числа, существующие в обоих массивах?

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

Answer 6

Если вы сначала отсортируете list2, а затем выполните бинарный поиск для каждого числа в списке1, вы увидите значительное увеличение скорости.

Я , а не парень из PHP, но этодолжен дать вам идею:

sort($numbers2);

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

Очевидно, что я не парень PHP, я не знаю библиотеку, но я уверен, что сортировка и бинарный поиск должны быть достаточно простыми для поиска.

Примечание: Если вы не знакомы с бинарным поиском;Вы сортируете list2, потому что бинарный поиск должен работать с отсортированными списками.

Answer 7

Сначала отсортируйте их.

Answer 8

Стоп - зачем вы это делаете?

Если числа уже есть в базе данных SQL, выполните объединение и дайте БД определить наиболее эффективный маршрут.

Если их нет в базе данных, то держу пари, что вы куда-то сошли с пути и действительно должны пересмотреть, как вы попали сюда.

Answer 9

Я не эксперт по PHP, поэтому для этого может потребоваться некоторая отладка, но вы можете легко сделать это за 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();
  }
}

Несмотря на это, пересечение не там, где уходит ваше время. Даже плохая реализация O (n ^ 2), как у вас сейчас, должна быть в состоянии пройти 1000 номеров в секунду.

Answer 10

$same_numbers = array_intersect($numbers1, $$numbers2);

foreach($same_numbers as $n)
{
  doBla();
}