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

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

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

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

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

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

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

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

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

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

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

sort($numbers2);

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

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

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

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

Я не эксперт по 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 чисел за секунду.

Остановись - зачем ты это делаешь?

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

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

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

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

Отсортируйте оба списка, затем просмотрите оба списка одновременно, используя шаблон последовательного обновления старого мастера нового мастера. Пока вы можете сортировать данные, это самый быстрый способ, так как вы действительно проходите по списку только один раз, до самой длинной части самого большого списка.

Ваш код просто сложнее, чем должен быть.

Предполагая, что вы ищете, чтобы числа в каждой позиции совпадали (а не только то, что массив содержит одинаковые числа), вы можете свести свой цикл к одному для.

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

?>

Используя приведенный выше код, вы будете выполнять цикл только 1000 раз, в отличие от цикла 1000000 раз.

Теперь, если вам нужно просто проверить, отображается или не отображается число в массивах, используйте array_diff и array_intersect следующим образом:

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

?>

Может быть, я чего-то здесь не вижу, но это похоже на классический случай пересечения множеств. Вот несколько строк на perl, которые сделают это.

Для каждого $e (@a, @b) {$объединение{$e}++&&$исект {$e}++}

@объединение = ключи %объединение; @isect = ключи %isect;

В конце этих строк кода @isect будет содержать все числа, которые находятся как в @a, так и в @b. Я уверен, что это можно перевести на php более или менее напрямую. ФУ, это мой любимый фрагмент кода из поваренная книга Perl.

Вы можете сделать это за O(n) времени, если используете сортировку по корзинам. Предполагая, что вы знаете максимальное значение, которое могут принимать числа (хотя есть способы обойти это).

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

Я думаю, что было бы намного проще использовать встроенную функцию array_intersect. Используя свой пример, вы могли бы сделать:

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

Лучшим способом было бы сделать что-то вроде этого:

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

Это гарантировано O(n) [при условии, что вставка поиска в хэш-карту является O(1) амортизированной].

Обновление: Наихудшим случаем этого алгоритма будет O(n²) и нет никакого способа уменьшить - если вы не измените семантику программы. Это потому, что в худшем случае программа вызовет doBla() n² количество раз, если все числа в обоих списках совпадают. Однако, если оба списки имеют уникальные номера (т.Е., Как правило, уникальные в списке), тогда среда выполнения будет стремиться к O(n).

Я создам графический интерфейс на Visual Basic, посмотрим, смогу ли я отслеживать цифры

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

Итак, в псевдокоде это будет выглядеть примерно так...

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

}

Если я прав, скорость этого алгоритма равна O(n logn).

Я не уверен, почему Mrk Mnl был отклонен, но вызов функции - это накладные расходы здесь.

Вытолкните совпадающие числа в другой массив и доБла() на них после сравнения. В качестве теста //out doBla() и посмотрите, испытываете ли вы ту же проблему с производительностью.

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

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

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

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

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

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

Этот код будет вызывать doBla() один раз при каждом обнаружении значения в $numbers1 в $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();
        }
    }
}

Если вам нужно позвонить 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(), вероятно, занимают больше времени, чем повторение массивы.

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

Объединение, сортировка и затем подсчет

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

Используйте WebAssembly вместо JavaScript.