Хабрахабр

[Перевод] Оптимизация поиска в ширину: как обработать граф с 10 миллиардами состояний

image

Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.

В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. Позже я напишу ещё один пост, в котором будет описана специфика игры. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным.

Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. Или а) состояния нужно сжать в 1/20 от их исходного, и так уже оптимизированного размера, или б) алгоритм должен иметь возможность эффективного сохранения состояний на диск и обратно, или в) сочетание двух вышеприведённых способов, или г) мне нужно купить больше ОЗУ или арендовать на несколько дней мощную виртуальную машину. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Как уместить 100 ГБ данных в 4 ГБ ОЗУ? Варианты А и В были исключены после proof of concept с помощью gzip: фрагмент описания состояний размером 50 МБ сжался всего до 35 МБ. Вариант Г я не рассматривал, потому что он слишком скучный. То есть оставался вариант Б, даже несмотря на то, что поиск в ширину казался довольно неудобным для хранения на вторичных накопителях. Это примерно по 7 байт на состояние, а мой запас памяти рассчитан примерно на 0,4 байта на состояние.

Содержание

Это довольно длинный пост, поэтому вот краткий обзор последующих разделов:

  • Поиск в ширину «по учебнику» — какова обычная формулировка поиска в ширину (breadth-first search, BFS), и почему она не подходит для сохранения частей состояния на диск?
  • BFS с сортировкой и слиянием — изменение алгоритма для эффективного пакетного избавления от избыточных данных.
  • Сжатие — снижение объёма используемой памяти в сто раз благодаря сочетанию стандартного и собственного сжатия.
  • Ой-ёй, я сжульничал! — в первых разделах я кое о чём умолчал: нам недостаточно просто знать, где находится решение, а нужно точно понимать, как его достичь. В этом разделе мы обновляем базовый алгоритм, чтобы он передавал достаточно данных для воссоздания решения из последнего состояния.
  • Сортировка + слияние со множественным выводом — хранение большего количества состояний полностью сводит на нет преимущества сжатия. Алгоритм сортировки + слияния необходимо изменить, чтобы он хранил два набора выходных данных: один, хорошо сжатый, используется во время поиска, а другой применяется только для воссоздания решения после нахождения первого.
  • Своппинг — своппинг в Linux намного хуже, чем я думал.
  • Сжатие новых состояний перед слиянием — до данного момента оптимизации памяти работали только со множеством посещённых состояний. Но оказалось, что список новых сгенерированных состояний намного больше, чем можно было подумать. В этом разделе показана схема для более эффективного описания новых состояний.
  • Экономия пространства на родительских состояниях — исследуем компромиссы между использованием ЦП/памяти для воссоздания решения в конце.
  • Что не сработало или может не сработать — некоторые идеи казались многообещающими, но в результате их пришлось откатить, а другие, которые предполагались рабочими из исследований, интуитивно мне кажутся неподходящими в данном случае.

Поиск в ширину «по учебнику»

Как выглядит поиск в ширину, и почему в нём не стоит использовать диск? До этого небольшого проекта я рассматривал только варианты формулировок «из учебников», например, такие:

def bfs(graph, start, end): visited = todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False

В процессе создания программой новых узлов-кандидатов каждый узел проверяется с хеш-таблицей уже посещённых узлов. Если он уже есть в хеш-таблице, то узел игнорируется. В противном случае он добавляется и в очередь, и в хеш-таблицу. Иногда в реализациях информация «visited» заносится в узлы, а не в стороннюю таблицу; но это рискованная оптимизация и она совершенно невозможна, если граф задан неявно.

Потому что хеш-таблицы склонны к созданию совершенно случайного паттерна доступа к памяти. Почему использование хеш-таблицы проблематично? Этот случайный паттерн доступа может вызывать проблемы с производительностью, даже если данные умещаются в памяти: доступ к огромной хеш-таблице с большой вероятностью будет вызывать промахи кэша и буфера ассоциативной трансляции (TLB). Если они этого не делают, то это плохая хеш-функция, и хеш-таблица скорее всего будет иметь низкую производительности из-за коллизий. Последствия будут катастрофическими: что-то порядка 10 мс на одну операцию поиска. Но что если значительная часть данных находится на диске, а не в памяти?

