如何为Python制作非图解算器，将其重写为Rust，以便可以通过WebAssembly在浏览器中直接运行它。
TL; DR
开始
关于Habré上的日语填字游戏（无字），已经有几篇文章。 例子
还有一个 。
图像使用位于行左侧和列上方的数字进行加密。 数字的数量显示相应行或列中有多少组黑色（或颜色，对于颜色填字游戏），以及数字本身-这些组中的每一个包含多少个合并的单元格（例如，一组三个数字-4，1，和3表示该行中有三组：第一组-四个，第二组-一个，第三组-三个黑格。 在黑白填字游戏中，组必须至少由一个空白单元格隔开;在彩色填字游戏中，此规则仅适用于一种颜色的组，并且多色的组可以紧密隔开（空单元格也可以沿着行的边缘）。 有必要确定细胞组的位置。
最普遍接受的观点之一是“正确”填字游戏只能称为以“逻辑”方式解决的填字游戏。 这通常称为解决方案方法，其中不考虑不同行和/或列之间的依赖关系。 换句话说，一种解决方案是对各个行或列的一系列独立决策，直到所有单元格都被填充为止（有关以下算法的更多信息）。 例如，只能在网站http://nonograms.org/（http://nonograms.ru/ ）上找到此类非图。 在以光速解决日本有色填字游戏一文中，已经引用了此站点的非图形作为示例。 为了进行比较和验证，我的求解器还增加了对从此站点下载和解析填字游戏的支持（感谢KyberPrizrak允许使用其站点的资料）。
但是，当通常的“逻辑”方法导致死胡同时，非图的概念可以扩展到更普遍的问题。 在这种情况下，必须对一个单元格的颜色进行假设，并在证明这种颜色导致矛盾之后，为该单元格标记相反的颜色。 这些步骤的顺序可以（如果有耐心的话）为我们提供所有解决方案。 本文将主要讨论解决此类填字游戏的更一般情况。
巨蟒
大约一年半以前，我无意间偶然发现了一篇描述一种解决单行方法的文章 （后来发现，该方法相当慢）。
当我在Python（我的主要工作语言）中实现此方法并添加所有行的顺序更新时，我发现所有这些并没有很快得到解决。 在研究了材料之后，事实证明，在这个主题上，有许多作品和实现为这项任务提供了不同的方法。
在我看来，分析各种求解器实现的最雄心勃勃的工作是由扬·沃尔特（Jan Wolter）进行的，并在他的网站上发布（据我所知，它仍然是Internet上最大的非图公共公共存储库），该详细研究包含大量信息和链接，可以帮助创建自己的求解器。
研究了大量资源（它们将在本文的结尾），我逐渐提高了求解器的速度和功能。 结果，我上瘾了，并且在空闲的时间里从事了10个月的算法实现，重构和调试。
核心算法
生成的求解器可以用四个决策层的形式表示：
（ line ）线性求解器：在输入处，一行单元格和一条描述线（线索），在输出处，部分求解的线。 在python解决方案中，我实现了4种不同的算法（其中3种适用于颜色填字游戏）。 最快的是BguSolver算法，以原始来源命名。 这是使用动态编程求解非图字符串的一种非常有效且几乎是标准的方法。 例如，可以在本文中找到此方法的伪代码。
（ 传播 ）我们将所有行和列放入队列中，并使用线性求解器进行遍历，当我们在求解行（列）时收到新信息时，我们分别使用新列（行）更新队列。 继续直到行为空。
示例和代码我们采取下一个任务从队列中解决。 使其为长度为7的空（未解析）字符串（我们将其表示为??????? ），并带有对块[2, 3] 。 线性求解器将产生部分分解的字符串?X??XX? 其中X是填充的单元格。 更新行时，我们看到编号为1、4、5的列已更改（索引从0开始）。 这意味着新信息已出现在指示的列中，并且可以将其返回到“线性”求解器。 我们将这些列放在优先级较高的任务队列中（以便接下来将它们提供给线性求解器）。
def propagation(board): line_jobs = PriorityDict() for row_index in range(board.height): new_job = (False, row_index) line_jobs[new_job] = 0 for column_index in range(board.width): new_job = (True, column_index) line_jobs[new_job] = 0 for (is_column, index), priority in line_jobs.sorted_iter(): new_jobs = solve_and_update(board, index, is_column) for new_job in new_jobs:
因此，我们从第二个层次开始解决我们的填字游戏（第一个仅适用于简并的情况，因为在整个填字游戏中只有一行或一列），然后逐步上移。 您可能会猜到，每个级别都会多次导致基础级别，因此，对于有效的解决方案，必须具有快速的第一级和第二级，对于复杂的难题可以调用数百万次。
在这个阶段，事实证明（完全可以预期），python根本不适合在这种CPU密集型任务中实现最高性能的工具：与低级语言相比，python中的所有计算效率极低。 例如，根据测量结果，在算法上最接近的BGU求解器（在Java中）在各种任务上的速度提高了7到17倍（有时高达27倍）。
更多细节 Pynogram_my BGU_my加速
舞者0.976 0.141 6.921986
猫1.064 0.110 9.672727
防滑1.084 0.101 10.732673
雄鹿1.116 0.118 9.457627
边缘1.208 0.094 12.851064
烟1.464 0.120 12.200000
结1.332 0.140 9.514286
秋千1.784 0.138 12.927536
妈妈2.108 0.147 14.340136
迪卡普2.076 0.176 11.795455
悲剧2.368 0.265 8.935849
默卡2.084 0.196 10.632653
石油2.948 0.219 13.461187
M＆M 3.588 0.375 9.568000
签名4.068 0.242 16.809917
轻3.848 0.488 7.885246
永远111.000 13.570 8.179808
中心5.700 0.327 17.431193
热门3.150 0.278 11.330935
空手道2.500 0.219 11.415525
9堂510.000 70.416 7.242672
国旗149.000 5.628 26.474769
狮子71.000 2.895 24.525043
马利12.108 4.405 2.748695
东西321.000 46.166 6.953169
自然inf 433.138 inf
Sierp inf inf NaN
盖蒂国际基金会
测量是在我的车上进行的，困惑是根据Jan Wolter在比较中使用的标准设置得出的
而且这已经是我开始使用PyPy之后的时间，在标准CPython上，计算时间比在PyPy上要长4-5倍！ 可以说，类似的Java求解器的性能比CPython代码高出28-85倍。
尝试使用性能分析（cProfile，SnakeViz，line_profiler）来提高我的求解器的性能虽然有所提高，但是它们并没有给出令人难以置信的结果。
+求解器可以解决https : //webpbn.com，http://nonograms.org及其网站（基于ini）格式的所有难题
+解决任意数量的颜色的黑白和彩色非图（满足的最大颜色数为10）
+解决缺少方块大小（填色）的难题。 这样的难题的一个例子 。
+可以在浏览器中的控制台/诅咒/窗口中呈现拼图（安装附加的Pynogram-web选项时）。 对于所有模式，都支持实时查看解决方案的进度。
-计算速度慢（与求解程序的文章比较中描述的实现方式相比，请参阅表 ）。
-低效的回溯：某些难题可以解决数小时（当决策树很大时）。
铁锈
年初，我开始学习Rust。 我像往常一样从The Book开始 ，了解了WASM，并完成了所建议的教程 。 但是，我想要一些真正的任务，在其中您可以发挥语言的优势（主要是其超级性能），而不是某人发明的一些示例。 所以我回到了非图论。 但是现在我已经有了Python中所有算法的有效版本，可以直接重写。
好消息从一开始就对我充满期待：事实证明，Rust及其类型系统完美地描述了我的任务的数据结构。 例如，一种基本的对应关系BinaryColor + BinaryBlock / MultiColor + ColoredBlock允许您永久地分离黑白和彩色非图。 如果在代码中的某处尝试使用普通的二进制描述块来解决彩色字符串，则会收到有关类型不匹配的编译错误。
基本类型看起来像这样 pub trait Color { fn blank() -> Self; fn is_solved(&self) -> bool; fn solution_rate(&self) -> f64; fn is_updated_with(&self, new: &Self) -> Result<bool, String>; fn variants(&self) -> Vec<Self>; fn as_color_id(&self) -> Option<ColorId>; fn from_color_ids(ids: &[ColorId]) -> Self; } pub trait Block { type Color: Color; fn from_str_and_color(s: &str, color: Option<ColorId>) -> Self { let size = s.parse::<usize>().expect("Non-integer block size given"); Self::from_size_and_color(size, color) } fn from_size_and_color(size: usize, color: Option<ColorId>) -> Self; fn size(&self) -> usize; fn color(&self) -> Self::Color; } #[derive(Debug, PartialEq, Eq, Hash, Clone)] pub struct Description<T: Block> where T: Block, { pub vec: Vec<T>, }
在移植代码时，有些要点清楚地表明，静态类型的语言（例如Rust（很好，例如C ++））更适合此任务。 更准确地说，泛型和特征比类层次结构更好地描述了一个域。 因此，在Python代码中，我有两个用于线性BguSolver类BguSolver和BguColoredSolver它们分别求解黑白线和彩色线。 在Rust代码中，我仍然具有唯一的通用struct DynamicSolver<B: Block, S = <B as Block>::Color>结构，它可以解决两种类型的任务，具体取决于创建过程中传递的类型（ DynamicSolver<BinaryBlock>, DynamicSolver<ColoredBlock> ）。 当然，这并不意味着在Python中无法完成类似的操作，只是在Rust中，类型系统清楚地向我表明，如果不这样做，就必须编写大量重复代码。
另外，当编写代码的过程归结为以下伪元算法时，任何尝试用Rust进行编写的人无疑都会注意到编译器中“信任”的影响：
write_initial_code
while（compiler_hints = $（货物检查））！= 0; 做
fix_errors（compiler_hints）
结束
当编译器停止发出错误和警告时，您的代码将与类型系统和借位检查器一致，并且您将预先警告一系列潜在的错误的发生（当然，要精心设计数据类型）。
我将给出一些函数示例，这些示例说明了Rust代码的简洁程度（与Python相比）。
unsolved_neighbours给出给定点（x，y）的未解决“邻居”列表
def unsolved_neighbours(self, position): for pos in self.neighbours(position): if not self.is_cell_solved(*pos): yield pos
fn unsolved_neighbours(&self, point: &Point) -> impl Iterator<Item = Point> + '_ { self.neighbours(&point) .into_iter() .filter(move |n| !self.cell(n).is_solved()) }
part_sums对于描述一条线的一组块，给出部分和（考虑到块之间的所需间隙），结果索引将指示该块可以终止的最小位置（此信息稍后将用于线性求解器）。
例如，对于这样的一组块[2, 3, 1]我们在输出[2, 6, 8]中有一个表示，这意味着第一个块可以最大程度地向左移动，以便其右边缘占据第二个单元格，其余的类似块：
1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _ _
2 3 1 | _ | _ | _ | _ | _ | _ | _ | _ | _ |
^ ^ ^
| | |
1个区块的结尾| | |
第2区块末尾-------- |
第3区块结束
@expand_generator def partial_sums(blocks): if not blocks: return sum_so_far = blocks[0] yield sum_so_far for block in blocks[1:]: sum_so_far += block + 1 yield sum_so_far
fn partial_sums(desc: &[Self]) -> Vec<usize> { desc.iter() .scan(None, |prev, block| { let current = if let Some(ref prev_size) = prev { prev_size + block.0 + 1 } else { block.0 }; *prev = Some(current); *prev }) .collect() }
移植时，我做了几处更改
有用的工具
- clippy是标准的静态分析器，有时甚至可以提供一些技巧，从而略微提高代码性能。
- valgrind是用于动态应用程序分析的工具。 我用它作为探查器来搜索botneks（
valrgind --tool=callgrind ），尤其是内存valrgind --tool=massif代码的部分（ valrgind --tool=massif ）。 提示：在启动分析器之前，将[profile.release] debug = true设置为Cargo.toml。 这会将调试字符保留在可执行文件中。 - kcachegrind查看callgrind文件。 一个非常有用的工具，用于查找性能方面最棘手的地方。
性能表现
开始在Rust上进行重写。 我们从已经提到的比较表中提取填字游戏，并通过原始文章中描述的最佳求解器进行操作。 运行结果和描述。 我们获取结果文件并在其上构建几个图，由于求解时间从毫秒到数十分钟不等，因此该图以对数标度绘制。
在jupyter笔记本电脑中运行 import pandas as pd import numpy as np import matplotlib.pyplot as plt %matplotlib inline
python求解器
（ 图片可点击 ）
我们看到这里的笔法图比所有提出的求解器都慢。 该规则的唯一例外是基于SAT的Tamura / Copris解算器，它比我们的解题器解决最简单的难题（图的左侧）的时间更长。 但是，这是SAT求解器的功能：它们是为超复杂的填字游戏而设计的，其中常规的求解器会长时间滞留在回溯中。 这在图的右侧清晰可见，其中Tamura / Copris解决最困难的难题的速度比其他人快数十和数百倍。
除锈剂
（ 图片可点击 ）
该图表明，在简单任务上的非齐格勒式也能应付或稍差于用C和C ++编写的高性能求解器（ Wolter和Syromolotov ）。 随着任务的复杂化，我们的求解器大致重复了BGU求解器（Java）的轨迹，但几乎总是领先于其大约一个数量级。 在最艰巨的任务上， 田村/ Copris始终领先于所有人。
锈与Python
（ 图片可点击 ）
最后，我们对这里描述的两个求解器进行了比较。 可以看出，Rust解算器几乎总是比python解算器提前1-3个数量级。
+求解器可以解决https://webpbn.com网站上的所有难题（不包括印迹-具有部分隐藏的块大小）， http ：//nonograms.org及其自身（基于TOML）格式
+解决任意数量颜色的黑白和彩色非图
+可以将拼图渲染到控制台（颜色c webpbn.com绘制真实颜色）
+运行速度快（与求解程序的文章比较中所述的实现方式相比，请参见表）。
-像Python解决方案一样，回溯仍然无效：某些难题（例如，无害的20x20 ）可以解决数小时（当决策树很大时）。 也许值得回溯，而不是使用集线器上已经提到的SAT解算器 没错，我乍看之下在Rust上发现的唯一SAT求解器似乎尚未完成并被抛弃。
网络组装
因此，用Rust重写代码已获得回报：求解器变得更快。 但是，Rust为我们提供了另一个非常酷的功能：WebAssembly中的编译以及直接在浏览器中运行代码的功能。
为了实现此功能，有一个用于Rust的特殊工具，它提供了必要的绑定器并生成样板，可以让您轻松地在JS代码中运行Rust函数-wasm-pack （+ wasm-bindgen ）。 Rust和WebAssembly教程中已经描述了与它以及其他重要工具有关的大多数工作。 但是，我必须自己弄清几点：
阅读时，会产生一种感觉，即该教程主要是为希望使用Rust加速其代码的JS开发人员编写的。 好吧，或者至少对于熟悉npm的人来说 。 对于我来说，作为一个远离前端的人，令人惊讶地发现，即使本书中的标准示例也不想使用与npm run start不同的第三方Web服务器。
幸运的是，wasm-pack具有一种模式，允许您生成常规JS代码（这不是npm模块）。 wasm-pack build --target no-modules --no-typescript将仅在输出中提供两个文件： project-name.wasm-编译为WebAssembly和project-name.js的Rust代码的二进制文件。 可以将最后一个文件添加到任何HTML页面<script src="project-name.js"></script>并使用WASM函数，而无需担心npm，webpack，ES6，模块和现代JS开发人员的其他乐趣。 no-modules模式非常适合WASM应用程序开发期间的非前端开发人员以及示例和演示，因为它不需要任何其他前端基础结构。
WebAssembly非常适合JavaScript繁重的任务。 首先，这些是执行许多计算的任务。 如果是这样，即使使用WebAssembly，也可以长时间执行此类任务，从而违反了现代Web的异步原理。 我正在谈论各种各样的警告：我的求解器工作时碰巧观察到的无响应脚本 。 要解决此问题，可以使用Web worker机制。 在这种情况下，使用“大量” WASM函数的方案可能如下所示：
- 从事件的主脚本（例如，单击按钮）中发送消息给工作人员，以启动重功能。
- , .
- - ()
WASM- JS, WASM . - ( ), HashMap , . ( JS) , / .
, Mutex , thread-safe. smart- . thread-safe Rc Arc RefCell RwLock . : 30%. --features=threaded thread-safe , WASM-.
6574 8098 ( 10 ):
, - 40..70% , , (32..37%) thread-safe ( cargo build --release --features=threaded ).
Firefox 67.0 Chromium 74.0.
WASM- ( ). https://webpbn.com/ http://www.nonograms.org/
TODO
"" /, / .
, . "" , , . .
( , 3600 ). WASM , ( , (!) , , WASM). , , - , nonogrid .
. : , , WASM . , ( ) , JS , .
JS. backtrace, .
( TOML- )
总结
, (, , etc).
Rust 1-3 PyPy 1.5-2 ( ).
Python Rust , Python (, , comprehensions), Rust-.
Rust WebAssembly . Rust , WASM, ( 1.5 ).
- The 'pbnsolve' Paint-by-Number Puzzle Solver by Jan Wolter and the survey
- The BGU Nonograms Project
- Solving Nonograms by combining relaxations
- An Efficient Approach to Solving Nonograms
- Color and black and white Japanese crosswords on-line
- 'Nonolib' library by Dr. Steven Simpson
- Rust and WebAssembly