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

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

Всем привет! Я вот тут решил немного поэкспериментировать с шаблонным метапрограммированием в С++. Начал с простого, а именно со старых добрых симпатичных узоров. В результате получилась следующая реализация.

Она даже быстро компилируется при N·M ≤ 30 и работает, например, при N = 5 и M = 100 (при больших никак, ибо максимальная глубина инстанцирования в GNU — 900). Она правильно считает, но у меня возникло несколько вопросов. Дело в том, что инстанцирование шаблона metaFor происходит для всех значений m, mask и cur_mask. Так вот этот самый cur_mask по сути просто счетчик цикла, не входящий в состояние динамики. Можно ли как-то убрать его из параметров шаблона, сохранив возможность итерирования с помощью него? Тогда можно было бы считать динамику при значительно больших N и M. Второй вопрос заключается в том, а можно ли как-то ускорить данную реализацию?

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

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

У меня был тот же вопрос..

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

Извините за копание в старой теме и ответ, не относящийся к вопросу
Имею мнение, что задачу можно решить перебором. Всего состояний (правильных и неправильных) при n*m = 30 равно 2^30, т.е. состояния раскладываются в двоичное число. Генерация состояний последовательная, с "подскоками", т.е. каждый сектор начиная с первого должен подставить единичку внизу справа, если есть одни нули, (либо сбросить единицы, если их четыре, и опять поставить единицу одну, не забывая прибавить к другому разряду, избегая зацикливания), не ожидая 100500 генераций в других секторах...
А код напоминает китайские иероглифы) Магия

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

    2^30 итераций = 10 секунд работы. Или Вы хотите тесты заифить?

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

      Смотря где. На моей машине итерации обходятся в меньшее время, сервера codeforces выдерживают все в 890 миллисекунд. Проверок требуется максимум 20 на итерацию. Еще конечно подсчет идет не тупо от 0 до 2^30, а с учетом того, чтобы получить, например, правильную первую ячейку 2х2, не надо лопатить остальные 20 ячеек, если все четыре поля заполнены единицами, то делаем "сброс" без бездумного переллпачивания, и так далее. И тесты я никогда не ифил, не надо :) Чем больше времени сэкономлено работающим и нехитрым решением, тем лучше будет)

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

        А, если перебор с отсечениями, тогда меньше времени конечно)