2010/1/10 Ruslan Zakirov <[email protected]>: > 2010/1/9 Alex Kapranoff <[email protected]>: >> Вроде простая совсем задачка: https://www.spoj.pl/problems/SUMITR/ >> >> А поди ж ты, на самом плохом тесткейсе в 2 секунды на довольно мощной >> машине уложить не могу :( > > Похоже и не получиться без улучшения производительности perl. > >> На Си хватает и половины секунды. В комментах пишут, что и Питон >> справляется. Хочет кто-нибудь поиграться? > > Куда играться-то? Лучше алгоритма чем Дейкстры не придумаешь для это задачки.
Базовый алгоритм остаётся, да, но всякие мелочи можно оптимизировать. У меня простейший оператор присваивания во внутреннем цикле занимает почти секунду :) Добрые перломонахи подсказали пару интересных идей: http://www.perlmonks.com/?node_id=816485 В частности, я тоже перешёл на твой вариант считать сверху вниз, а потом вывести максимум, чем срезал пару присваиваний. Ещё важным предложением оказалось считать сразу весь файл в плоский массив, а всю двухмерность рассчитывать по ходу дела индексами. Вот текущий вариант: http://ideone.com/np0UUaTO На плохом тесткейсе у меня на машине вместо 6 секунд работает всего 3.5 :) Проверку на spoj.pl, правда, всё равно не проходит. > У меня есть прямое, которое по ходу считает, а потом в нижнем ряду > находит максимум. Разница не значительная. > > В итоге в твоем решении тратиться: > 3 сек с копейками на split > 7 сек на ~5000000 сравнений и суммирований > 1.2 сек на вывод результата У меня, кстати, в профиле вывод вообще не виден. Проверь ещё разок.. > Вот такая математика. Пока 7 секунд не превратятся в 1, о каком-то > приближении к топу и быть не может. -- Moscow.pm mailing list [email protected] | http://moscow.pm.org
