Created
April 15, 2011 17:45
-
-
Save netslow/922115 to your computer and use it in GitHub Desktop.
Compare tail recursion, list folding and classic approach
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package org.halfcup.scala | |
import scala.annotation._ | |
object TestTailRec { | |
def main(args: Array[String]): Unit = { | |
val list = List("one", "two", "three", "four", "five", "six", "seven", "eight", "nine","ten") | |
def maxWidth(s: List[String]) = { | |
var maxLength = 0 | |
for (str <- s) { | |
maxLength = maxLength.max(str.length) | |
} | |
maxLength | |
} | |
@tailrec | |
def maxWidthRec(s: List[String], max: Int): Int = { | |
s match { | |
case Nil => max | |
case _ => maxWidthRec(s.tail, max.max(s.head.length)) | |
} | |
} | |
def maxWidthFold(list:List[String]):Int = { | |
return list.foldLeft("")((s1, s2) => | |
if (s1.length > s2.length) s1 | |
else s2).length | |
} | |
for (i <- 1 to 100) { | |
val t3 = System.currentTimeMillis; | |
for (i <- 1 to 1000000) { | |
val max = maxWidth(list) | |
} | |
val t4 = System.currentTimeMillis - t3 | |
println("Simple: " + t4) | |
val t1 = System.currentTimeMillis; | |
for (i <- 1 to 1000000) { | |
val max = maxWidthRec(list, 0) | |
} | |
val t2 = System.currentTimeMillis - t1 | |
println("Tailrec:" + t2) | |
val t10 = System.currentTimeMillis | |
for (i <- 1 to 1000000) { | |
val max = maxWidthFold(list) | |
} | |
val t20 = System.currentTimeMillis - t10 | |
println("Fold: " + t20) | |
} | |
} | |
} |
On the other hand I get quite reasonable result when I run it from terminal:
Simple: 46
Tailrec:53
Fold: 47
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Sample output:
Simple: 221
Tailrec:182
Fold: 81