Это нам не подходит; задачу совершенно точно нужно преобразовать так, чтобы программа могла обрабатывать большие пакеты данных за один проход. При 10 миллиардах уникальных состояний только для доступа к хеш-таблице нам понадобится около четырёх месяцев ожидания дискового ввода-вывода.

BFS с сортировкой и слиянием

Если бы мы стремились максимально объединять операции доступа к данным в пакеты, то какой бы была максимально достижимая приблизительность? Поскольку программа не знает, какие узлы обрабатывать в слое глубины N+1 до полной обработки слоя N, кажется очевидным, что нужно выполнять дедупликацию состояний по крайней мере один раз за глубину.

Мы можем тривиально найти новое множество visited с помощью объединения множеств потоков и столь же тривиально найти множество todo с помощью разности множеств. Если мы одновременно работаем с целым слоем, то можно отказаться от хеш-таблиц и описать множество visited и новые состояния как какие-нибудь отсортированные потоки (например, как файловые потоки, массивы, списки).

По сути мы заглядываем в оба потока, обрабатываем меньший элемент, а затем продвигаемся вперёд по потоку, из которого был взят элемент (или по обоим потокам, если элементы в их начале одинаковы). Две операции со множествами можно объединить, чтобы они работали за один проход с обоими потоками. Затем продвигаемся вперёд по потоку новых состояний, а также добавляем элемент в новое множество todo: В обоих случаях мы добавляем элемент в новое множество visited.

def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False # Merges sorted streams new and visited. Return a sorted stream of
# elements that were just present in new, and another sorted
# stream containing the elements that were present in either or
# both of new and visited.
def merge_sorted_streams(new, visited): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: if visited.peek() == new.peek(): out_visited.add(visited.pop()) new.pop() elif visited.peek() < new.peek(): out_visited.add(visited.pop()) elif visited.peek() > new.peek(): out_todo.add(new.peek()) out_visited.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()) out_visited.add(new.pop()) return out_todo, out_visited

Паттерн доступа к данным теперь совершенно линеен и предсказуем, на всём протяжении слияния нет никаких произвольных доступов. Поэтому задержка операций с диском становится нам не важной, и единственное, что остаётся важным — пропускная способность.

Усреднённое состояние будет считываться и записываться 50 раз. Как будет выглядеть теоретическая производительность при упрощённом распределении данных по 100 уровням глубины, в каждом из которых есть по 100 миллионов состояний? Мой жёсткий диск предположительно может выполнять чтение и запись со средней скоростью 100 МБ/с, то есть на ввод-вывод в среднем уйдёт (2 * 2,5 ТБ) / (100 МБ/с) =~ 50к/с =~ 13 часов. Это даёт 10 байт/состояние * 5 миллиардов состояний * 50 = 2,5 ТБ. Это на пару порядков меньше, чем предыдущий результат (четыре месяца)!

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

Сжатие

Во введении я сказал, что в первоначальных экспериментах сжатие состояний не выглядело многообещающим, и показатель сжатия равен всего 30%. Но после внесения изменений в алгоритм состояния стали упорядоченными. Их должно быть намного проще сжать.

После сортировки они сжались в среднем до 1,4 байта на состояние. Чтобы протестировать эту теорию, я использовал zstd с головоломкой из 14,6 миллионов состояний, каждое состояние которой имело размер 8 байт. Его недостаточно, чтобы выполнять всю программу в памяти, но он может снизить время ввода-вывода диска всего до пары часов. Это походит на серьёзный шаг вперёд.

