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

Question

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

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

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

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

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

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

Answer 1

Эту проблему можно разбить на 2 задачи. 1-я задача - найти все комбинации (n ^ 2-n) / 2. Для n = 1000 решение x = 499500. Второе задание состоит в том, чтобы просмотреть все числа x и сравнить их с функцией 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 2

Этот код будет вызывать doBla() один раз за каждый раз, когда в $numbers2 будет найдено значение $numbers1:

// 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();
        }
    }
}

Если вам нужно только один раз вызвать doBla(), если совпадениенайдено:

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

Если $numbers1 и $numbers2 будут содержать только уникальные значения или если не важно, сколько раз встречается какое-либо конкретное значение в обоих массивах, array_intersect() выполнит работу:

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

Я согласен с несколькими предыдущими постами, что вызовы doBla(), вероятно, занимают больше времени, чем перебор массивов.

Answer 3

Слияние, сортировка и подсчет

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

Вывод / значения с количеством три - это те, которые вы хотите

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

Answer 4

Если вы пытаетесь получить список чисел без дубликатов, вы можете использовать хеш:

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

Это будет немного (очень немного) медленнее, чем метод обхода массива, но, на мой взгляд, он чище.

Answer 5

1. Создайте две дубликаты коллекций, предпочтительно с быстрым поиском, например HashSet или, возможно, TreeSet. Избегайте списков, так как они имеют очень плохое время поиска.

2. Когда вы найдете элементы, удалите их из обоих наборов. Это может сократить время поиска, поскольку в последующих поисках требуется меньше элементов для просеивания.

Answer 6

Можно ли поместить эти числа в две таблицы базы данных, а затем сделать INNER JOIN? Это будет очень эффективно и предоставит только цифры, которые содержатся в обеих таблицах. Это идеальное задание для базы данных.