Всем привет!
Многим известны соревнования Google Code Jam, Facebook Hackercup, IPSC, ch24, deadline24 и т.п. Их объединяет то, что в задаче даётся инпут с мультитестом внутри, на который нужно посчитать ответ у себя локально. Мне стало интересно, пользуетесь ли вы распараллеливанием? Современные машины позволяют дать ощутимый прирост, например, чтобы избежать таких ситуаций.
А прошедший deadline24 мы писали так
Я решил написать свой вариант шаблона, и вот что у меня получилось: code.
Вот ещё другой подход от kormyshov: code.
Кто может предложить другие варианты, желательно на с++? А может на других языках это делается проще? А может у кого-то есть инструменты, позволяющие параллелить инпут на несколько машин (кроме рук и флешки:)? Интересны любые ответы и замечания по теме.
На Challenge24 мы распараллеливали так: http://pastie.org/10024847.
Для распараллеливания на несколько машин, можно воспрользоваться каким-нибудь фреймворком для распределённых вычислений, например для Java это Hadoop, Ignite и др. Для других языков можно поискать аналоги.
Hadoop всётаки это история не про то, она про map-reduce. У него специфика чуть другая.
Ну так ты же можешь сделать split по тестам :)
Когда я последний раз пробовал использовать Hadoop для того чтобы параллелить задачи (в его версии для амазона) — там только инициализация мапредьюса занимала минут 5; так что для всяких facebook hacker cup'ов и gcj этот вариант категорически не подходит.
Если же использовать своё железо — то гораздо эффективнее и дешевле запускать на одном мощном десктопе, а не на 5 слабых лаптопах.
Эм. Возможно ты неправильно настроил конфиг, хоть не знаю, не могу тут дискутировать. Я работал только с Ignite (точнее, когда он был ещё просто GridGain) и там нужно немного времени на запуск, хендшейки и прочие вещи, что занимает несколько секунд. Зато потом ты можешь не перезаускать запущенные ноды при переписывании кода, а просто создавать новые таски (в практически таком же api, как ты бы делал, используя ThreadPool, то есть фреймворк сам сериализует объект Callable и передаёт его на нужную ноду, которая запустит его и вернёт Future). То есть, я на самом деле думаю, что это вполне юзабельно. Будет время, займусь этим вопросом.
UPD. Конечно, имея под боком мощный рабочий сервак, можно на нём запускать ;)
Хендшейки это мелочь, в случае с мапредьюсом на амазоне там же куча виртуалок с нуля инициализируется, думаю, в этом и боттл-нек (а держать их постоянно запущенными — пожалуй дороговато).
А никто не пробовал на хадупе? Может шаблон какой-то есть для GCJ? А то я на работе бы позапускал, но самому все это писать неохота)
Насколько я понимаю, эта задача разбивается на две: 1) написание конфига для нод 2) написание клиента (на самом деле, просто подключается библиотека и тоже нужна настройка)
Примитивные шаблоны уверен, есть в сети. Более того, например у gridgain есть семплы прямо в пакете, может такое есть и у хадупа.
Запускает (потенциально) в два потока: http://pastie.org/10024923
std::async()сам определяет, когда запускать новый поток, а когда вычислять в том же. Поэтому на каждыйCase #можно сделать поasync()и потом печатать ответы с помощью.get().Как я себе представляю(могу ошибаться), определение вычислять ли сразу, происходит в момент вызова async. Поэтому либо все будет в 1 поток, либо запустится сколько нужно потоков, а потом все остальное будет в одном, либо запустится все сразу в разных потоках.
Кажется, что лучше либо форсировать создание потоков(можно и в самом async'е), либо делать что-то типа thread-poola
мой шаблон (с ошибкой в формате вывода :( )
чтобы распараллелилось, компилировать с
-fopenmp. Кстати очень удобно завести проект cmake и написать там что-нибудь типаТогда распараллелится только версия для релиза, а отлаживать код можно будет как обычно.
Только надо очень аккуратно использовать стандартную библиотеку, чтобы что-нибудь там не вызвало гонку или дедлок. Например, нельзя пользоваться функцией
rand().По поводу запуска на нескольких машинах. Например, можно поднять на каждой HTTP-сервер, который будет принимать запросы с данными, запускать обработчик, и возвращать его вывод. Все это очень просто пишется, есть куча библиотек и фреймворков на куче языков.
Да, так дебажить проще будет, спасибо. Но если, к примеру, нужно вырваться из распараллеленного цикла (грубо говоря, если ответ (не)нашелся где-то в процессе), то при дебаге компилятор не ругнется на break, а должен. Так что действительно нужно очень аккуратно следить за всем.
Я когда-то писал такой код для распараллеливания на потоки по тестам, а не инпутам https://github.com/asiunov/utils/blob/master/MultithreadedSolution.java . Там всё, что нужно заполнить, находится сверху в тудушках. Немного запутанный код и стоило бы отрефакторить, но щас не буду этим заниматься.