Open Murlakotamus opened 6 years ago
Murlakotamus
commented
6 years ago Ссылки для покурить:
Murlakotamus
commented
6 years ago Ваня, пишу для тебя вводную. Общую структуру проекта, если интересно, можно найти в Вики проекта.
Есть класс Solver, который реализует полный перебор всех действий, которые можно совершить с фигурой в стакане и фигурами в прогнозе, то есть местами ему не впадлу обсчитать аж пять фигур и среди всех вариантов выбрать самый результативный, который далее и будет принят виртуальным игроком как руководство к действию.
Перебор вариантов - рекурсивный и идёт в один поток. Хотелось бы процесс перебора распараллелить, и первое, что приходит в голову, это запустить не один, а четыре потока, каждый на одно из положений начальной фигуры в стакане (одно начальное + три со сдвигом ещё на один, два и три кубика в сторону). Однако, это решение нестабильно, так как первый поток может отработать быстро (просто в силу конкретного комбинаторного решения первее прочих исчерпать доступные для него варианты), а остальные три продолжать работать - на лицо простаивание вычислительных ресурсов...
В процессе поиска решения, наиболее затратной по времени строчкой является
Несмотря на то, что внутри неё многое параллелится относительно легко, наиболее интересным атомом для распараллеливания оказывается она целиком... то есть всё, что стоит за processGlass() можно рассматривать как отдельную задачу, поручаемую некоему консьюмеру.
Технология форк/джоин осложнена тут, как минимум, тем (как мне кажется... гм, да, эти слова надо добавлять почти ко всему, что я тут пишу с таким уверенным видом), что в рекурсию нельзя уйти, не обсчитав отдельный этап virtualGlass.processGlass(), который может показать, что на данном варианте игра просто заканчивается... Вот пока как-то так.
Сейчас поиск решения идёт в один поток, в то время как поиск можно распараллелить, как минимум, в четыре раза. Кроме того, интуиция подсказывает, что полноценному распараллеливанию поддаётся поиск на любом своём этапе, вопрос только в том, чтобы понять, как это можно сделать правильно.