ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Порождение перестановок, имеющих ограничения (with constraints)
9 сообщений из 9, страница 1 из 1
Порождение перестановок, имеющих ограничения (with constraints)
    #39745600
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Тема громкая, но трудная, и я не претендую на полный охват. Начало было положено вопросом DimaT в известном некоторым топике о том, как ускорить цикл
do{ ... }while( next_permuts(....)) .

Тема естественным образом распадается на 3 варианта:
1) не влезая внутрь next_permuts()
2) влезя или используя свою
3) для чего это нужно.

Вопрос оказался интересным,особенно (2-3). Я кратко напишу потом свои думки и что нарыл. Ну и кому есть что сказать по теме топика, тоже пишите, пожалуйста.

Чтоб увернуться от помидоров, прикладываю С++ исходник - как есть, т.е. с разной грязью.
Грязь в виде лишних переменных, закомеченных строк, иногда кривых комментариев, актуальных в VBA.
Т.к. прога берёт начало аж от VBS-скрипта, отлажена в эксэл-вба, и только потом переложена на Си.
Отсутствует Си-шная оптимизация. Есть некоторая алгоритмическая оптимизация.
Это только начало.

Особенности проги.
 
Компилилось в minGW 6.
В её ядре нет места "Classицизму".
Прога формирует перестановки, используя родной next_permuts(....), к-рый порождает их в лексикографической послед-сти.
Те из них, которые удовлетворяют заложенному ограничению, выводятся в stdout.
Ограничение= правильное расположение в задаче о ферзях. Сидит в отдельной процедуре CheckPermuts2().
Запускать ЕХЕ так: main3.exe [14] [<in1] [>true14]
- "14" - единственный используемый параметр в argv[], размерность задачи, по умолчанию переменная DLINA=4
- true14 - stdout
- in1 - stdin
На win64 время для 13 - 340сек, для 14 - 5000 сек, файл текстовый 24,3 Мб
Поскольку для 15 придётся время умножить на 15, а диск на ..., то ....

Небольшой тормоз представляет периодический сброс stdout на диск.
Регулируется макросом FLUSH2DISK= 0xffffff - каждые ХХ перестановок.
При долгой работе на диске файла долго не видно. Чтобы не накручивать показометр хода процесса, заставляю принудительно писать на диск.
Так я могу мониторить время, а в тоталкоммандере и открыть файл он-лайн.

