Нет, сортировка там может быть совсем не проблемой в контексте задачи. Просто немного неаккуратно написать тут, чуть не оптимально в другом месте, чуть хуже ассимптотику для сортировки выбрать и всё: под нагрузкой (такой как у Яндекса или Мейлру) имеем в кластере для этого сервиса больше железа, чем могло быть, если бы писал человек, который в таких вопросах себя чувствует свободно. А железо — это деньги. А зачем платить больше, когда расходы можно предотвратить ещё на этапе собеседования? :-)
Какова алгоритмическая сложность наилучшего и наихудшего возможного алгоритма сортировки массива из N элементов? (Наихудшая сложность – O(N^2), потому что нужно сравнить каждый с каждым, наилучшая – O(N * ln(N)). Почему такая наилучшая? Не помню. Читал в книжке. В какой — не помню).
Вы упоминали Мейл и Яндекс. Так вот незнание таких базовых вещей разработчиком вполне может обернуться дополнительным железом, которое придется поставить под ваш код и которое стоит существенных денег. А разница может быть всего лишь в том, чтобы заюзать стандартный sort или написать в нужном месте нормальный sort, который работает за O(N) вместо O(NlogN).
Не каждый готов сорваться и уехать на другой конец планеты. Но если есть потребность в решении сложных и полезных задач дома, пишите мне — ivan.gorbachev@odnoklassniki.ru :-)
>> Итого 200^2*1000*100, это 4 миллиарда итераций, по большей части записи в память.
А зачем для каждой пары (муравей, цель) запускать отдельный поиск в ширину? Можно просто запустить поиск в ширину от каждого муравья, после чего мы получим кратчайшие пути до каждой клетки поля (в том числе и до всех целей). В итоге получится около 40 млн. операций, что уже в 500мс укладывается.
Не хочу показаться не скромным, но наш hovercraft на этом видео всех очень сильно обыграл. :) А в целом забавнейшее мероприятие. Невероятно интересно не только писать тактику для своего персонажа, но и потом болеть за него на итоговом соревновании.
«Но этот алгоритм медленнее, время его работы, особенно в сильно «густых» графах, лежит в O(V4)»
Меня смутила эта фраза. Я подумал, что Вы говорите именно о Форд-Беллмане. Вы же имели в виду ещё просчёт для всех вершин, т.е. O(v^4) в целом. :)
Кстати, да. Я, когда в первый раз собирал систему, ничего не понял в handbook (опыта работы с linux у меня не было). Но тщательно следовал всему, что там написано. И ничего, получилось, система заработала. Поэтому низкий поклон авторам хендбука за столь качественную работу. :)
Мне интересно, а автор тестировал приложение под Linux? Мне не удалось заставить работать под Gentoo. Хотя по этому поводу стоит пообщаться лично с автором…
Действительно. Странные ребята, строят себе датацентры, а всего лишь десятью баксами можно было бы обойтись :-)
Складывается ощущение, что мы говорим о компаниях и задачах абсолютно разного масштаба.
Вы упоминали Мейл и Яндекс. Так вот незнание таких базовых вещей разработчиком вполне может обернуться дополнительным железом, которое придется поставить под ваш код и которое стоит существенных денег. А разница может быть всего лишь в том, чтобы заюзать стандартный sort или написать в нужном месте нормальный sort, который работает за O(N) вместо O(NlogN).
А зачем для каждой пары (муравей, цель) запускать отдельный поиск в ширину? Можно просто запустить поиск в ширину от каждого муравья, после чего мы получим кратчайшие пути до каждой клетки поля (в том числе и до всех целей). В итоге получится около 40 млн. операций, что уже в 500мс укладывается.
Меня смутила эта фраза. Я подумал, что Вы говорите именно о Форд-Беллмане. Вы же имели в виду ещё просчёт для всех вершин, т.е. O(v^4) в целом. :)
2. Алгоритм Форда-Беллмана работает за O(V*E), а не O(V^4).