免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: send_linux

《ruby元编程》有奖试读中!(获奖名单已公布) [复制链接]

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-03-03 16:31 |显示全部楼层
回复 86# starwing83

关于缓式求值。在默认缓式求值的语言中,缓式求值是普遍深入的。

C(generator本来就只是模拟缓式求值的机制,而C连模拟generate都困难)里,只能一边产生组合,一边剪枝。
你给的第2个lua版本,是将产生所有组合的方式利用generator缓式化,对么? 当需要一个组合时,就resume得到一个, 再判断它与3的关系。

但在默认缓式求值的语言中, 连产生一个组合 —— bit32.totable —— 都是缓式的。
当你需要某个组合中的某个元素时,它的计算才会被求值。


缓式求值显然是有代价的,肯定需要计算本身(相对于计算结果)记录在某些地方。

但一个显然的好处是它将原先的产生组合的过程从整个dfs中剥离了出来。 这部分就可以复用。
也许这些函数式的可复用代码拼凑在一起后可能达到手工拼凑dfs的效果 —— 手工dfs也需要自己记录一些,比如i, selected, 递归也是利用函数调用栈。

能达到手工拼凑的例子有。比如count_if(elems, pred)。
haskell里 count_if 可以用 filter 与 length 定义, 并且filter 产生的中间list可以被消除。
http://stackoverflow.com/questio ... the-given-predicate
在其他语言里通常就不能这么干。

用缓式的totable拼出一个组合, 再缓式拼出所有组合, 这部分是范化的通用代码; 最后在它们的基础上编写逻辑相关的剪枝 —— 我不能肯定是否能达到手工将3者全写在一起的效率。
我觉得对你举的这个例子应该没戏……  至少在空间效率方面肯定败了。  需要保存的中间结果太小, 就一个N大小的数组……
而对一些逻辑更复杂的,并且是有经验的haskell程序员, 也许就可以。


BTW: 这也是bench不好做的一个例子。
haskell其实效率很高, 但需要有很深入的了解才知道它那些机制会产生怎样的代价, 这种代价与手写是否相同, 或者即使差一点也值得用运行时间来换开发时间?
haskell的效率很难估计, 它的抽象层次与机器相差太远了, 很容易写出低效的代码。

你前面举的那个gambit慢的文章, 就也许类似我看到过的一个说haskell慢的文章。 你猜他怎么比的……
它用一个不纯的而且是严格求值的函数式语言, 命令式地建一个大的hash表。 然后将这代码直译到haskell……

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-03-03 16:56 |显示全部楼层
回复 91# OwnWaterloo


    要不对这个问题你给个haskell代码?我也很好奇这是怎么做的。

缓式缓式,但是缓式也得有被求值的时候。这里最麻烦的是次序问题。缓式求值只能避过不必要的求值,却没有办法改变求值的逻辑顺序。这里的问题是。组合是**早就产生**的,我们是在已经产生后的组合上进行**筛选**,而dfs的情况下,组合是**延后产生**的,我们是确定产生的组合无效的前提下进行**剪枝**,这里的逻辑次序都不一样。一个是产生组合->验证组合,还有一个是验证组合->产生组合。就算是缓式求值,在第二个方案中,你也必须在列出组合以后再验证是不是合法组合,而合格验证过程对其后的产生、验证过程毫无好处。因此即使是缓式求值我也认为**完全**没有作用,这是算法上的问题,不是写法上的问题。

这就是我说的第二个算法完全没有价值的原因:它在**算法**上就杜绝了所有**实现**上的优化。因为它的顺序错了(先产生后验证,验证udi产生没有好处),一个相似的例子是朴素求素数和筛法,一个是产生并验证,效率低,一个直接跳,其实就是验证再产生。

我认为lisp是相同的问题,是先理论在实现,最后发现实现有问题,没法和计算机模型匹配。而其他语言是先考虑实现复杂度再抽象出理论。这样就和计算机模型兼容了,对计算机来说自然。但是这样就很考验一个人的理论水平了,不然就会变成ruby或者python式的patch语言。

这就是我举这个例子的含义。

对了,这个题你试着用haskell写写看哈,就当是教教我怎么写haskell呗。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-03-03 17:15 |显示全部楼层
回复 90# starwing83

比如我举的那个 define/set!(scheme), defun(common lisp/emacs lisp)与 set(emacs lisp)的比较。
这样吧…… 就举set/setq, 貌似cl与el都支持的。

有两种需求:
1. 需要设置某个变量的值, 该变量编译时可知
2. 需要设置某个变量的值, 该变量只有运行时才知道

