几个月前，我终于不得不承认我不够聪明，无法通过某些级别的“
蛇鸟”拼图。 恢复某些自尊的唯一方法是编写求解器。 因此，我可以假装创建一个程序来解决难题与自己解决难题几乎相同。
Github上提供了生成的C ++程序的代码。 本文考虑的代码的主要部分在
search.h和
compress.h中实现 。 在本文中，我将主要讨论优化广度优先搜索，该搜索需要50-100 GB的内存才能容纳4 GB。
稍后，我将写另一篇文章，描述游戏的细节。 在这篇文章中，您需要知道我找不到蛮力的替代品，因为通常的技巧都没有。 游戏具有许多状态，因为有很多移动或推动的对象，并且其中一些的形状很重要，并且会随着时间而变化。 对于A *之类的算法，没有合适的保守启发法来缩小搜索空间。 搜索图是定向的和隐式指定的；因此，不可能同时进行正向和反向搜索。 唯一的举动可以以许多不相关的方式改变状态，因此没有什么比像
Zobrist哈希那样派上用场了。
粗略估计表明，最大的难题是，消除所有对称位置后，将有大约100亿个州。 即使在以最大密度打包状态描述之后，状态大小仍为8-10字节。 拥有100 GB的内存，这项任务将是微不足道的，但是对于我的拥有16 GB内存的家用计算机而言，这并不是一件容易的事。 由于Chrome需要12 GB的存储空间，因此我的实际内存接近4 GB。 超出此卷的所有内容都必须保存到磁盘（旧且生锈的硬盘驱动器）中。
如何在4 GB的RAM中容纳100 GB的数据？ a）需要将状态压缩到已优化的原始大小的1/20，或者b）算法应该能够有效地将状态保存到磁盘，反之亦然，或者c）以上两种方法的组合，或者d）我需要购买更多RAM或租用功能强大的虚拟机几天。 我没有考虑选项D，因为它太无聊了。 在使用gzip进行概念验证后，排除了选项A和B：状态描述为50 MB的片段被压缩为仅35 MB。 每个状态大约7个字节，而我的内存大约每个状态0.4个字节。 也就是说，即使广度优先搜索对于将其存储在辅助驱动器上似乎很不方便，也保留了选项B。
目录内容
这是一篇相当长的文章，因此这里是以下各节的简要概述：
- 教科书中的广度优先搜索-常用的广度优先搜索（BFS）措辞是什么，为什么它不适合将部分状态保存到磁盘？
- 具有排序和合并功能的BFS-为有效批量处理冗余数据而对算法进行的更改。
- 压缩 -由于标准压缩和本机压缩的组合，使使用的内存量减少了一百倍。
- 哦，哦，我被骗了！ -在第一部分中，我对某些事情保持沉默：仅仅了解解决方案的位置还不够，但是我们需要确切地了解如何实现。 在本节中，我们将更新基本算法，以便它传输足够的数据以从最后一个状态重新创建解决方案。
- 排序+与多个输出合并 -存储更多状态会完全抵消压缩的好处。 排序+合并算法需要更改，以便它存储两组输出数据：一组在搜索过程中经过了充分压缩，而另一组仅在找到第一个后才用于重新创建解决方案。
- 交换 -在Linux上交换比我想象的要糟糕得多。
- 合并之前压缩新状态 -到目前为止，内存优化仅适用于许多访问状态。 但是事实证明，新生成状态的列表比您想象的要大得多。 本节显示了用于更有效地描述新状态的图。
- 节省父状态的空间 -最后探讨在使用CPU /内存重新创建解决方案之间的权衡。
- 什么不行或可能行不通 -有些想法似乎很有希望，但结果却不得不撤回，而另一些本应是研究人员的想法在我看来在这种情况下不合适。
广泛搜索“按教科书”
广度优先搜索是什么样的？为什么不使用磁盘？ 在进行这个小型项目之前，我只考虑了“从教科书中”的措词选项，例如：
def bfs(graph, start, end): visited = {start} 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
在程序创建新的候选节点的过程中，将使用已访问节点的哈希表检查每个节点。 如果它已经在哈希表中，则忽略该节点。 否则，它将被添加到队列和哈希表中。 有时，在实现中，“访问”信息是在节点中输入的，而不是在外部表中输入的； 但这是一个冒险的优化，如果隐式指定图形，则完全不可能。
为什么使用哈希表有问题？ 因为散列表倾向于创建完全随机的内存访问模式。 如果不这样做，那么这将是一个不好的哈希函数，并且由于冲突，哈希表很可能会具有较差的性能。 即使数据适合内存，这种随机访问模式也可能导致性能问题：对巨大的哈希表的访问可能会导致高速缓存未命中和关联转换缓冲区（TLB）。 但是，如果很大一部分数据在磁盘上而不在内存中怎么办？ 结果将是灾难性的：每次搜索操作大约10毫秒。
拥有100亿个唯一状态，仅访问哈希表将花费我们大约四个月的时间来等待磁盘I / O。 这不适合我们； 绝对必须转换任务，以便程序可以在一次通过中处理大型数据包。
具有排序和合并功能的BFS
如果我们想将数据访问操作尽可能地集成到程序包中，那么可达到的最大近似值是多少？ 由于该程序直到深度N层被完全处理才知道在深度N +1层中要处理的节点，因此很显然，有必要对每个深度至少重复一次状态。
如果我们同时使用整个层，则可以放弃哈希表，并将访问状态和新状态集描述为某些排序流（例如，文件流，数组，列表）。 我们可以通过组合流程集合来简单地找到访问的新集合，并且使用集合的差异来找到集合待办事项也很容易。
可以将带有集合的两个操作组合在一起，以便它们在两个线程中一次通过。 实际上，我们研究了两个流，处理了较小的元素，然后沿着获取元素的流前进（如果开头的元素相同，则沿着两个流前进）。 在这两种情况下，我们都将项目添加到新的访问集中。 然后，我们沿着新状态流前进，并向新的待办事项集添加一个元素：
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
现在，数据访问模式是完全线性且可预测的；在整个合并过程中，没有任意访问。 因此，磁盘操作的延迟对我们而言并不重要，唯一重要的是带宽。
简化的数据分布在100个深度级别（每个深度级别都有1亿个状态）下，理论性能会如何？ 平均状态将被读取和写入50次。 这提供了10个字节/状态* 50亿个状态* 50 = 2.5 TB。 我的硬盘大概可以以100 MB / s的平均速度进行读写，也就是说，平均I / O将花费（2 * 2.5 TB）/（100 MB / s）=〜50k / s =〜13小时。 这比以前的结果（四个月）少了几笔订单！
还值得注意的是，这种简化的模型没有考虑新生成状态的大小。 在合并步骤之前，必须将它们存储在内存中以进行排序和重复数据删除。 我们将在以下各节中介绍。
压缩方式
在引言中，我说过，在最初的实验中，状态压缩看起来没有希望，压缩率仅为30％。 但是在更改算法后，状态变得简化了。 它们应该更容易压缩。
为了验证这一理论，我使用了zstd以及1460万个状态的谜题，每个状态的大小为8个字节。 排序后，每个状态平均将它们压缩到1.4个字节。 这似乎是向前迈出的重要一步。 在内存中运行整个程序是不够的，但是可以将磁盘I / O时间减少到几个小时。
如果我们对数据结构有所了解，是否有可能以某种方式改善现代通用压缩算法的结果？ 您几乎可以肯定。 PNG格式就是一个很好的例子。 从理论上讲，压缩只是标准的Deflate传递。 但是，不是压缩原始数据，而是首先使用
PNG过滤器转换图像。 PNG过滤器实质上是一个公式，用于根据前一行中相同字节和/或前一个像素中相同字节的值来预测原始数据字节的值。 例如，“向上”过滤器通过在压缩时从前一个字节中减去前一行的值来转换每个字节，并在拆包时执行相反的操作。 给定使用PNG的图像类型，结果几乎总是由零或接近零的数字组成。 Deflate可以比原始数据更好地压缩此类数据。
可以将此原理应用于BFS状态记录吗？ 看来这应该是可能的。 与PNG一样，我们具有恒定的行大小，并且可以预期相邻行非常相似。 带有减法/加法滤波器的第一个采样，然后是zstd，使压缩率又提高了40％：每个状态0.87字节。 过滤操作是微不足道的，因此，从CPU消耗的角度来看，它们实际上是“免费的”。
我不清楚是否可以进行其他任何改进，或者这是否是实际的限制。 在图像数据中，您可以在逻辑上期望同一行的相邻字节相似。 但是在这些州没有这种东西。 但是实际上，稍微复杂一些的过滤器仍然可以改善结果。 最后，我来到了这个系统：
假设我们有相邻的行R1 = [1,2,3,4]，R2 = [1,2,6,4]。 输出R2时，我们将每个字节与前一行的相同字节进行比较，0表示匹配，1表示不匹配：diff = [0，0，1，0]。 然后，我们传递此位图，将其编码为VarInt，然后仅传递与前一行不匹配的字节。 在此示例中，我们得到两个字节0b000001006。此过滤器本身将参考数据压缩为2.2字节/状态。 但是通过组合+ zstd过滤器，我们将数据大小减小到0.42字节/状态。 或者，换句话说，这相当于每个状态3.36位，仅比我们为确保所有数据都适合RAM所需的近似计算指标多一点。
实际上，由于分类的集合变得更密集，因此压缩率得以提高。 当搜索到内存开始引起问题的程度时，压缩率会变得更好。 最大的问题是，最终我们有46亿个访问州。 排序后，这些状态占据405 MB，并根据上述方案进行压缩。 这给我们
每个状态0.7位 。 最后，压缩和解压缩占用程序CPU时间的25％左右，但这对于将内存消耗减少100倍是一个很大的折衷。
由于每行上的VarInt标头，上述过滤器似乎有点昂贵。 看起来很容易以较低的CPU成本或稍微增加复杂性为代价进行升级。 我尝试了几种不同的选择，按列顺序转置数据，或在较大的块中写入位掩码等。 仅这些选项产生的压缩率就高得多，但是当滤波器输出被zstd压缩时效果不佳。 这不是zstd错误，使用gzip和bzip2的结果却是相似的。 关于为何这种特定类型的编码在压缩方面比其他选择要好得多，我没有任何特别巧妙的理论。
另一个谜：当数据按小端而不是大端排序时，压缩率要好得多。 最初，我认为是这样，因为在小尾数排序中，由VarInt编码的位掩码有更多的前导零。 但是，即使没有这种依赖性的过滤器，这种差异仍然存在。
（由于它们是搜索引擎的基本组成部分，因此有很多关于压缩整数排序集的研究。但是，我没有找到太多有关压缩恒定长度的排序记录的信息，也不想猜测，以任意精度将数据表示为整数值。）
哦，哦，我被骗了！
您可能已经注意到，以上以伪代码执行的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]
不幸的是，这将破坏在上一节中获得的所有压缩好处。 它们基于相邻线非常相似的假设。 当我们只看国家本身时，这是真的。 但是没有理由相信这对于父母制国家是正确的。 实际上，它们是随机数据。 其次，排序+合并解决方案应读取和写入每次迭代时查看的所有状态。 为了保存状态/父状态的链接，我们必须在每次迭代时将所有这些压缩不良的数据读写到磁盘上。
排序+与多个输出合并
最后，返回到解决方案时，程序仅需要状态/父状态束，因此，我们可以并行存储两个数据结构。 如之前在合并过程中重新计算的，“访问”将继续是访问状态集。 父级至少是未覆盖的状态/父级状态对的排序列表。 在每次合并操作之后，将“状态+父状态”对添加到父项。
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
这使我们可以在运行时和工作集方面利用这两种方法，但是需要更多的辅助存储空间。 另外，事实证明，将来，由于其他原因，按深度分组的访问状态的单独副本将很有用。
掉期
伪代码中忽略了另一个细节：磁盘I / O没有显式代码，只有抽象Stream接口。 流可以是文件流或内存中的数组，但是我们忽略了此实现细节。 相反，伪代码正在创建一个内存访问模式，该模式允许磁盘的最佳使用。 在理想情况下，这就足够了，其余的可以由OS虚拟内存子系统占用。
但这至少在Linux上不会发生。 在某个时候（在将工作数据压缩到内存大小之前），我让程序在大约11个小时内运行，并且数据主要保存到磁盘上。 然后，我使程序使用匿名页面而不是存储在文件中，并在同一驱动器上选择了足够大小的交换文件。 但是，三天后，该程序只进行了四分之一，但随着时间的推移，它变得越来越慢。 根据我的乐观估计，她应该在20天内完成工作。
我会澄清-这是相同的代码和
完全相同的访问模式 。 唯一更改的是，内存不是保存为显式磁盘文件，而是保存为交换文件。 几乎不需要证据表明交换会完全破坏Linux性能，而常规文件I / O不会。 我一直认为这是由于程序倾向于将RAM视为随机存取存储器。 但是事实并非如此。
事实证明，虚拟机子系统对文件保存页面和匿名页面的处理方式有所不同。 它们存储在具有不同到期策略的单独的LRU缓存中。 此外，它们似乎具有不同的预读/加载预读属性。
现在我知道：即使在最佳条件下，在Linux上交换也很可能无法正常工作。 如果地址空间的某些部分可能会在一段时间内卸载到磁盘上，则最好将它们手动保存在文件中，而不是信任交换。 我通过实现自己的向量类来实现此目的，向量类最初仅在内存中工作，并且在超过一定大小阈值后，将其切换到临时单独文件中的mmap。
合并前压缩新状态
在简化的性能模型中，我们假设每个深度将出现1亿个新条件。 事实证明，这与现实相距不远（在最复杂的难题中，一层深度上最多有超过1.5亿个独特的新状态）。 但是，这不应该被衡量； 合并之前的工作集不仅与唯一状态相关，而且还与为此迭代推断的所有状态相关联。 这个数字达到每个深度层8.8亿个输出状态。 这8.8亿个状态a）需要使用随机访问模式进行处理以进行排序，b）由于缺乏排序而无法有效压缩，c）必须与父状态一起存储。 该工作集大约为16 GB。
显而易见的解决方案：使用某种外部排序。 只需将所有状态写入磁盘，执行外部排序，重复数据删除，然后照常合并即可。 最初，我使用了此解决方案，尽管它最多消除了问题A，但我无法应付B和C。
最后，我采取了另一种方法：将状态收集到内存中的数组中。 如果数组太大（例如，超过1亿个元素），则将对其进行排序，重复数据删除和压缩。 这为我们提供了排序状态运行的程序包，并且每次运行内都没有重复项，但是在两次运行之间可能会出现重复项。 从根本上说，合并新州和拜访州的代码保持不变。 它仍然基于溪流的逐渐通过。 唯一的区别是，对于新状态的每个已排序运行，每个流都有一个单独的流，而不是仅通过两个流。
当然，这些1亿个州运行的压缩率不如所有访问状态集的压缩率好。 但是即使有了这样的指标，它也显着减少了工作集的数量和磁盘I / O的需求。 您需要更多的CPU资源来处理线程的优先级队列，但这仍然是一个很大的折衷。
节省父州的空间
在此阶段，程序占用的绝大部分空间都用于存储父状态，因此找到解决方案后，我们可以重新创建其过程。 它们很可能很难被很好地压缩，但是在CPU和内存之间是否存在某种折衷？
我们需要将状态“在D + 1的深度处与其状态S的父状态在D的深度处进行连接。如果我们可以遍历S的所有可能的父状态，那么我们可以检查它们中是否有任何一个在D的深度处出现。 （我们已经创建了很多访问对象，并按深度分组，作为合并过程中状态/父母状态包派生的便捷副产品）。不幸的是，这种方法不适用于该任务。对于我们来说，对于给定的S'生成S的所有可能状态简直太困难了。但是，对于许多其他搜索任务，这样的解决方案可能会起作用。如果我们只能在状态之间产生向前的转换，而不能向后转换，那为什么不这样做呢？让我们迭代遍历深度D处的所有状态，看看它们得到什么样的输出状态。如果输出中的某个状态给出S'，则我们找到了一个合适的S。此计划的问题是，它将程序的总CPU消耗增加了50％。 （不是100％，因为平均而言，通过查看深度D处的一半状态，我们可以找到S）。因此，我不喜欢这种限制情况之一，但是在这里，至少可以在CPU /内存之间做出折衷。两者之间是否有更可接受的解决方案？最后，我决定不存储对（S'，S），而是存储对（S'，H（S）），其中H是8位哈希函数。为了找到给定S'的S，我们再次迭代遍历深度D的所有状态。但是在进行其他操作之前，我们先计算相同的哈希值。如果输出与H（S）不匹配，则这不是我们正在寻找的状态，我们可以直接跳过它。这种优化意味着只需要对1/256状态执行昂贵的重新计算，这表示CPU负载略有增加，同时将用于存储父状态的内存量从8-10字节减少到1字节。什么不起作用或可能不起作用
在前面的部分中，我们研究了有效的高级优化顺序。我尝试了其他无效的方法或在文献中发现的其他方法，但决定在这种情况下它们将无效。这是部分清单。此时，我不会重新计算每次迭代访问的整个集合。而是将其存储为许多已排序的运行，并且不时压缩这些运行。这种方法的优点是更少的磁盘写入和CPU资源用于压缩。缺点是增加了代码复杂度并降低了压缩率。最初，我认为这样的方案是有意义的，因为就我而言，写操作比读取要昂贵。但是最后，压缩率竟然是原来的两倍。这种折衷的优势并不明显，因此，我回到了一种更简单的形式。在二级存储中对隐式定义的图执行体积广度优先搜索方面的研究很少，您可以开始探索该主题摘自2008年这篇文章。您可能会猜到，在辅助存储中进行重复数据删除以及排序+合并的想法并不新鲜。令人惊讶的是，它仅在1993年开放。太晚了！以后，建议在二级存储中进行广度优先搜索，而无需排序步骤。其中之一是将状态绑定到整数，并将访问状态的位图存储在内存中。在我的情况下，这是完全没有用的，因为与真正可到达的状态空间相比，编码状态的大小有很大不同。而且我非常怀疑这种方法能否有效地解决一些有趣的问题。另一个严肃的选择是基于临时哈希表。访问状态被存储而没有在文件中排序。我们将从深度D获得的输出保存到哈希表中。然后迭代遍历访问状态并在哈希表中查找它们。如果在哈希表中找到该项目，则将其删除。迭代遍历整个文件后，仅非重复元素将保留在其中。然后将它们添加到文件中，并用于初始化下一次迭代的待办事项列表。如果输出量太大，以致哈希表无法容纳在内存中，则可以使用相同的标准（例如，高位状态位）将文件和哈希表划分为多个部分，并且应分别处理每个部分。虽然有基准表明基于散列的方法比排序+合并快30％，但似乎它们没有考虑压缩。我只是没有看到拒绝压缩带来的好处可以证明其合理性，因此我什至没有尝试使用这种方法。另一个值得关注的研究领域是数据库查询的优化。看起来像。重复数据删除任务与数据库连接密切相关，排序和散列难题 也有完全相同的。显然，其中一些研究可以应用于搜索问题。区别可能是联接数据库输出是临时的，而BFS重复数据删除输出将存储到计算结束。看来，这正在改变折衷的平衡：现在，它不仅涉及一次迭代的最有效处理，而且还涉及为下一次迭代创建最佳输出数据格式。结论
这结束了我对我从一个项目中学到的知识的总结，该项目通常适用于蛮力的其他搜索任务。这些技巧的组合使解决最复杂游戏难题的解决方案数量从50-100 GB减少到500 MB，并在任务超出可用内存并写入磁盘时平稳地增加了成本。此外，即使对于内存中的难题，我的解决方案也比基于哈希表的幼稚状态重复数据删除快50％。可以在Steam，Google Play和App Store上购买Snakebird 。我推荐给对非常复杂但诚实的难题感兴趣的任何人。