Форум Сайтостроение Веб-строительство

Пересечение 2 несортированных массивов за линейное время

12
mustafa
На сайте с 28.10.2005
Offline
202
mustafa
1716

Собственно, задача: пересечь 2 массива наиболее быстрым способом.

По науке:

1) сортируем массивы, 0(N*logN) - быстрая сортировка

2) пересекаем их за 0(N).

Время выполнения получается логарифмичным :(

Написал свой алгоритм пересекающий массивы за 0(N). Идея взята с "индексной" сортировки. 

function intersect($a, $b)

{

	if (count($b)>count($a))

		return intersect($b, $a); // $a должен быть больше $b

	$c=array(); // вспомогательный массив. В качестве индексов используются значения массивов $a и $b

	$d=array(); // результирующий массив

	$ta=count($a);

	$tb=count($b);

	for ($i=0; $i<$ta; $i++)

	{

		if (++$c[$a[$i]]==2)

			$d[]=$a[$i];

		if ($i<$tb && (++$c[$b[$i]]==2))

			$d[]=$b[$i];

	}

	return $d;

}

Полдня думал :) Сделал и решил поделиться с народом :) Может кому пригодится :)

p.s. предполагается, что значения массивов уникальны.

maximkuk
На сайте с 14.09.2005
Offline
72
maximkuk
#1

Так лучше не делать: for ($i=0; $i<count($a); $i++)

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

$count_a = count($a);

for ($i=0; $i<$count_a; $i++)

памяти на лишней переменной съест немного, зато отразится на производительности

Just another WordPress weblog (http://maxkuk.ru)
mustafa
На сайте с 28.10.2005
Offline
202
mustafa
#2
maximkuk:
Так лучше не делать: for ($i=0; $i<count($a); $i++)
т.к. при каждом шаге будет вычисляться размер массива, если массивы большие, то скажется на производительности, лучше сделать так:

:) RTFM :) Каждый раз не считается количество элементов :)

maximkuk
На сайте с 14.09.2005
Offline
72
maximkuk
#3
mustafa:
:) RTFM :) Каждый раз не считается количество элементов :)

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

mustafa
На сайте с 28.10.2005
Offline
202
mustafa
#4
maximkuk:
;) не уверен в PHP интерпретаторе, в си точно вычисляется каждый раз, касперский даже как-то статью на эту тему писал, об узких местах в коде.

сейчас проверим.

maximkuk
На сайте с 14.09.2005
Offline
72
maximkuk
#5

похоже я прав: http://www.php.net/manual/ru/function.count.php

NEVER USE IN CYCLES!
//size of $arr ~ 2000 elements

//wrong variant (Time exec ~ 19 sec)
for($i=0;$i<count($arr);$i++)
{
...
}

//right variant(Time exec ~ 0.2 sec)
$arr_size=count($arr);
for($i=0;$i<$arr_size;$i++)
{
...
}

it was discovered experimentally.
maximkuk
На сайте с 14.09.2005
Offline
72
maximkuk
#6

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

mustafa
На сайте с 28.10.2005
Offline
202
mustafa
#7

maximkuk, ага. Сейчас проверил у себя. Черт, а кто-то же говорил, что у пыха кэширование включено :) Обманули :)

maximkuk
На сайте с 14.09.2005
Offline
72
maximkuk
#8

кеширование здесь ни причём, см. /ru/forum/comment/2051170

mustafa
На сайте с 28.10.2005
Offline
202
mustafa
#9

maximkuk, да и пофигу :) зато работает в 5-6 раз быстрее стандартной array_intersect.

D
На сайте с 21.06.2006
Offline
168
Dash
#10

RTFM2: count не пересчитывает, а всего лишь читает внутреннюю переменную объекта типа Array. Но то, что читает ОЧЕНЬ ДОЛГО - это факт!

Можете проверить на маленьком и большом массиве - время будет одинаковое.

А чтобы с каунтом не заморачиваться, лучше использовать foreach.

ТС: а чем array_intersect не угодил?

Appstorespy - платформа анализа мобильных сторов | Publa.io - готовая инфраструктура для приема платежей и оплаты рекламных кабинетов в бурже
12

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий