随机终盘生成性能测试
由于都使用的DFS搜索,而DLX代码的正确性已经验证过,所以我能确定所生成的数独终盘都是合法的。
所以我只需要进行相应函数的时间消耗测试:
测试每次跑20组,每组10w次,
1.“5+4”的DFS
2.“9”的DFS
3.“5+4”的DLX
4.“9”的DLX
显然这会比上一项还要费时,所以就不进行测试了。
可以看出,第一种方法比第二种是要快一点的。如果在100w的数据下,前者为11秒,后者为13秒。至于最后的DLX算法,emmm,当初听说很快,比直接DFS搜索快,但是最终的测试结果却慢将近20倍。我觉得DLX算法的搜索其实不占时间,但是初始化的过程太耗内存与时间,建立一个拥有2000多个节点的双向十字链表显然是非常耗时的。
所以最终,我选择了第一种方法。
至于求解的算法,我也会选择DFS,原因是很显然的。DLX算法已知的数越多,节点就越少(每个已知节点对应4个点,每个未知节点对应4*9=36个节点)对于已知5*9=45个格子的题目来说,这显然是已经知道的够多的了,但是DLX算法的效率还是这么慢。所以孰优孰劣,一目了然。
最终的在加上经过优化的文件输出后100w的数据时间为13.7秒,比纯粹的计算多了2秒左右。