Можно быть практически уверенными в этом. Можно ли как-то улучшить результат современного алгоритма сжатия общего назначения, если мы что-то знаем о структуре данных? Теоретически сжатие — это просто стандартный проход Deflate. Хорошим примером этого является формат PNG. Фильтр PNG по сути является формулой для предсказания значения байта сырых данных на основании значения того же байта в предыдущей строке и/или того же байта предыдущего пикселя. Но вместо сжатия сырых данных изображение сначала преобразуется с помощью фильтров PNG. Учитывая типы изображений, для которых используется PNG, результат почти всегда будет состоять из нулей или чисел, близких к нулю. Например, фильтр «up» преобразует каждый байт вычитанием из него при сжатии значения предыдущей строки, и выполняя противоположную операцию при распаковке. Deflate может сжимать такие данные намного лучше, чем сырые данные.

Похоже, что это должно быть возможно. Можно ли применить подобный принцип к записям состояний BFS? Первые пробы с фильтром вычитания/прибавления, за которым выполнялся zstd, привели к улучшению показателя сжатия ещё на 40%: 0,87 байт на состояние. Как и в случае с PNG, у нас есть постоянный размер строки, и мы можем ожидать, что соседние строки окажутся очень схожими. Операции фильтрации тривиальны, поэтому с точки зрения потребления ресурсов ЦП они практически «бесплатны».

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

При выводе R2 мы сравниваем каждый байт с тем же байтом предыдущей строки, и 0 будет обозначать совпадение, а 1 — несовпадение: diff = [0, 0, 1, 0]. Допустим, у нас есть соседние строки R1 = [1, 2, 3, 4] и R2 = [1, 2, 6, 4]. В этом примере мы получим два байта 0b00000100 6. Затем мы передаём эту битовую карту, закодированную как VarInt, за которой следуют только байты, не совпавшие с предыдущей строкой. Но скомбинировав фильтр + zstd, мы снизили размер данных до 0,42 байт / состояние. Сам по себе этот фильтр сжимает эталонные данные до 2,2 байт / состояние. Или, если сказать иначе, это составляет 3,36 бит на состояние, что всего немного больше наших примерных вычисленных показателей, необходимых для того, чтобы все данные уместились в ОЗУ.

Когда поиск достигает точки, где память начинает вызывать проблемы, показатели сжатия могут становиться намного лучше. На практике показатели сжатия улучшаются, потому что отсортированные множества становятся плотнее. После сортировки эти состояния занимают 405 МБ и сжимаются по представленной выше схеме. Самая большая проблема заключается в том, что в конце мы получаем 4,6 миллиардов состояний visited. В конце концов сжатие и распаковка занимают примерно 25% от времени ЦП программы, но это отличный компромисс за снижение потребления памяти в сто раз. Это даёт нам 0,7 бита на состояние.

Похоже, что это легко усовершенствовать ценой малых затрат ЦП или небольшого повышения сложности. Представленный выше фильтр кажется немного затратным из-за заголовка VarInt в каждой строке. Эти варианты сами по себе давали гораздо более высокие показатели сжатия, но проявляли себя не так хорошо, когда выходные данные фильтра сжимались zstd. Я попробовал несколько разных вариантов, транспонирующих данных в порядок по столбцам, или записывающих битовые маски более крупными блоками, и т.д. У меня нет каких-то особо гениальных теорий о том, почему этот конкретный тип кодирования оказался гораздо лучше в сжатии, чем другие варианты. И это не было какой-то ошибкой zstd, результаты с gzip и bzip2 оказались похожими.

Изначально я подумал, что так получается, потому что в сортировке little-endian появляется больше ведущих нулей при битовой маске, закодированной VarInt. Ещё одна загадка: показатель сжатия оказался намного лучше, когда данные сортируются little-endian, а не big-endian. Но это отличие сохраняется даже с фильтрами, у которых нет таких зависимостей.