set可以完成两种

  1. (set 'x 12) ; x => 12
  2. (set v 26) ; (eval v) => 26
复制代码
而setq就只能完成前一种。 在这个层面来说, 它是一种特殊化的set —— 编译时必须可知的set。
如果对一种范化机制的专门化使用, 能达到特殊机制的效率, 为什么还要提供那种特殊机制?


理由依然也有。 但其实是两种看待问题的方式。
例如scheme与lua支持尾调用优化, 而clojure不支持。 对一个纯函数式语言不支持尾调用优化是很要命的事, 所以它支持一种特殊的loop/recur, 然后将它翻译为goto。

如果换另一种角度看待loop/recur。
假设某种语言的尾调用优化支持并不完善, 但该语言依然鼓励程序员去使用, 因为总有一天这东西可以被完善。
而对那些必须不增长栈的尾调用, 可以将loop/recur当作一种询问: 这地方我确实需要它被优化, 编译器你能保证么?

还是以scheme与lua为例(支持尾调用优化的语言不多……),但它们都不支持:

  1. (define factorial
  2.   (lambda (x)
  3.     (if (> x 0) (* x (factorial (- x 1))) 1)))
复制代码
必须得显式地写出那个accumulator。
这确实不算是尾调用, 但这种模式实在是太常见, 为什么要程序员一次又一次去自己写那个accumulator? 编译器不能帮助翻译吗?

这时就可以让loop/recur作为一种询问,假设这样:

  1. (define factorial
  2.   (lambda (x)
  3.     (if (> x 0) (recur (* x (factorial (- x 1)))) 1)))
复制代码
编译器能将代码进行某种转换后,保证recur可以复用栈空间吗? 如果可以,就执行; 如果不可以, 那我人工转换, 直到某个版本支持这种转换。


这是两种看待问题的方式: 优先考虑程序员表达与优先考虑编译器实现 —— lisp与Fortran。
set比setq更范化, 所以优先提供前者, 并尽量让前者的专门化使用能达到后者的效率。
如果暂时没能达到, 可以让setq作为一种优化的hint。
如果这目标达到了无论是一开始就达到还是后续达到了再将setq废弃, 至少后续程序员就不需要了解setq这个东西。

而如果优先提供setq, 程序员就需要去找set, 或者根本就限制了程序员, 让他根本就想不到原来还可以这样。

用set/setq做类比, lisp已经在考虑setq的事情了。
r6rs里对翻译到C/JVM/CLI的实现方式来说, 要高效地实现尾调用优化确实很困难, 依然坚持将尾调用优化作为强制要求只是为了维持向后兼容。
类似的还有mutable/immutable cons/string。


最后, 即使添加了许多限制, 也依然没能伤害到lisp的精髓。
而且这种从一开始就考虑范化/通用化的设计的语言, 肯定比那些从一开始就只考一种又一种特殊化/专门化的设计的语言更简练。
它只在不得不特殊化的地方才做妥协。
lua的coroutine相比python的generator的例子你也清楚……

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-03-03 17:47 |显示全部楼层
回复 92# starwing83

你说的次序可以包含在产生内。
我都忘了你说的是要找=3还是找>=3的……  假设是找>=3吧。

你所说的剪枝是否是[1,1,1,?,?]后面4种组合肯定满足,不需要在验证了,直接产生?
[0,0,0,?,?]后面的4种组合肯定不满足,直接丢弃。

而如果一次产生一个完整的排列,比如[1,1,1,?,?]就被重复验证了4次,[0,0,0,?,?]同样?

可以不产生每个完整的排列,而直接产生决策树嘛……
不是验证一个完整的排列的序列, 而是验证产生排列的树, 如果没达到要求,直接放弃整个子树。
依然可以将产生与决策剥离。


嗯,产生完整排列的序列确实没希望了……

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2012-03-03 18:58 |显示全部楼层
紧急召唤瓜瓜来把你们两个禁言了,都歪到第10页了

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-03-03 20:53 |显示全部楼层
回复 94# OwnWaterloo


    是吧……

我说的第二种方式就是产生整个组合,而产生决策树说白了就是dfs。

论坛徽章:
0
发表于 2012-03-04 08:31 |显示全部楼层
本帖最后由 2gua 于 2012-03-04 08:32 编辑



歪题就此打住!继续者禁言!

论坛徽章:
0
发表于 2012-03-04 08:32 |显示全部楼层
回复 92# starwing83


    歪题就此打住!继续者禁言!

论坛徽章:
0
发表于 2012-03-04 08:33 |显示全部楼层
回复 94# OwnWaterloo


    歪题就此打住!继续者禁言!

论坛徽章:
2
2015年迎新春徽章
日期:2015-03-04 09:55:28IT运维版块每日发帖之星
日期:2016-07-29 06:20:00
发表于 2012-03-04 21:39 |显示全部楼层
帖子中给的链接 点不进去了.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP