Домашнее задание

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

Итак, задача, для начала простенькая. У нас есть 10000 человек, которые любят ходить по большому, каждый из них - ровно в одно и то же время каждый день, и сидят в сортире ровно по часу. Надо задать всем людям их время похода в сортир (с помощью генератора случайных чисел) и посчитать, какое минимальное количество толчков потребуется для того, чтоб никому не пришлось терпеть.

Конечно, сейчас набегут крутые программисты, которые скажут:
- А, ну так это ж алгоритм Шпрехензе-Дойча, который на PHP не реализуем в силу ущербности последнего, и вообще надо Кнута читать, писать на .NET и носить в кармане айфон!
Пускай :)

Так как я сам должен показывать пример разработчикам (как единственный из двух ведущих разработчиков, который согласился прокачаться и стать эльфом 80-го уровня с соответствующей зарплатой), то я тоже сделал это задание.

Первый вариант, который я набросал за 10 минут, имел два больших недостатка: во-первых, я предположил, что время квантуется по минутам, а, во-вторых, организовал вложенный цикл, увеличив общее число итераций до 600000.

$ php -d memtrack.enabled=1 -d memtrack.soft_limit=1K -d memtrack.vm_limit=1K hometask_01.php
483
0.54826402664185 sec
PHP Warning:  [memtrack] [pid 1842] virtual memory usage on shutdown: 2076672 bytes in Unknown on line 

Полсекунды - это очень дофига, но зато потребление памяти - почти как у пустого скрипта, там всего-то массив в 1440 элементов.

Потом я эти два недочёта убрал - квантование времени сделал по секундам и убрал вложенные циклы. Получилось примерно вот что:

$m = array(0 => 0, 3599 => 0);
for($i = 0; $i < 10000; $i++)
{
	$e = round(mt_rand(0, 86399));
	if(isset($m[$e]))
	{
		$m[$e]++;
	}
	else
	{
		$m[$e] = 1;
	}
	$e += 3600;
	if($e > 86400)
	{
		$e -= 86400;
		$m[0]++;
	}
	elseif($e == 86400)
	{
		$m[0]++;
		$m[3599]--;
	}
	if(isset($m[$e]) && $e)
	{
		$m[$e]--;
	}
	else
	{
		$m[$e] = -1;
	}
}
$s     = 0;
$max_s = 0;
for($i = 0; $i < 86400; $i++)
{
	if(isset($m[$i]))
	{
		$s += $m[$i];
		$max_s = max($max_s, $s);
	}
}
echo $max_s."\n";

$ php -d memtrack.enabled=1 -d memtrack.soft_limit=1K -d memtrack.vm_limit=1K hometask_01.php
475
0.048645973205566 sec
PHP Warning:  [memtrack] [pid 1846] user function main() executed in  on line 0 allocated 1835008 bytes in Unknown on line 0
PHP Warning:  [memtrack] [pid 1846] virtual memory usage on shutdown: 3911680 bytes in Unknown on line 0

Если сначала отсортировать массив $m, а потом перебирать его поэлементно, то это получится дольше примерно на 0.01 секунды и потребует памяти больше примерно на 800 Кб, поэтому я отказался от этой затеи.

Значение нужного количества сортиров колеблется в районе 460-480, хотя, как мне кажется, должно быть около 416,6, что наводит меня на мысль о том, что алгоритм Шпрехензе-Дойча реализован не совсем верно :(
Подумаю ещё немного.

А ещё blogger.com принялся втыкать дополнительные пустые строчки внутрь <pre>, нахрена? Дерьмо.