Однако я не нашёл много информации о сжатии отсортированных записей постоянной длины, и не хотел гадать, представляя данные как целочисленные значения с произвольной точностью.) (Есть множество исследований по сжатию отсортированных множеств целых чисел, ведь они являются базовыми строительными блоками поисковых движков.

Ой-ёй, я сжульничал!

Вы могли заметить, что представленные выше реализации BFS в псевдокоде возвращают только булевы значения — решение найдено/не найдено. Это не особо полезно. В большинстве случаев нам необходимо будет создать список точных шагов решения, а не просто сообщить о наличии решения.

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

def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state]

К сожалению, это уничтожит все преимущества сжатия, полученные в предыдущем разделе; в основе их лежит предположение о том, что соседние строки очень похожи. Когда мы просто смотрим на сами состояния, это справедливо. Но нет никаких причин полагать, что это будет истинно для родительских состояний; по сути, они являются случайными данными. Во-вторых, решение с сортировкой + слиянием должно считывать и записывать все просмотренные состояния на каждой итерации. Для сохранения связки состояния/родительского состояния нам придётся считывать и записывать на диск при каждой итерации все эти плохо сжимаемые данные.

Сортировка + слияние со множественным выводом

В самом конце, при возврате назад по решению, программе нужны будут только связки состояний/родительских состояний, Следовательно, мы можем параллельно хранить две структуры данных. Visited по-прежнему будет оставаться множеством посещённых состояний, как и раньше заново вычисляемым во время слияния. Parents — это по большей мере отсортированный список пар состояния/родительского состояния, которые не переписываются. После каждой операции слияния к parents добавляется пара «состояние + родительское состояние».

def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None # Merges sorted streams new and visited. New contains pairs of
# key + value (just the keys are compared), visited contains just
# keys.
#
# Returns a sorted stream of keys that were just present in new,
# another sorted stream containing the keys that were present in either or
# both of new and visited. Also adds the keys + values to the parents
# stream for keys that were only present in new.
def merge_sorted_streams(new, visited, parents): out_todo, out_visited = Stream(), Stream() while visited or new: if visited and new: visited_head = visited.peek() new_head = new.peek()[0] if visited_head == new_head: out_visited.add(visited.pop()) new.pop() elif visited_head < new_head: out_visited.add(visited.pop()) elif visited_head > new_head: out_todo.add(new_head) out_visited.add(new_head) out_parents.add(new.pop()) elif visited: out_visited.add(visited.pop()) elif new: out_todo.add(new.peek()[0]) out_visited.add(new.peek()[0]) out_parents.add(new.pop()) return out_todo, out_visited

Это позволяет нам пользоваться преимуществами обоих подходов с точки зрения времени выполнения и рабочих множеств, но требует больше вторичного пространства хранения. Кроме того, оказывается, что в дальнейшем по другим причинам будет полезной отдельная копия посещённых состояний, сгруппированная по глубине.

Своппинг

В псевдокоде игнорируется и другая деталь: в нём нет явного кода для дискового ввода-вывода, а присутствует только абстрактный интерфейс Stream. Stream может быть файловым потоком или массивом внутри памяти, но мы игнорировали эту подробность реализации. Вместо этого псевдокод занимается созданием паттерна доступа к памяти, позволяющего оптимально использовать диск. В идеальном мире этого было бы достаточно, и остальным могла бы заняться подсистема виртуальной памяти ОС.

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

Единственное, что изменилось — память сохранялась не как явный дисковый файл, а как своп. Уточню — это был тот же код и точно тот же паттерн доступа. Я всегда предполагал, что так происходит из-за того, что программы склонны считать ОЗУ памятью с произвольным доступом. Почти не требует доказательств тот факт, что своппинг совершенно рушит производительность в Linux, в то время как обычный файловый ввод-вывод этого не делает. Но здесь не тот случай.

Они хранятся в отдельных кэшах LRU с разными политиками истечения срока хранения; кроме того, похоже, что они имеют разные свойства упреждающего чтения/загрузки. Оказывается, что страницы с сохранением файлов и анонимные страницы обрабатываются подсистемой виртуальной машины по-разному.

