我从Knuth的算法X的高级草图中实现了一些代码.计算机程序的技术描述了具有限制前缀的词典排列的生成(参见draft的第16页).
这是上述算法的相应flow chart.
这可能是一个非常聪明和非常有效的算法,但代码的结构似乎是具有挑战性的.我最终使用了好的老goto风格的实现：
//Algorithm X;
1:
initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
if (k == n) {
visit();
goto 6;
}
goto 4;
}
goto 5;
4:
increase(k);
goto 2;
5:
increasev2(a[k]);
if (q != 0) {
goto 3;
}
6:
decrease(k);
if (k==0) {
goto 7;
}
set(p,u_k);
goto 5;
7:
return;
一个(虚假)答案是“查阅引用的科学论文,并沿着它”的建议 – 的确,这当然是一种可能性.但是,这个问题是关于程序员在看到这个spaghetti code后立即看到的.
我对如何重构感兴趣,一步一步,不仅仅是代码.
注意：
>根据其高级规范和goto跳转实际实现算法X是直接的.实现黑盒子函数initialize()等将只需要几个额外的指令,但是对于代码的结构是不相关的.在函数调用过程中发生的情况并不重要,因为现在关注程序的流程.
>“GOTO still considered harmful?”的辩论与这个问题绝对无关,在答案和意见中都不应该被解决.
解决方法
找到一个更好的论文,讨论如何生成结构化代码,同时保留原始控制流程图：
https://stackoverflow.com/a/36661381/120163597/1-s2.0-S01676423https://stackoverflow.com/a/36661381/120163597-main.pdf?_tid=1b75bd8c-1401-11e6-ae94-00000aab0f02&acdnat=1462590747_485d767d608ea2714e654707609910dc” rel=”nofollow noreferrer”>W.D Maurer,“Generalized structured programs and loop trees”,Science of Computer Programming,2007
我遵循这个程序(在纸上,希望我做的对,在上午2:40看起来不错).他的基本技巧是找到强连接的区域(代码中的循环);这些将成为循环;他然后通过删除边缘来打破这个循环;这最终成为一个循环反向链接(当他完成时恢复).重复该过程,直到找不到更多的循环;剩下的是本质上是具有识别循环的结构化程序.这样做是很棘手的;你真的需要一个自动化程序.你的代码虽然很小,但仍然很糟糕： – }
我在一个地方骗了Maurer坚持认为,前进goto是可以的,甚至进入循环的中间.如果你买的话,那么你可以保存CFG.如果没有,你必须处理循环有两个或多个入口点的情况;你的算法有这样一个循环.我通过对循环进行编码来解决问题,并编写一个循环尾部片段等价物,其行为就像跳转到中间的第一个迭代,循环本身后面.
我的符号有点滑稽：大多数语言没有“块{…}”结构. [我编码的(见生物)].认为这是一个“执行一个迭代”循环： – }我假设块/循环有循环退出并循环继续.如果你没有这些,你可以用足够数量的{{}}和exit_block @ N来模拟它们.
编辑接受后：在光明的一天,我没有做到正确,我省略了while循环@ 3.我修补了对块构造的需求现在消失了,因为我可以退出while循环@ 3来实现相同的影响.实际上,代码读得好一点.
//Algorithm X;
1:
initialize();
2:
while (true) {
enter_level(k);
3:
while (true) {
set(a[k],q);
if (test() == ok) {
if (k != n) exit_while@3;
visit();
decrease(k); // replicate logic at 6 to avoid jumping into middle of 5 loop
if (k==0) return;
set(p,u_k);
}
5:
while (true) {
increasev2(a[k]);
if (q != 0) continue_while@3;
6:
decrease(k);
if (k==0) return;
set(p,u_k);
} // while(true)@5
} // while(true)@3
4:
increase(k);
} // while(true)@2
与我迄今为止看到的大多数其他答案不同,它的运行速度与原始速度相同(没有额外的标志或标志检查).
@ hatchet的答案很有趣; a)同样快,b)他用相同的技术选择了两个入口循环,但他选择了“其他条目”作为循环顶点.他在标签2中做了类似于“enter_level(k)”的操作.
有趣的是,所有这些结构似乎都不能帮助这个代码的可读性.令人惊奇的是“结构化计划”的整体.也许精心设计的意大利面条不是那么糟糕： – }
