2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5
 
 Re: Sokoban: оптимальные решения
Сообщение01.12.2021, 13:07 
Аватара пользователя


26/05/12
1534
приходит весна?
zykov в сообщении #1541131 писал(а):
B@R5uk в сообщении #1541097 писал(а):
что скорость работы определяется временем доступа к оперативной памяти,
Да, скорее всего там не в процессоре bottle neck, а в памяти. Поэтому видимо на сервере и работало быстрее, т.к. там была быстрая серверная память.

При программировании на Java есть ещё одна заковыристая проблема быстродействия, связанная со сборщиком мусора. Например, в моём последнем брутфорсере объекты создаются и уничтожаются сотнями тысяч в секунду. По мере накопления отработанных данных вызывается GC, и это хорошо видно на графике производительности (при решении упомянутого в теме чуть ранее пазла):

Изображение

Низкие горизонтальные плато как раз соответствуют моментам удаления мусора. Не смотря на то, что сам процесс удаления не самый рациональный (сборщик мусора должен перебрать все зарегистрированные в Java-окружении объекты и определить на которые из них нет ссылок из используемых в программе объектов), проблема не в самой сборке мусора. Проблема заключается в том, как ведёт себя программа, активно создающая и уничтожающая объекты, когда память Java-окружения подходит к концу. Заканчивается она, разумеется, потому, что созданных и ещё используемых в программе объектов очень много. В этой ситуации сборщику мусора приходится просеивать стог сена (десятки миллионов объектов) в поисках нескольких затерявшихся иголок. Он, конечно, со своей задачей справляется, но очень медленно. А пока он занят, основная работа простаивает. И это, опять же, хорошо видно на графике производительности:

Изображение

