найти повторяющиеся число в большом в массиве

[SimbiX]

Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. Массив не отсортирован. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза, Нужно найти это число.

Вот написал так:

// Create array and shuffle him
$array = range(1, 1000000);
shuffle($array);


// Set the duplicate value
$array[mt_rand(1, 1000000)] = 40;

// Begin calculating
$begin = microtime(TRUE); 

$computed = array_count_values($array);
$number = array_search(max($computed), $computed);

$end = microtime(TRUE);

// Output
echo $number;
echo sprintf("\nExecution time: %.3f", $end - $begin);

На моей машине выполняется за 0,4 сек в среднем, интересует можно ли как-то сделать это быстрее ?

Спасибо за внимание

 

[флоппик]

интересует можно ли как-то сделать это быстрее ?

Конечно, просто на С перепиши.

 

[Adelf]

Значительно улучшить на php скорее всего не удастся. Стало интересно. Попробовал пару вещей. Чуть-чуть лучше результат показывает вот это.

$test = array_fill(1, 1000000, 0);
foreach($array as $val)
{
	if($test[$val] == 1) { $number = $val; break; }
	$test[$val] = 1;
}

Но, понятное дело, зависит от того как ляжет монета

 

[SimbiX]

флоппик
ну это задача более теоретическая, конечно я б не стал оперировать массивами в миллион значений в пхп, но вот нужно добиться хорошего результата на пхп

Adelf
какой-то уж очень рандомний вариант

 

[С.]

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

 

[С.]

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

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

 

[SimbiX]

С.
честно говоря не очень понял к чему Вы ведете

Эта задача с одного собеседование, на котором мне сказали что такую задачу можно решить намного эффективней чем предложений мною вариант, на пхп естественно, мне вот интересно как.

 

[Adelf]

SimbiX
Текст задачи точно такой? Я встречал похожую, там действительно есть хорошее решение.

 

[SimbiX]

Adelf

вот в оригинале:
Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. В этом массиве все числа уникальные, кроме одного числа, которое повторяется два раза. Найти это число. Решить эту задачу с минимальным использованием процессорного времени. Решить на PHP и выслать рабочий код.

 

[С.]

Ну если собеседование, то можно забить на мой коммент. Я про реальную жизнь говорил.

 

[Adelf]

http://www.sql.ru/forum/actualthread.aspx?bid=24&tid=875790 - вот здесь обсуждение хорошее.
Самый популярный вариант я и тут и опубликовал. Но в php это совсем не так быстро работает. Но, вполне возможно, с тебя этого и ожидали на собеседовании.

Вот здесь еще ответ другой:

Задачу можно решить за один проход. Для каждого числа в другом массиве создавать ключ, равный значению числа, но перед этим проверять - не существует ли уже такой ключ.Если существует, значит искомое число найдено.

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