Если части адресного пространства скорее всего будут выгружаться на какое-то время на диск, то лучше сохранять их вручную в файлы, чем доверять свопу. Теперь я знаю: своппинг в Linux скорее всего не будет хорошо работать даже в оптимальных условиях. Я осуществил это, реализовав собственный класс векторов, который изначально работает только в памяти, а после превышения определённого порога размера переключается на mmap во временный отдельный файл.

Сжатие новых состояний перед слиянием

В упрощённой модели производительности мы предполагали, что на каждую глубину будет приходиться 100 миллионов новых состояний. Оказалось, что это не очень далеко от реальности (в самой сложной головоломке максимум 150 с лишним миллионов уникальных новых состояний на одном слое глубины). Но измерять нужно не это; рабочее множество до слияния связано не только с уникальными состояниями, но и со всеми состояниями, выведенными для этой итерации. Этот показатель достигает величины в 880 миллионов выходных состояний на слой глубины. Эти 880 миллионов состояний а) нужно обрабатывать при паттерне случайного доступа для сортировки, б) нельзя эффективно сжать из-за отсутствия сортировки, в) нужно хранить вместе с родительским состоянием. Это рабочее множество составляет примерно 16 ГБ.

Просто записать все состояния на диск, выполнить внешнюю сортировку, провести дедупликацию, а затем как обычно выполнить слияние. Очевидное решение: использовать некую внешнюю сортировку. Поначалу я использовал это решение, и хотя оно по большей мере устраняло проблему А, но никак не справлялось с Б и В.

Если массив становится слишком большим (например больше 100 миллионов элементов), то он сортируется, дедуплицируется и сжимается. В конечном итоге я воспользовался альтернативным подходом: собрал состояния в массив в памяти. Фундаментально код для слияния новых и посещённых состояний остаётся таким же; он по-прежнему основан на постепенном проходе по потокам. Это даёт нам пакет отсортированных прогонов состояний, и внутри каждого прогона нет дубликатов, но они возможны между прогонами. Единственное отличие заключается в том, что вместо прохода всего по двум потокам существует отдельный поток для каждого из отсортированных прогонов новых состояний.

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

Экономия пространства на родительских состояниях

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

Если мы сможем проитерировать все возможные родительские состояния S', то у нас получится проверить, появляется ли какое-нибудь из них на глубине D во множестве visited. Нам нужно связать состояние S' на глубине D+1 с его родительским состоянием S на глубине D. К сожалению, для этой задачи такой подход не сработает; нам попросту слишком трудно сгенерировать все возможные состояния S для заданного S'. (Мы уже создали множество visited, сгруппированное по глубинам как удобный побочный продукт вывода связок состояния/родительского состояния при слиянии). Впрочем, для многих других задач поиска такое решение может и сработать.

Давайте итеративно обойдём все состояния на глубине D и посмотрим, какие выходные состояния у них получаются. Если мы можем генерировать переходы между состояниями только вперёд, но не назад, то почему бы тогда не сделать только это? Проблема этого плана в том, что он увеличивает общее потребление ресурсов процессора программой на 50%. Если какое-то состояние на выходе даёт S', то мы нашли подходящее S. (Не на 100%, потому что в среднем мы найдём S, просмотрев половину состояний на глубине D).

