03 Авг 2012

PHP: быстрая проверка наличия значения в большом массиве

Постоянно встречается задача проверки наличия значения в массиве. В PHP для этих целей часто используют функцию in_array которая принимает два аргумента: искомое значение (или массив значений) и массив, в котором будет произведён поиск. Если значение найдено, функция возвращает true, в противном случае false.

Описание проблемы

Пока значений в массиве немного, то всё работает быстро. Но как только массив разрастается до 10 000 – 20 000 элементов, начинаются проблемы.

Один мой скрипт должен был проверять элементы на уникальность, сделать это средствами БД не получалось, т.к. массив после запроса к базе модифицировался пару раз. В массиве хранились только числовые id элементов (это пригодится для решения). В какой-то момент элементов стало больше 60 000 и скрипт стал работать по 20-30 с. на локальном хосте, что крайне медленно.

Простым замером времени исполнения участков кода (с помощью функции microtime()) что проблема именно в in_array.

Решение проблемы

Если подумать, то перебирать весь массив каждый раз чтобы проверить существование в нём элемента глупо. Гораздо проще проверить существование конкретного элемента массива, без перебора остальных значений. Для этого вместо массива вида ключ => значение(ID элемента) нужно использовать массив вида ключ(ID элемента) => какое-то значение (например true).

В таком случае для проверки существования элемента в массиве достаточно использовать функцию isset(), в которую следует передавать переменную вида $имя_массива[искомый ID элемента].

После перехода на такой способ проверки скрипт стал отрабатывать за 1.2 с, что вполне нормально.

Искренне Ваш К.О. =)

10 комментариев

Winrol 9 декабря 2012 18:49

А пример можете написать, потому что так не очень ясно.

Ответить

Морозов Максим 9 декабря 2012 21:23

Основная идея проста: поменять местами ключ и значение в ассоциативном массиве. Т.е. в коде вместо:

$array[] = 'значение';

будет

$array['значение'] = true;

Где вместо true может быть что угодно. В итоге чтобы проверить есть ли этот элемент в массиве, достаточно проверить определён ли искомый ключ:

if(isset($array['искомое значение'])){ echo 'Искомый элемент найден'; }

Ответить

Юра 27 декабря 2012 11:50

Результат для python:
>>> timeit.timeit(‘import random\narr = {}\nfor i in range(60000):\n val=random
.random()\n arr[random.random()]=val\n if i == 30000:\n valu=val\nfor k,v i
n arr.iteritems():\n if v == val:\n print True’, number=100)
4.579244164521924
>>>

коротенько поясню:
импортируем модуль random
создаём словарь вида arr[]=
и ключ и значение — float
на 30000 шаге запоминаем значение (чтобы было потом по чему проверять наличие значения)
и соответственно теперь проверяем есть ли среди 60000 значений искомое. Если есть выводим True
Запихиваем всё это в timeit и прогоняем сто раз для верности.
Выше показано время для ста итераций. То есть в среднем одна итерация проходит за
0.045 секунды.
Это на создание массива и поиска нужного ключа по значению

Ответить

Морозов Максим 27 декабря 2012 12:15

Ты не совсем понял суть написанного =) Я просто предлагаю проверять наличие ключа. А не перебирать каждый раз массив.

Но сейчас попробую повторить твой эксперимент.

Ответить

Тёма 27 декабря 2012 12:27

А можно написать простой однострочник

inArray = lambda arr, value: value in arr.itervalues()

Ответить

Морозов Максим 27 декабря 2012 12:42

Выполняем вот это:

set_time_limit(0); 

$time = 0;

for($i = 0; $i < 100; $i++){
	$time += findItemInRandomArray();
}

echo $time;

function findItemInRandomArray(){
	$startTime = microtime(true);
	
	for($i = 0; $i < 600000; $i++){
		$randomValue = rand();
		
		$array[rand()] = $randomValue;
		
		if($i == 30000){
			$storedValue = $randomValue;
		}
	}
	
	foreach($array as $value){
		if($value == $storedValue){
			echo 'true
';
		}
	}
	
	return (microtime(true) - $startTime);
}

Получаем эпичные 18.884446144104 секунд *CRAZY*

Ответить

Морозов Максим 27 декабря 2012 12:55

А если исправить ошибку и создавать только 60 000 элементов вместо 600 000, то получается нормуль — 2.09117436409. Вот только rand() возвращает целое. Я сейчас перепишу на float.

Ответить

Морозов Максим 27 декабря 2012 13:55

С float получаем 2.4262247085571. Нормуль, я считаю.

Ответить

Морозов Максим 27 декабря 2012 14:06

Окончательный вариант кода:

set_time_limit(0); 

$startTime = microtime(true);

for($i = 0; $i < 100; $i++){
	findItemInRandomArray();
}

echo (microtime(true) - $startTime);;

function findItemInRandomArray(){
	for($i = 0; $i < 60000; $i++){
		$randomValue = (float) rand();
		
		$array[(float) rand()] = $randomValue;
		
		if($i == 30000){
			$storedValue = $randomValue;
		}
	}
	
	foreach($array as $value){
		if($value == $storedValue){
			echo 'true
';
		}
	}
}

Ответить

Алексей 18 апреля 2018 8:29

Спасибо, ты гений)))

Ответить