Меню
Что нового?

Что бысрей: array_search или array_key_exists?

trofim

Новичок
Что бысрей: array_search или array_key_exists?

Встретилась задача. Не сам придумал :)
Пусть есть набор из 100 тысяч слов (словарь). Программа на PHP получает на вход некоторый текст и проверяет, содержится ли очередное слово текста в словаре или нет. Сравните две версии программы и выберите наиболее быструю, ответ объясните.

(a) /* чтение словаря в память, затраты на этот этап не оцениваются, $a – очередное слово из словаря */
PHP: 
...
$dictionary[] = $a;
...

/* основной цикл работы программы, $word – очередное слово текста */
while (...)
{
	if (array_search($word, $dictionary) === false)
		echo «Not found»;
	else
		echo «Found»;
}
(b) /* чтение словаря в память, затраты на этот этап не оцениваются, $a – очередное слово из словаря */
PHP: 
...
$dictionary[$a] = 1;
...

/* основной цикл работы программы, $word – очередное слово текста */
while (...)
{
	if (!array_key_exists($word, $dictionary))
		echo «Not found»;
	else
		echo «Found»;
}
Поскольку имхо в PHP нет разницы между индексными и ассоциативными массивами, то мне кажется, что нет и никакой разницы в поиске ключа\значения. Т.е. первый и второй пример по скорости работы равнозначны.
Хоть я и не смог найти реализацию функций array_key_exists и array_search. Может там и есть какие-то принципиальные различия. Есть другие мнения?
 

trofim

Новичок
Повторяю, задача для меня никакой практической ценности не имеет. Просто встретилась в одном тесте.
Сравнить, конечно, я могу. Только как ответить на вопрос "почему?". А именно он и интересует. Хочу все знать! :)
 
Фанат

Фанат

oncle terrible
Команда форума
Хочешь - знай.
А мы - то здесь при чём?
что за манера - удовлетворять любопытство за чужой счёт?

Если тебе интересно - ты и ищи. Найдёшь - нам расскажешь

-~{}~ 08.11.06 16:45:

не смог найти реализацию функций array_key_exists и array_search
Нажмите для раскрытия...
ты хочешь, чтобы это кто-то сделал за тебя?
 
Shturm

Shturm

Гигант мысли
trofim
Подумай, что быстрее - прошерстить весь массив на предмет наличия в нем данного значения, или определить наличие в нем данного ключа?
 

hermit_refined

Отшельник
(b) В первом случае имеем поиск по списку - O(N), во втором - по хеш-таблице - O(1).

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

itprog

Cruftsman
кстати говоря, array_key_exists чуть ли не в три раза медленнее isset
 

camka

не самка
itprog
isset возвращает false, если значиние искомого элеманта массива есть NULL, то есть, сравнивать isset и array_key_exists не совсем правильно.
 

newARTix

Новичок
Автор оригинала: camka
itprog
isset возвращает false, если значиние искомого элеманта массива есть NULL, то есть, сравнивать isset и array_key_exists не совсем правильно.
Нажмите для раскрытия...
Да, сравнивать функции имеет смысл только для конкретной задачи.
Например стоит задача: обновление каталога товаров в БД.

При этом перебирается массив товаров и проверяется есть ли такой уже в базе, если есть, то он обновляется, если нет, то он добавляется. Товаров допустим около 10000. Конечно, делать каждый раз запрос в базу, мягко говоря неоптимально, поэтому имеет смысл загрузить массив уникальных идентификаторов товаров в массив поиска и просто проверять вхождения в него. Но как именно формировать этот массив и каким способом осуществлять поиск... конечно чисто интуитивно быстрее должен работать индексированный массив, но захотелось проверить практикой...

PHP: 
ini_set('max_execution_time',180);

// массив в котором будет осуществляться поиск по значениям
$array_values = array();
// индексированный массив, поиск по ключам
$array_keys = array();
// строка, поиск по вхождению
$string = '';
// массив значений которые будут искаться
$search = array();

for($i=0;$i<10000;$i++) {
	
	$value = rand(0,999)*rand(0,999);
	$value = md5($value);
	$array_values[] = $value;
	//$array_keys[$value] = $value;
	$string .= $value.',';
	if(rand(0,1)) $search[] = $value;
	
}


// время затраченное на формирование массива из while($row)
$t = microtime(true);
$tmp = $array_values;
$array_values = array();
foreach($tmp AS $value) {
	$array_values[] = $value;
}
echo 'примерное время затраченное на формирование массива из while($row=$db->fetch()): '.(microtime(true)-$t).'с<br />';


// время затраченное на формирование массива из GROUP_CONCAT
$t = microtime(true);
$array_values = explode(',',$string);
echo 'время затраченное на формирование массива из explode(GROUP_CONCAT string): '.(microtime(true)-$t).'с<br />';


// время затраченное на индексирование массива foreach
$t = microtime(true);
foreach($array_values AS $value) {
	$array_keys[$value] = $value;
}
echo 'время затраченное на индексирование массива foreach: '.(microtime(true)-$t).'с<br />';


$array_keys = array();
// время затраченное на индексирование массива array_combine
$t = microtime(true);
$array_keys = array_combine($array_values,$array_values);
echo 'время затраченное на индексирование массива array_combine: '.(microtime(true)-$t).'с<br />';


// поиск по значениям in_array()
$t = microtime(true);
foreach($search AS $value) {
	in_array($value,$array_values);
}
echo 'поиск по значениям in_array(): '.(microtime(true)-$t).'с<br />';


// поиск по значениям array_search()
$t = microtime(true);
foreach($search AS $value) {
	array_search($value,$array_values);
}
echo 'поиск по значениям array_search(): '.(microtime(true)-$t).'с<br />';


// поиск по ключам isset()
$t = microtime(true);
foreach($search AS $value) {
	isset($array_keys[$value]);
}
echo 'поиск по ключам isset(): '.(microtime(true)-$t).'с<br />';


// поиска по ключам empty()
$t = microtime(true);
foreach($search AS $value) {
	empty($array_keys[$value]);
}
echo 'поиск по ключам empty(): '.(microtime(true)-$t).'с<br />';


// поиск по ключам array_key_exists()
$t = microtime(true);
foreach($search AS $value) {
	array_key_exists($array_keys[$value]);
}
echo 'поиск по ключам array_key_exists(): '.(microtime(true)-$t).'с<br />';


// поиск в строке strstr
$t = microtime(true);
foreach($search AS $value) {
	strstr($string,$value);
}
echo 'поиск в строке strstr: '.(microtime(true)-$t).'с<br />';


// поиск в строке strpos
$t = microtime(true);
foreach($search AS $value) {
	strpos($string,$value);
}
echo 'поиск в строке strpos: '.(microtime(true)-$t).'с<br />';
 

newARTix

Новичок
dimagolov
нет :) к своему стыду я просто про него не знал :) Спасибо, что осадил, а то я бы еще научил кого-нибудь... :)
хотя опять же мало ли какие извращения могут быть... вдруг поле по которому надо проверять не является уникальным с точки зрения хранения данных, а является логическим ключом только в процессе импорта.
С другой стороны в теме речь не про БД, а про поиск в массиве :) Просто решил убедиться в итак очевидных вещах :)
 
Войдите или зарегистрируйтесь для ответа.
Сверху