S17

S-99: Ninety-Nine Scala Problemsを試してみる。
勉強のためにListのAPIはなるべく使わない方向。

view plainprint?

1. // P17 (*) Split a list into two parts.  
2. // The length of the first part is given. Use a Tuple for your result.  
3. // Example:  
4. // scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))  
5. // res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))  
6.   
7. // tail revursion but too slow  
8. def split_tail_too_slow[T](nth: Int, xs: List[T]) = {  
9.   def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {  
10.     case Nil => throw new NoSuchElementException  
11.     case l if (n == 0) => (acc._1, l)  
12.     case h :: t => recursive(n - 1, t, (acc._1 ::: List(h), Nil)) // add to tail -> O(n)  
13.   }  
14.   if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))  
15. }  
16.   
17. // tail revursion  
18. def split_tail_fast[T](nth: Int, xs: List[T]) = {  
19.   def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {  
20.     case Nil => throw new NoSuchElementException  
21.     case l if (n == 0) => (acc._1.reverse, l)  
22.     case h :: t => recursive(n - 1, t, (List(h) ::: acc._1 , Nil)) // add to head -> O(1)  
23.   
24.   }  
25.   if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))  
26. }  
27.   
28. def split_take[T](nth: Int, xs: List[T]): (List[T], List[T]) =  
29.   (xs.take(nth) , xs.takeRight(xs.length - nth))  
30.   
31. val l = (1 to 1000000).toList  
32. println(split_take(100000, l))  
33. println(split_tail_fast(100000, l))  
34. println(split_tail_too_slow(100000, l)) // 超遅い  

// P17 (*) Split a list into two parts.
// The length of the first part is given. Use a Tuple for your result.
// Example:
// scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
// res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))

// tail revursion but too slow
def split_tail_too_slow[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1, l)
    case h :: t => recursive(n - 1, t, (acc._1 ::: List(h), Nil)) // add to tail -> O(n)
  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

// tail revursion
def split_tail_fast[T](nth: Int, xs: List[T]) = {
  def recursive(n: Int, rest: List[T], acc: (List[T], List[T])): (List[T], List[T]) = rest match {
    case Nil => throw new NoSuchElementException
    case l if (n == 0) => (acc._1.reverse, l)
    case h :: t => recursive(n - 1, t, (List(h) ::: acc._1 , Nil)) // add to head -> O(1)

  }
  if(nth <= 0) throw new IllegalArgumentException else recursive(nth, xs, (Nil, Nil))
}

def split_take[T](nth: Int, xs: List[T]): (List[T], List[T]) =
  (xs.take(nth) , xs.takeRight(xs.length - nth))

val l = (1 to 1000000).toList
println(split_take(100000, l))
println(split_tail_fast(100000, l))
println(split_tail_too_slow(100000, l)) // 超遅い

３方式で書いてみた。

split_tail_too_slowはリストの最後尾に追加する。追加の度にリストをたどらなければならないので、再帰の度に遅くなる。O(n)
split_tail_fastはリストの先頭に追加するため、リストの要素数に関係なくO(1)
split_tail_takeはList APIを使ったバージョン。


100万個のリストで(10万, 90万)で分割（split_take以外の2つは10万回再帰）してみたところ、
split_tail_too_slowはいつまでたっても終わらなかった。

末尾再帰にすりゃいいってもんじゃないのね。勉強になりました。

解答例
ふむふむ、splitAtってのがあるのね。
match式にタプルを使えばいいのか。if式がいらなくなるのね。なるほど。