Этот график соответствует случаю, когда пазл сокобана (#21 из оригинальных 60) не разрешим с имеющейся у среды памятью. К концу работы (прерванной вручную) программа всё больше и больше времени (10+ секунд) простаивает, пока работает GC, что перемежается коротенькими рывками задачу таки решить. При этом программа не завершается с ошибкой Out of memory, просто потому, что до этого момента ещё далеко как по величине оставшейся памяти (в этом случае больше 10%), так и (в особенности!) по времени. (Заметка: на 250-ой секунде система сделала своп незадействованных процессов в файл подкачки, чтобы освободить оперативку. При этом даже нагрузка на процессор упала, так как Java-среда остановилась).

Чтобы бороться с такими ситуациями и позволить программе завершиться в разумное время (когда станет понятно, что для выполнения задачи выделенной среде памяти не хватит), я вручную отслеживаю загруженность памяти и завершаю работу, когда величина свободного места упадёт ниже некоторого лимита. Обычно это 20% от всего объёма. На втором графике для наглядности я этот лимит понизил до 10%, поэтому мне пришлось в конце концов завершить программу вручную. Соответствующий код выглядит приблизительно так:

код: [ скачать ] [ спрятать ]
Используется синтаксис Java

public class StateProcessor {
   
    private static final int MEMORY_RESERVE_PERCENT = 20;
    private static final int TIME_STEP = 1000;
    private static final int ITER_MASK = 8191;
    private static final Runtime rt = Runtime .getRuntime ();
   
    //  ...
   
    private long startTime, time;
   
    //  ...
   
    public void run (boolean priorityType, StateSpace stateSpace) {
        long iterCount, nextTime, memoryLimit, memory;
       
        initialize (priorityType, stateSpace);
       
        iterCount = 0;
        startTime = System .currentTimeMillis ();
        nextTime = startTime + TIME_STEP;
        memoryLimit = (long) ((1.0 - MEMORY_RESERVE_PERCENT / 100.0) * rt .maxMemory ());
       
        while (!nodesQueue .isEmpty ()) {
            expandState (nodesQueue .remove (), stateSpace);
           
            ++iterCount;
            if (0 != (iterCount & ITER_MASK)) {
                continue;
            }
            time = System .currentTimeMillis ();
            if (nextTime > time) {
                continue;
            }
            nextTime = time + TIME_STEP;
            //System .out .println ((time - startTime) + " " + iterCount + " " + stateSpace .getSize ());
            memory = rt .totalMemory () - rt .freeMemory ();
            if (memoryLimit > memory) {
                continue;
            }
            System .out .println ("Memory limit exceeded: " + memory + " / " + memoryLimit + " / " + rt .maxMemory ());
            return;
        }
       
        time = System .currentTimeMillis ();
    }
   
    //  ...
}
 


Можно, конечно, писать программы так, чтобы создавались только используемые объекты, тогда сборщику мусора нечего будет собирать... но в этом случае придётся шагать по труппам всех концепций ООП, положенных в основу Java. Не говоря о сложности такого написания и его склонности порождать трудновылавливаемые ошибки.

 Профиль  
                  
 
 Re: Sokoban: оптимальные решения
Сообщение04.12.2021, 19:35 
Аватара пользователя


26/05/12
1534
приходит весна?
Задумал я тут придумать функцию оценки удалённости состояний для алгоритма А-стар. Естественно, нужно будет эту функцию протестировать на корректность и эффективность. Для этого нужен некоторый полигон: много разных состояний с известными расстояниями между ними, желательно не привязанных ни к какому пазлу. А так же желательно, чтобы кратчайшие цепочки состояний были как можно длиннее. Так бабка за дедку, Жучка за внучку я написал автоматический генератор пазлов внутри произвольного лабиринта:
Цитата:
State_Space_Gauge.java (5.28 kB)
CellVector.java (3.04 kB)
DoubleComp.java (0.30 kB)
Helper.java (1.18 kB)
Level.java (16.60 kB)
StateSpace.java (23.05 kB)

Работает он что не наесть "в лоб". Сначала переборов всех возможных сочетаний генерируются все возможные состояния на заданной карте лабиринта (с учётом положения агента). Это даже получилось сделать в порядке возрастания кодирующего состояние идентификатора (57 бит на флаги наличия ящика в ячейке и 6 бит на индекс ячейки с агентом). Затем, так же перебором, строятся связи между этими состояниями: для каждого находится предыдущее и последующее. В результате получается ориентированный граф, весьма компактно хранимый фактически в двух массивах: childStates и parentStates. Массив stateIds нужен чтобы по индексу состояния определить какие положения ящиков и агента ему соответствуют.

Затем делается самое сложное: находится диаметр графа состояний. Это тоже делается в лоб. Для каждой конечной позиции ящиков мультистаром для каждого положения агента в этой позиции обратным ходом находятся расстояния от каждого состояния до стартовых конечных. Результаты сравниваются с сохранёнными максимальными расстояниями и при необходимости обновляются. При этом сохраняется и конечная позиция, соответствующая цепочке с этим расстоянием. Временная сложность этой части получается квадратичной по числу состояний, которое в свою очередь является (грубо говоря) экспоненциальной величиной от числа ящиков и количества ячеек на карте. Результаты получаются приблизительно такие:
код: [ скачать ] [ спрятать ]
Используется синтаксис Text

Maze map:
####
#..#####
#......#
#..#...#
##.#...#
 #.....#
 #...###
 #####

Number of cells:             25
Number of boxes:              5
Number of states:     1 062 600

Processing time:            991.917 sec
Processing speed:             1.115 Msttps
Processed states: 1 106 379 452
Divider:                   1020.553

State #326740:
####
#@.#####
#..$...#
#..#.$.#
##.#.$$#
 #.$...#
 #...###
 #####

State #1006840:
####
#$.#####
#$.....#
#.$#..$#
##.#...#
 #.....#
 #$..###
 #####

Distance: 176 moves, 43 pushes

Puzzle:
####
#+ #####
#. $   #
# .# $.#
## # $$#
 # $   #
 #.  ###
 #####
 

Как видно, производительность не очень даже для таких маленьких карт. Спасает только то, что коэффициент пропорциональности между квадратом числа состояний и реальным числом обработанных состояний весьма велик (величина divider в статистике). Работу можно чутка ускорить, если сделать более эффективную очередь, но не на много (порядок-полтора максимум). В связи с этим возникает вопрос: а можно ли искать диаметр направленного графа алгоритмически как-то более эффективно?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 62 ]  На страницу Пред.  1, 2, 3, 4, 5

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group