Блог пользователя oversolver

Автор oversolver, 10 лет назад, По-русски

Всем привет!
Многим известны соревнования Google Code Jam, Facebook Hackercup, IPSC, ch24, deadline24 и т.п. Их объединяет то, что в задаче даётся инпут с мультитестом внутри, на который нужно посчитать ответ у себя локально. Мне стало интересно, пользуетесь ли вы распараллеливанием? Современные машины позволяют дать ощутимый прирост, например, чтобы избежать таких ситуаций.

А прошедший deadline24 мы писали так


(само описание событий)

Я решил написать свой вариант шаблона, и вот что у меня получилось: code.
Вот ещё другой подход от kormyshov: code.

Кто может предложить другие варианты, желательно на с++? А может на других языках это делается проще? А может у кого-то есть инструменты, позволяющие параллелить инпут на несколько машин (кроме рук и флешки:)? Интересны любые ответы и замечания по теме.

  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

На Challenge24 мы распараллеливали так: http://pastie.org/10024847.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Для распараллеливания на несколько машин, можно воспрользоваться каким-нибудь фреймворком для распределённых вычислений, например для Java это Hadoop, Ignite и др. Для других языков можно поискать аналоги.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Hadoop всётаки это история не про то, она про map-reduce. У него специфика чуть другая.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Когда я последний раз пробовал использовать Hadoop для того чтобы параллелить задачи (в его версии для амазона) — там только инициализация мапредьюса занимала минут 5; так что для всяких facebook hacker cup'ов и gcj этот вариант категорически не подходит.

    Если же использовать своё железо — то гораздо эффективнее и дешевле запускать на одном мощном десктопе, а не на 5 слабых лаптопах.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Эм. Возможно ты неправильно настроил конфиг, хоть не знаю, не могу тут дискутировать. Я работал только с Ignite (точнее, когда он был ещё просто GridGain) и там нужно немного времени на запуск, хендшейки и прочие вещи, что занимает несколько секунд. Зато потом ты можешь не перезаускать запущенные ноды при переписывании кода, а просто создавать новые таски (в практически таком же api, как ты бы делал, используя ThreadPool, то есть фреймворк сам сериализует объект Callable и передаёт его на нужную ноду, которая запустит его и вернёт Future). То есть, я на самом деле думаю, что это вполне юзабельно. Будет время, займусь этим вопросом.

      UPD. Конечно, имея под боком мощный рабочий сервак, можно на нём запускать ;)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          А никто не пробовал на хадупе? Может шаблон какой-то есть для GCJ? А то я на работе бы позапускал, но самому все это писать неохота)

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Насколько я понимаю, эта задача разбивается на две: 1) написание конфига для нод 2) написание клиента (на самом деле, просто подключается библиотека и тоже нужна настройка)

            Примитивные шаблоны уверен, есть в сети. Более того, например у gridgain есть семплы прямо в пакете, может такое есть и у хадупа.

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Запускает (потенциально) в два потока: http://pastie.org/10024923

std::async() сам определяет, когда запускать новый поток, а когда вычислять в том же. Поэтому на каждый Case # можно сделать по async() и потом печатать ответы с помощью .get().

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Как я себе представляю(могу ошибаться), определение вычислять ли сразу, происходит в момент вызова async. Поэтому либо все будет в 1 поток, либо запустится сколько нужно потоков, а потом все остальное будет в одном, либо запустится все сразу в разных потоках.

    Кажется, что лучше либо форсировать создание потоков(можно и в самом async'е), либо делать что-то типа thread-poola

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

мой шаблон (с ошибкой в формате вывода :( )

чтобы распараллелилось, компилировать с -fopenmp. Кстати очень удобно завести проект cmake и написать там что-нибудь типа


set(CMAKE_CXX_FLAGS_RELEASE "-O3 -fopenmp") set(CMAKE_CXX_FLAGS_DEBUG "-g")

Тогда распараллелится только версия для релиза, а отлаживать код можно будет как обычно.

Только надо очень аккуратно использовать стандартную библиотеку, чтобы что-нибудь там не вызвало гонку или дедлок. Например, нельзя пользоваться функцией rand().

По поводу запуска на нескольких машинах. Например, можно поднять на каждой HTTP-сервер, который будет принимать запросы с данными, запускать обработчик, и возвращать его вывод. Все это очень просто пишется, есть куча библиотек и фреймворков на куче языков.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, так дебажить проще будет, спасибо. Но если, к примеру, нужно вырваться из распараллеленного цикла (грубо говоря, если ответ (не)нашелся где-то в процессе), то при дебаге компилятор не ругнется на break, а должен. Так что действительно нужно очень аккуратно следить за всем.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я когда-то писал такой код для распараллеливания на потоки по тестам, а не инпутам https://github.com/asiunov/utils/blob/master/MultithreadedSolution.java . Там всё, что нужно заполнить, находится сверху в тудушках. Немного запутанный код и стоило бы отрефакторить, но щас не буду этим заниматься.