Comments 21
Третья существенная оптимизация была связана с чтением данных. Этот этап занимал гораздо большее время, чем этапы построения графа и поиска пути в нём
Очень странно. Неужели в Интеле хотели провести соревнование на то, кто лучше напишет парсинг дат и собственный менеджер памяти? У других участников это тоже было узким местом?
Естественно, имелось в виду, что к этому времени алгоритм, занимающийся расчетом пути, уже был полностью переписан. Быстрый парсинг дат понадобился лишь после того, как алгоритм был сделан максимально эффективным.
Про других участников достоверно не знаю, но почти уверен, что чем более быстрым был придуманный ими алгоритм, тем больше времени пришлось потратить на оптимизацию его обвязки.
Про других участников достоверно не знаю, но почти уверен, что чем более быстрым был придуманный ими алгоритм, тем больше времени пришлось потратить на оптимизацию его обвязки.
А вы не пробовали вместо Дейкстры считать кратчайшие пути Левитом? Обычно он существенно быстрее.
Теоретически у него асимптотика хуже, и мы подумали, что пусть наш алгоритм будет работать приемлемо быстро на любом входе, а не чуть лучше в среднем — мало ли что будет в финальных тестах.
Мы хотели использовать parallel boost graph library, но оказалось что и самописная реализация неплохо работает. К тому же, поиск пути занимал примерно 5-10% от времени работы. Ещё 30-40% на построение графа, остальное — на чтение, но ускорить его ещё больше мы были бессильны. Гораздо больше мы выиграли, когда развернули цикл, перебирающий 25 пар типов вершин при добавлении рёбер в граф.
Мы хотели использовать parallel boost graph library, но оказалось что и самописная реализация неплохо работает. К тому же, поиск пути занимал примерно 5-10% от времени работы. Ещё 30-40% на построение графа, остальное — на чтение, но ускорить его ещё больше мы были бессильны. Гораздо больше мы выиграли, когда развернули цикл, перебирающий 25 пар типов вершин при добавлении рёбер в граф.
Я даже больше скажу (не имею к авторам никакого отношения): этот алгоритм в худшем случае работает за экспонинцеальное время. Это даже «чуть хуже» назвать нельзя.
Тоже учавствовали, заняли второе место. Много впечатлений, плохих — больше. Такое ощущение, что в интеле пытаются специально перемудрить с условием, чтобы выигрывали не хорошие алгоритмы, а хорошее распараллеливание. Кстати, задача-то NP-полная, если принимать все условия, но судя по всему, все забили на условие неповторения городов (я написал валящие тесты для почти всех решений, которые были выложены на форуме, в том числе решения победителя), хотя я дважды спрашивал у организаторов, можно ли на него забивать, и оба раза ответ был четкий — «нет, нельзя».
По поводу решения — мы использовали динамику, а не дейкстру, что дает немного лучшую асимптотику. А для пересчета времени не обязательно было писать свою функцию, просто не надо вызывать setenv каждый раз, и все будет быстро.
По поводу решения — мы использовали динамику, а не дейкстру, что дает немного лучшую асимптотику. А для пересчета времени не обязательно было писать свою функцию, просто не надо вызывать setenv каждый раз, и все будет быстро.
В прошлогоднем конкурсе условия были проще, и всё равно там был какой-то чит (связанный с предсказуемой генерацией будто бы случайных тестов), который позволил победить тем, кто это заметил. Так что это уже не первый раз такое. Тогда мы не участвовали, но в этот раз впечатления были действительно подпорчены.
А setenv мы в первую очередь вынесли наружу, но всё равно было достаточно медленно.
А setenv мы в первую очередь вынесли наружу, но всё равно было достаточно медленно.
Ну это касается не только условий. Например весной была русская поддержка, а в этот раз — нет. Проверяющий сервак был часто недоступен, а ожидание ответа от него по полчаса или дольше — вообще ни в какие ворота. Им явно есть чему поучиться у других конкурсов.
Но в общем, круто, что существуют такие конкурсы =)
Но в общем, круто, что существуют такие конкурсы =)
Так получилось, что вся «русская поддержка» внезапно перестала быть русской. И да, нам есть чему поучиться, что мы и пытаемся делать ;)
Спасибо за участие и интерес к конкурсу, а также за освещение темы на Хабре. Надеюсь, вас не обидели призами :)
Насколько я понял, вы участвовали в двух последних конкурсах — весной и осенью 2012. Если так, то вы можете сравнить, стало ли лучше?
Думаю, со временем у Интела выстроится определенная система для конкурсов и всё будет организованно лучше.
DmitryO, ты не собираешься переводить конкурсы на крупные уже существующие платформы?
Насколько я понял, вы участвовали в двух последних конкурсах — весной и осенью 2012. Если так, то вы можете сравнить, стало ли лучше?
Думаю, со временем у Интела выстроится определенная система для конкурсов и всё будет организованно лучше.
DmitryO, ты не собираешься переводить конкурсы на крупные уже существующие платформы?
о, rozboris, а я как раз собирался тебе ссылку послать :)
Мы тут проводили App Innovation Contest на codeproject.com. Это, конечно, совсем другой класс конкурсов — там все заточено на функционал и завершенность приложения, а не на оптимизацию алгоритма. Но опыт работы с крупными девелоперскими ресурсами неплохой.
Потом Terror тут пиарил еще один конкурс, по моим данным из России пришло много народу.
Если дойдут руки до алгоритмических конкурсов, будем думать :)
Мы тут проводили App Innovation Contest на codeproject.com. Это, конечно, совсем другой класс конкурсов — там все заточено на функционал и завершенность приложения, а не на оптимизацию алгоритма. Но опыт работы с крупными девелоперскими ресурсами неплохой.
Потом Terror тут пиарил еще один конкурс, по моим данным из России пришло много народу.
Если дойдут руки до алгоритмических конкурсов, будем думать :)
Да участвововал в двух последних, и надеюсь поучаствую в будущих. Сравнить адекватно не могу, ибо весной мы написали решение на коленке за один день (или около того), вообще не параллелили и послали просто «for fun». Но когда получилось 4 место по России, поняли, что надо было приложить чуть больше усилий, и во второй раз писали уже серьезно. Из того что помню — весной была русская поддержка, отчеты были подробнее и приходили на мыло (очень удобная фича), не было такого долгого ожидания сервера, условие читалось легче (хотя текстовое все равно не совпадало с реальным). А вот что стало лучше в последнем, припомнить не могу.
Насчет призов — ультрабуки это очень круто, но диагональ 11 дюймов совсем нерабочая (IMHO), надо хотя бы 13. Но тут уж грех жаловаться.
В общем и целом, если интел действительно разовьет это направление, я стану евангелистом =) Очень радуют подобные конкурсы для студентов, позволяют держать себя в тонусе. Да и новые технологии изучить можно (до конкурсов о параллельном программировании читал только статьи, ни разу сам не пробовал). Желаю всяческих успехов!
Насчет призов — ультрабуки это очень круто, но диагональ 11 дюймов совсем нерабочая (IMHO), надо хотя бы 13. Но тут уж грех жаловаться.
В общем и целом, если интел действительно разовьет это направление, я стану евангелистом =) Очень радуют подобные конкурсы для студентов, позволяют держать себя в тонусе. Да и новые технологии изучить можно (до конкурсов о параллельном программировании читал только статьи, ни разу сам не пробовал). Желаю всяческих успехов!
Ультрабуки крутые, подтверждаю:) 11 дюймов меня, конечно, поначалу тоже из колеи выбили… Всё мелкое, ещё и Full HD — вообще ничего не разглядеть. Но быстро снес без зазрения совести лицензионную винду, поставил убунту — и ненарадуюсь. Не знаю почему, но на ней как-то легче этот уровень dpi переносится. Для серьёзной работы всё равно бы подключал внешний монитор, даже если бы дюймов и было 13.
Поздравляю с третьим местом (лучше поздно чем никогда)!
Мне понравился ваш вывод — «никакого фанатизма для этого не требуется» ;)
Мне понравился ваш вывод — «никакого фанатизма для этого не требуется» ;)
Спасибо!
Про фанатизм — я в его отсутствии у нас стал полностью уверен, впечатлившись достижениями ассемблерных ребят;)
Про фанатизм — я в его отсутствии у нас стал полностью уверен, впечатлившись достижениями ассемблерных ребят;)
Тоже участвовали, заняли первое место :) Вообще да, заметно, что организаторы пытались дать неполиномиальную задачку, но в итоге все забили на некоторые случаи, и решали обычными дейкстрами или динамиками. Кстати, в отличие от некоторых, у нас было честное распараллеливание, правда, всего лишь на 4 потока.
Лично я участвую в третий раз, уже старожил. Весной 2012 вообще не было времени на этот конкурс, и поэтому сделали все тяп-ляп, даже отчета не написали вообще, профукали 25 баллов. В этот раз более серьезно отнеслись, почти весь месяц что-то делали, ну под конец больше тестировали и писали отчет, чем код :)
Ультрабуки, конечно, очень крутые, но 11 дюймов и FullHD — это жесть. Фильмы смотреть, конечно, здорово, но код — это же текст… Я ставил для работы 1600x900 или даже еще меньше. Все становится нормально видно, но картинка становится слегка размытой и непропорциональной :( и шрифты иногда как-то странно едут. Но вообще спасибо за них :)
А еще подобные конкурсы будут?
Лично я участвую в третий раз, уже старожил. Весной 2012 вообще не было времени на этот конкурс, и поэтому сделали все тяп-ляп, даже отчета не написали вообще, профукали 25 баллов. В этот раз более серьезно отнеслись, почти весь месяц что-то делали, ну под конец больше тестировали и писали отчет, чем код :)
Ультрабуки, конечно, очень крутые, но 11 дюймов и FullHD — это жесть. Фильмы смотреть, конечно, здорово, но код — это же текст… Я ставил для работы 1600x900 или даже еще меньше. Все становится нормально видно, но картинка становится слегка размытой и непропорциональной :( и шрифты иногда как-то странно едут. Но вообще спасибо за них :)
А еще подобные конкурсы будут?
Для решения проблемы высокого разрешения еще со времен XP есть в Винде такая штука, как масштаб:
ну про эту штуку я не знал :) спасибо
На самом деле штука отличная, только иногда (редко) возникают проблемы, если какое-то конкретное криво написанное приложение ее не поддерживает (да, разработчикам нужно потратить энное количество усилий, чтобы их приложение отображалось корректно при масштабе, отличном от стандартных 96 dpi). Микрософт даже кучу гайдлайнов в MSDN написал на тему адаптации приложений под high-resolution дисплеи, но ведь кто ж их читает?)
Sign up to leave a comment.
Рассказ об участии в конкурсе Intel Accelerate Your Code