Существует ли более приемлемое решение где-то посередине? Поэтому мне не нравится не один из предельных случаев, но здесь, по крайней мере, возможен компромисс между ЦП/памятью. Чтобы найти S для заданного S', мы снова итеративно обходим все состояния на глубине D. В конце концов я решил хранить не пару (S', S), а пару (S', H(S)), где H — 8-битная хеш-функция. Если выходной результат не соответствует H(S), то это не то состояние, которое мы ищем, и мы можем просто его пропустить. Но прежде чем делать что-то другое, вычислим тот же хеш. Эта оптимизация означает, что затратные повторные вычисления нужно выполнять только для 1/256 состояний, что составляет незначительное повышение нагрузки на ЦП, и в то же время снижает объём памяти для хранения родительских состояний с 8-10 байт до 1 байта.

Что не сработало или может не сработать

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

Вместо этого оно хранилось как множество отсортированных прогонов, и эти прогоны время от времени ужимались. На этом этапе я не вычисляю повторно всё множество visited при каждой итерации. Недостаток — повышенная сложность кода и пониженный показатель сжатия. Преимущество такого подхода заключается в меньшем количестве записей на диск и ресурсов ЦП, затрачиваемых на сжатие. Но в конечном итоге показатель сжатия оказался больше в два раза. Изначально я думал, что подобная схема имеет смысл, ведь в моём случае операции записи более затратны, чем считывание. Преимущества такого компромисса неочевидны, поэтому в результате я вернулся к более простому виду.

Как можно догадаться, идея выполнения дедупликации совместно с сортировкой + слиянием во вторичном хранилище не нова. Уже проводились небольшие исследования о выполнении объёмного поиска в ширину для неявно заданных графов во вторичном хранилище, начать изучение этой темы можно с этой статьи 2008 года. Довольно поздно! Удивительно в этом то, что открыта она была только в 1993 году. Существуют более поздние предложения по поиску в ширину во вторичном хранилище, которые не требуют этапа сортировки.

В моём случае это совершенно бесполезно, потому что размеры кодируемых по сравнению с действительно достижимыми пространствами состояний очень отличаются. Одно из них заключалось в том, чтобы привязать состояния к целым числам, и хранить в памяти битовую карту посещённых состояний. И я очень сомневаюсь, что существуют интересные задачи, в которых подобный подход сработал бы.

Посещённые состояния хранятся без сортировки в файле. Ещё одна серьёзная альтернатива основывается на временных хеш-таблицах. Затем итеративно обходим посещённые состояния и ищем их в хеш-таблице. Сохраняем выходные данные, полученные из глубины D в хеш-таблицу. После итеративного обхода всего файла в нём останутся только недублируемые элементы. Если элемент найден в хеш-таблице, то удаляем его. Если количество выходных данных так велико, что хеш-таблица не помещается в памяти, то и файлы, и хеш-таблицы можно разбить на части, пользуясь одинаковым критерием (например, верхними битами состояния), и обрабатывать каждую часть по отдельности. Затем их добавляют к файлу и используют для инициализации списка todo для следующей итерации.

Я просто не увидел, как отказ от преимуществ сжатия может оправдать себя, поэтому не стал даже экспериментировать с такими подходами. Хоть и существуют бенчмарки, показывающие, что подход на основе хешей примерно на 30% быстрее, чем сортировка + слияние, но, похоже, что в них не учитывается сжатие.

Похоже. Ещё одной стоящей внимания областью исследований показалась оптимизация запросов к базе данных. Очевидно, что некоторые из этих исследований можно перенести и на задачу поиска. что задача дедупликации сильно связана с join баз данных, в котором тоже есть совершенно такая же дилемма «сортировка против хеширования». Похоже, это меняет баланс компромиссов: теперь он касается не только наиболее эффективной обработки одной итерации, но и создания наиболее оптимального формата выходных данных для следующей итерации. Разница может заключаться в том, что выходные данные join баз данных являются временными, в то время как выходные данные дедупликации BFS сохраняются до конца вычислений.

Заключение

На этом я завершаю изложение того, что я узнал из проекта, который в общем случае применим и к другим задачам поиска грубым перебором. Сочетание этих трюков позволило снизить объём решений самых сложных головоломок игры с 50-100 ГБ до 500 МБ и плавно увеличивать затраты, если задача превышает доступную память и записывается на диск. Кроме того, моё решение на 50% быстрее, чем наивная дедупликация состояний на основе хеш-таблиц даже для головоломок, помещающихся в памяти.

Рекомендую её всем, кому интересны очень сложные, но честные головоломки. Игру Snakebird можно приобрести в Steam, Google Play и в App Store.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть