Эффективность php array_intersect ()

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

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

Согласно (короткому, ненаучному) тесту, который я только что запустил, это похоже на array_intersect php:

Вот код, который я использовал для его проверки. Как вы можете видеть, для размера ввода, равного 1000, вам не нужно беспокоиться.

array_intersect сортирует массивы, прежде чем сравнивать их значения параллельно (см. использование zend_qsort в исходном файле array.c ). Это само по себе принимает O ( n · log n ) для каждого массива. Тогда фактическое пересечение принимает только линейное время.

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

 $index = array_flip($arrayOne); foreach ($arrayTwo as $value) { if (isset($index[$value])) unset($index[$value]); } foreach ($index as $value => $key) { unset($arrayOne[$key]); } var_dump($arrayOne); с $index = array_flip($arrayOne); foreach ($arrayTwo as $value) { if (isset($index[$value])) unset($index[$value]); } foreach ($index as $value => $key) { unset($arrayOne[$key]); } var_dump($arrayOne); 

Из того, что вы указали выше, я бы рекомендовал вам реализовать механизм кэширования. Таким образом, вы загрузите БД и ускорьте свое приложение. Я также рекомендую вам рассчитать скорость array_intersect с увеличением объема данных, чтобы увидеть, как масштабируется производительность. Вы можете сделать это, просто завернув вызов в вызовы системного времени и вычислив разницу. Но я бы рекомендовал использовать реальный профилировщик для получения хороших данных.

Я реализую этот простой код сравнения array_intersect и array_intersect_key,

 $array = array(); for( $i=0; $i<130000; $i++) $array[$i] = $i; for( $i=200000; $i<230000; $i++) $array[$i] = $i; for( $i=300000; $i<340000; $i++) $array[$i] = $i; $array2 = array(); for( $i=100000; $i<110000; $i++) $array2[$i] = $i; for( $i=90000; $i<100000; $i++) $array2[$i] = $i; for( $i=110000; $i<290000; $i++) $array2[$i] = $i; echo 'Intersect to arrays -> array1[' . count($array) . '] : array2[' . count($array2) . '] ' . '<br>'; echo date('Ymd H:i:s') . '<br>'; $time = time(); $array_r2 = array_intersect_key($array,$array2); echo 'Intercept key: ' . (time()-$time) . ' segs<br>'; $time = time(); $array_r = array_intersect($array,$array2); echo 'Intercept: ' . (time()-$time) . ' segs<br>'; 

результат….

 Intersect to arrays -> array1[200000] : array2[200000] 2014-10-30 08:52:52 Intercept key: 0 segs Intercept: 4 segs 

При этом сравнении эффективности между array_intersect и array_intersect_key мы можем видеть перехват с ключами намного быстрее.