`
fineqtbull
  • 浏览: 51511 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类

for语句中内嵌if语句的副作用

阅读更多
Scala中的for(... if(...)){}和for(...) if(...){}语句是否是等价的呢?由于for语句的内部实现机制,决定了它们不是等价的。
例1:
scala>  def compress[T](l : List[T]): List[T] = {
     | var r = List(l.first)
     | for(x <- l) if (x != r.last) r = r ::: List(x)
     | r
     | }
compress: [T](List[T])List[T]

scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e,
     | 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)


例2:
scala>  def compress[T](l : List[T]): List[T] = {
     | var r = List(l.first)
     | for(x <- l if (x != r.last)) r = r ::: List(x)
     | r
     | }
compress: [T](List[T])List[T]

scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
     | )
res1: List[Symbol] = List('a, 'b, 'c, 'c, 'd, 'e, 'e, 'e, 'e)


上述例1得到了正确的结果,而例2却得到了不同的结果,那是为什么呢?那是由于例1的for语句被解释为
l.foreach{x => if(x != r.last) r = r ::: List(x) } 

例2的for语句则被解释为
l.filter(x => x != r.last).foreach{x => r = r ::: List(x)} 

例1中的x != r.last语句中的r每次迭代时都不同,而例2中由于用了filter语句,所以过滤时使用的是同一r的实例,也就是例1是边过滤边计算,而例2是全部过滤好之后再计算,算法不同结果也就不同了。
分享到:
评论
14 楼 fineqtbull 2009-10-09  
有一点感触,Scala语言的确很强大,同时包含了面向对象和函数式的功能,不过相比Java或Erlang等较纯粹的语言自身的复杂度也上升了。如果把Scala用在大规模的项目开发中,要是没有很好的编程规范的话,感觉还是很容易出问题的,特别是对于初入门的程序员来说。比如这里提到的for和case的副作用问题,一般初学者是不会意识到的,用测试用例来测的话,又会提高对覆盖率的要求。考虑是否在圈子里把与这些易出现问题相关的帖子集中一下,以方便刚入门者参考。
13 楼 RednaxelaFX 2009-10-09  
我那例子是在2.7.3上试的,但规范里说了match...case的顺序是不确定的,所以在新版本里结果不同也是可接受范围。事实上真像我那例子那样写的话那就是典型的broken code了……||||

fineqtbull 写道
还有night_stalker的例子:
引用
a match {case a if false => b; case c => d} // d  
a match {case a => if(false)b; case c => d} // Unit 

这个例子比较特殊,因该是由于if语句的位置不同而改变了控制流程吧。而且这里使用了返回类型的推断,如果是在实际程序里,我想编译器因该会帮我们找出类型不一致的问题吧。

这里关键是在于,作为guard的if不是结果表达式的一部分,所以不会影响结果的类型;没有匹配的else的if表达式,在Scala里类型就是Unit;Unit跟其它类型unify之后也还是Unit。如果要条件表达式确实有值的话,就要记得加上匹配的else子句。
12 楼 fineqtbull 2009-10-09  
谢谢night_stalker和RednaxelaFX的回复,很详细,一看就懂了 。不过执行结果在我的环境下有些不一致,我猜可能是版本的原因,如下:
Welcome to Scala version 2.7.5.final (Java HotSpot(TM) Client VM, Java 1.6.0_13)
scala> var i = List(1)
i: List[Int] = List(1)

scala> i match {
     |         case List(x) if ((i = List(2, 3), x == 2)._2) => x
     |         case List(x, y) => y
     |         case _ => 0
     |       }
res5: Int = 0


我也想了一下是什么导致了for和case语句的副作用呢?正如前面alanwu所说的,它们都引用了可变变量(var)。比如for的例子:
for(x <- l if (x != r.last)) r = r ::: List(x)

其中x != r.last是匿名函数,它包含了r这个外部可变变量,打破了函数对象的非可变性。
又比如case的例子:
case List(x) if ((i = List(2, 3), x == 2)._2) => x

假设RednaxelaFX的例子成立,则它是引用了可变变量i,并在内嵌if语句中改变了i的值。
还有night_stalker的例子:
引用
a match {case a if false => b; case c => d} // d  
a match {case a => if(false)b; case c => d} // Unit 

这个例子比较特殊,因该是由于if语句的位置不同而改变了控制流程吧。而且这里使用了返回类型的推断,如果是在实际程序里,我想编译器因该会帮我们找出类型不一致的问题吧。
11 楼 RednaxelaFX 2009-10-08  
night_stalker 写道
补充:改成 case `a` ……

呃,码字码到一半去吃饭,回来也没看到你已经回复了 T T
10 楼 RednaxelaFX 2009-10-08  
我下面写的都是在Scala 2.7.3上测试的。没追踪最新版本的动态……

fineqtbull 写道
night_stalker 写道
night_stalker 前天
case 里面的 if 也有类似的现象
case a if b => c 和 case a => if(b)c 也不一样。

ps:从来不用 for 语句 ……

可否详细说明一下,case a if b => c语句在Scala中是被如何解释的,与for的内嵌if语句有何相似之处。

附带问一下,不用for语句是由于性能原因吗?

case里的if也可以有副作用,可能改变被匹配的值;如果if是作为guard嵌在case条件里,那么它要是返回false,就会影响到其它case所匹配到的值;如果if是作为case匹配后的结果表达式的一部分,那么它就算返回false也不会使控制流掉到其它case中。这个是最大的区别。
假如我故意写:
scala> var i = List(1)
i: List[Int] = List(1)

scala> i match {
     |   case List(x) if ((i = List(2, 3), x == 2)._2) => x
     |   case List(x, y) => y
     |   case _ => 0
     | }
res1: Int = 3

就会看到诡异的副作用出现了。

另外一点,把if放在case的条件里,它的意义就是作为pattern的guard,所以不需要else——可以看成是它的“else”就是其它case。但把if作为结果的表达式的一部分的话,没有匹配的else就会影响类型推导,例如:
scala> val a = List(1, 2, 3)
a: List[Int] = List(1, 2, 3)

scala> a match {
     |   case List(x, y, z) if x == 1 => z
     | }
res1: Int = 3

scala> val b = a match {
     |   case List(x, y, z) => if (x == 1) z
     | }
b: Unit = ()

在该拿到值的地方拿到了Unit可就糗大了……||||

fineqtbull 写道
至于HotSpot优化部分没有怎么看懂,好像和由Scalac还是HotSpot来做inline有关系。

有几个方面。首先是说测试性能的计时方式,那帖里有人提出要正确预热再计时。其次是由泛型的类型擦除而带来的类型损失的问题。

关于预热。HotSpot默认是以“混合模式”来执行代码的——先解释执行所有代码,然后在发现“热”的代码时将它们编译为native code来执行。“热”的程度是通过方法被调用的次数,或者方法中的反向控制流(意味着循环)被执行的次数来判断的。HotSpot编译代码需要时间,而这部分时间算在性能测试的计时中比较不合适。而且,虽然HotSpot的JIT编译是以方法为单位,但编译却不一定是在目标方法的入口出发生的,而可能在目标方法执行过程当中发生;这样的话就会用到所谓“栈上替换”(on-stack replacement,OSR)的方式来从解释模式切换到native模式,代码的效率会比在方法入口正常编译的版本要差一些。所以为了得到比较接近现实中长时间运行的程序里的性能特征,正确预热有必要。

关于泛型与类型擦除。Scala编译器在许多时候都能知道可以用JVM支持的primitive type来生成更高效的代码。但由于Java是通过类型擦除来实现泛型的,换句话说在JVM层次上没有对泛型的直接支持,Scala在实现泛型的时候为了能更好的跟Java API整合,也只好用类型擦除法来实现泛型。这意味着Scala编译器拥有足够的类型信息去判断泛型的实际参数类型,但完成编译后,HotSpot却得不到那些信息,所有泛型参数都被替换为Object了。有些inlining如果由Scala编译器来做的话,就能够保持泛型的类型信息,从而输出更高效的代码,减轻HotSpot的负担。

例如说你要是写List(1, 2, 3).map(_ + 1),虽然我们知道_ + 1中的_肯定是Int,应该可以对应到JVM里的int类型,但List.map接收的参数是Function1,而Function1.apply被编译为字节码后的描述符是scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;,这样primitive type就要被装箱才能完成调用,效率也就低了。当前版本的Scala编译器会为这个_ + 1生成两个apply,一个是int参数类型的,进行实际的加法;另一个是Object参数类型的,把参数拆箱为int之后调用int参数类型的版本。
如果这个lambda由Scala编译器来完成inline的话,上述装箱就可以一定程度上被避免(虽然List还是泛型的所以有些地方还是得装箱)。
9 楼 night_stalker 2009-10-08  
补充:改成 case `a` ……
8 楼 night_stalker 2009-10-08  
case 的 if 子句为 false 时,会往下寻找其他匹配。
但一旦进入了 => 的右边,就不会寻找其他匹配了。
a match {case a if false => b; case c => d} // d
a match {case a => if(false)b; case c => d} // Unit


我觉得 foreach 就够用了 …… 而且 for 翻译后变成 foreach,何苦呢。
for(x <- xs) yield f(x) 的写法也不喜欢 …… 如果是 [ f(x) | x <- xs ] 就好了 ……
7 楼 fineqtbull 2009-10-08  
night_stalker 写道
night_stalker 前天
case 里面的 if 也有类似的现象
case a if b => c 和 case a => if(b)c 也不一样。

ps:从来不用 for 语句 ……

可否详细说明一下,case a if b => c语句在Scala中是被如何解释的,与for的内嵌if语句有何相似之处。

附带问一下,不用for语句是由于性能原因吗?
6 楼 fineqtbull 2009-10-08  
Eastsun 写道
fineqtbull 写道
Eastsun 写道

...

一年多前我在nabble发了一个相关的帖子:
A suggestion to optimize the for loops

好长的帖子呀,总算看完了,受益匪浅,赞一个 真是一石激起千层浪,一下子引出了这么多洋牛,个个功力深厚。看来你的算法在性能上还是被肯定了,不过正如那个帖子中所提到的,有无filter在逻辑上有差别(正如本帖提到的副作用),还是有与旧版本的兼容性问题。至于HotSpot优化部分没有怎么看懂,好像和由Scalac还是HotSpot来做inline有关系。还有一个闭包就对应一个下类这点感触较深,的确听到很多Scala编译慢的怨言,大概就和这有关吧。希望那个帖子中提到的优化方法能反映在Scala将来的版本中,做到正真的在性能上与Java不相上下。

David MacIver 貌似后来也加入了Scala2.8的创作,他对for语句的观点某些方面和我的是一致的;
那个bearfeeder 应该就是lift的作者,他认为“for性能本来就不好,也没必要去优化”,让人很是无语。
不过我怀疑将来版本中对for进行改进的可能性不大,可能有其他我没想到的理由(除了向后兼容性之外)

看来你对Scala还研究挺深的,期待你在论坛中能够发表更多见解 ,让我们这些低年级的能够分享一下前辈的知识。
5 楼 Eastsun 2009-10-07  
fineqtbull 写道
Eastsun 写道

...

一年多前我在nabble发了一个相关的帖子:
A suggestion to optimize the for loops

好长的帖子呀,总算看完了,受益匪浅,赞一个 真是一石激起千层浪,一下子引出了这么多洋牛,个个功力深厚。看来你的算法在性能上还是被肯定了,不过正如那个帖子中所提到的,有无filter在逻辑上有差别(正如本帖提到的副作用),还是有与旧版本的兼容性问题。至于HotSpot优化部分没有怎么看懂,好像和由Scalac还是HotSpot来做inline有关系。还有一个闭包就对应一个下类这点感触较深,的确听到很多Scala编译慢的怨言,大概就和这有关吧。希望那个帖子中提到的优化方法能反映在Scala将来的版本中,做到正真的在性能上与Java不相上下。

David MacIver 貌似后来也加入了Scala2.8的创作,他对for语句的观点某些方面和我的是一致的;
那个bearfeeder 应该就是lift的作者,他认为“for性能本来就不好,也没必要去优化”,让人很是无语。
不过我怀疑将来版本中对for进行改进的可能性不大,可能有其他我没想到的理由(除了向后兼容性之外)
4 楼 fineqtbull 2009-10-07  
Eastsun 写道

...

一年多前我在nabble发了一个相关的帖子:
A suggestion to optimize the for loops

好长的帖子呀,总算看完了,受益匪浅,赞一个 真是一石激起千层浪,一下子引出了这么多洋牛,个个功力深厚。看来你的算法在性能上还是被肯定了,不过正如那个帖子中所提到的,有无filter在逻辑上有差别(正如本帖提到的副作用),还是有与旧版本的兼容性问题。至于HotSpot优化部分没有怎么看懂,好像和由Scalac还是HotSpot来做inline有关系。还有一个闭包就对应一个下类这点感触较深,的确听到很多Scala编译慢的怨言,大概就和这有关吧。希望那个帖子中提到的优化方法能反映在Scala将来的版本中,做到正真的在性能上与Java不相上下。
3 楼 Eastsun 2009-10-07  
按照目前的Scala语言规范,
for(x <- e;if y) z
会被编译器转换为:
e.filter((x1,x2..,xn) => y).foreach{case x => z}

这里调用了filter,会产生一个新的对象,由此会造成一定的性能损失。
按我的理解,更好的方式是将上式转换为:
e.foreach{ case x if y =>z; case _ => }

一年多前我在nabble发了一个相关的帖子:
A suggestion to optimize the for loops
2 楼 night_stalker 2009-10-05  
case 里面的 if 也有类似的现象
case a if b => c 和 case a => if(b)c 也不一样。

ps:从来不用 for 语句 ……
1 楼 alanwu 2009-10-05  
有时候用着用着循环的列表大小变掉了但没注意,导致越界访问。

这里也说明了val的好处,不用担心collection大小会变化。

相关推荐

Global site tag (gtag.js) - Google Analytics