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

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

ScalaC#CC++算法 
阅读更多
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是全部过滤好之后再计算，算法不同结果也就不同了。
分享到：
| Scala 讲座：献给追求创意兴奋的程序员(全 ...
评论
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大小会变化。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics