c – 解开Knuth结:如何重组意大利面条代码?

前端之家收集整理的这篇文章主要介绍了c – 解开Knuth结:如何重组意大利面条代码?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
这个问题的灵感来自于 How to transform a flow chart into an implementation?,它要求从代码中算法去除goto语句的方法. answer的一般问题在 this年的科学论文中有所描述.

我从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;

问题是:该代码如何重构以消除所有的goto调用

一个(虚假)答案是“查阅引用的科学论文,并沿着它”的建议 – 的确,这当然是一种可能性.但是,这个问题是关于程序员在看到这个spaghetti code后立即看到的.

我对如何重构感兴趣,一步一步,不仅仅是代码.

注意:

>根据其高级规范和goto跳转实际实现算法X是直接的.实现黑盒子函数initialize()等将只需要几个额外的指令,但是对于代码的结构是不相关的.在函数调用过程中发生的情况并不重要,因为现在关注程序的流程.
>“GOTO still considered harmful?”的辩论与这个问题绝对无关,在答案和意见中都不应该被解决.

相关:how to work with or complete the spaghetti code?

解决方法

我在 https://stackoverflow.com/a/36661381/120163早期草拟了OP算法

找到一个更好的论文,讨论如何生成结构化代码,同时保留原始控制流程图:

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)”的操作.

有趣的是,所有这些结构似乎都不能帮助这个代码的可读性.令人惊奇的是“结构化计划”的整体.也许精心设计的意大利面条不是那么糟糕: – }

原文链接:https://www.f2er.com/c/112680.html

猜你在找的C&C++相关文章