Процедура, описанная в начале
void my_atexit() { /*Paused to look at results ...*/
имеет цель, указанную в комментарии: перед выходом остановиться и посмотреть конечный резалт. По ENTERу заканчивавем.
Если на stdin подать файл "in1" (любой, лучше пустой файл в текущем с ЕХЕ каталоге),то прога закончит без остановки в конце.

И, как отмечал, не удивляйтесь VBAшным "For-Step-Next" и т.д., а загляните в начало, где они описаны как макросы.

Продолжение последует, но не сразу.
...
Рейтинг: 0 / 0
10.12.2018, 19:47
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39745623
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
exp98,

а зачем отделять ограничения от процесса генерации?
...
Рейтинг: 0 / 0
10.12.2018, 20:29
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39745919
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!
...
Рейтинг: 0 / 0
11.12.2018, 12:34
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39748116
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Возможно я повторяю кого-либо.
Кзалось бы как ускорить перебор, не меняя функцию?
Но если нужна только их часть, обладающая общим свойством, то можно.
Имелось желание свести построение N-перестановок к декартовому поизведению К-перестановок, где К меньше N. Как писал выше, типа (Pn)=(Pn-k) х (Pk) и (Pk) - с нужными свойствами.

Это не означает рекурсивные вызовы.
- готовится (Pk) при n=k с той лишь разницей, что значения не в [1-k], а в [1-n]. И это не перестановки,а размещения (An,k). И они имеют заданное свойство в своей части
- затем каждая из них склеивается с (Pn-k) и проверяется на свойство.

Я просто посмотрел это на проге из начаала темы для к=3 и 4. Небольшая обвёртка, даже заведомо неоптимаизированная дал прибавку. Ускорение понятно, что за счёт сокращения общего кол-ва. Время работы ~ объёму перебора.
Было
13 - 340сек, для 14 - 5000 сек,
Стало
13 - 130сек, для 14 - 2000 сек
Нууу, 15 предположительно за ночь прогонится.

Непонятно, имеет ли смысл дробить мельче, чем k= n/2 ?
В случае свойства = "расстановка фишек" ?
В случае подбора пароля ?
...
Рейтинг: 0 / 0
14.12.2018, 18:40
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39748642
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
exp98Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!

Почему вас не устраивает классический перебор с возвратом? Или существующие подходы к решению constraint satisfaction problem, где уже в постановке задачи вводят ограничения на каждую переменную
...
Рейтинг: 0 / 0
16.12.2018, 17:34
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39748700
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Потому что Вы про пункт (2), а я про п.(1) - т.е. не влезая внутрь готовой функции.
И потом, разве плохой метод ускорения? И я не настаиваю, что знаю всё на свете. И просто интерсно сравнить.

Хотел немного оправдаться. Выше я сравнивал варианты (Pn-k)x(An,k) при k=4, к тому же записью в файл.
Сравнил для k=5, без печати:
Код: plaintext
1.
2.
3.
4.
5.
6.
12/5, w/o print, time= 0.390001 s, Total= 84934080, 218 m/c
13/5, w/o print, time= 5.694010 s, Total= 1253952000, 220 m/c
14/5, w/o print, time= 88.311755 s, Total= 19620195840, 222 m/c

12/0, w/o print, time= 2.308804 s, Total= 479001600,  207.5 m/c
13/0, w/o print, time= 29,858453 s, Total= 6227020800, 208.5 m/c
14/0, w/o print, time= 414.898329 s, Total= 87178291200, 210 m/c

12,13,14 - размерность n
12/5 при k=5
12/0 при k=0,т.е. для (Pn)
Total - длина перебора
m/c - вычисленная производительность млн/сек
...
Рейтинг: 0 / 0
16.12.2018, 20:45
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39783762
Мудроглюков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Мудроглюков
Участник
exp98Мне кажется, что это может пригодиться в реальных задачах.
В данном случае - для использования конкретного встроенного и "вылизанного" генератора в исследовательских целях.

Забегая вперёд: если нужен не N!, то использовать варианты вроде (А) х (В) х(С),
где В/C/или оба имеют нужные свойства, а ||A|| = N!

Так использование ограничений в процессе генерации и позволяет сократить перебор (в общем виде это называется "метод ветвей и границ"),
НО в каждой задаче свои ограничения - вот и нужен не столько встроенны генератор,
сколько общий фрейм генератора, чтобы на разных этапах формирования очередного варианта была возможность добавлять ограничения, отсекающие непригодные варианты.
...
Рейтинг: 0 / 0
07.03.2019, 20:52
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39783765
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Я тоже думалл, что нужен (типа qsort). Почему-то его не видно - это раз. А так получилось проверить идею "квазибэктрекинга".
Второе - вопрос тогда, что будет быстрее работать: бэктрекинг, заточенный под задачу или этот универсальный? или тот, встроенный, или квази. Если "под задачу", то очевидно, что его самому реализовывать.
...
Рейтинг: 0 / 0
07.03.2019, 21:07
| Ответить | Цитировать | Написать  
Порождение перестановок, имеющих ограничения (with constraints)
    #39783771
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Чесгря успел забыть про тему, увы.
Я почитал про сплетение групп и полугрупп, как раз чтобы получать заданные св-ва либо, или если другими методами, то для реализации быстро вычисляемыми операциями.
Но за 3 подхода не смог полностью уяснить, что я делал - это тоже сплетение или нет. И огорчило, что не нашёл более детальных разработок про это.
...
Рейтинг: 0 / 0
07.03.2019, 21:31
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Порождение перестановок, имеющих ограничения (with constraints)
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39748116&tid=1339983]:
 0ms
get settings:
 11ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 176ms
get topic data:
 10ms
get forum data:
 3ms
get page messages:
 53ms
get tp. blocked users:
 1ms
others: 241ms
total:  516ms
созд. / загр.: 516ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]