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

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

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

будет

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

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

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

Ответить

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

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

Ответить

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

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

Ответить

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

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. Нормуль, я считаю.

Ответить

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

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
';
		}
	}
}

Ответить