Scala '읽고 말하기 수열' 실습

Posted 2010.08.25 01:44
 스칼라 스터디 멤버가 읽고 말하기 수열(개미수열)을 실습 퀴즈로 출제했는데, 짧고 재밌는 예제인 듯 하여 공유합니다. 당연한 말이지만, 푸는 방법은 여러 가지가 존재하므로 참고만 하심 되겠습니다.
 
 개미 수열이라고도 알려진 '읽고 말하기(look-and-say) 수열'은, 나열된 숫자를 "숫자 x가 y개"와 같은 식으로 읽으면 수열이 완성됩니다. 예를 들어 [1,1,2] 를 주어진 형식에 맞게 읽으면  숫자 1이 2개, 숫자 2가 1개이지요. 이를 수열로 나타낸 [1,2,2,1]이 개미 수열입니다.

 저는 다음과 같이 작성하였습니다.
// co-ons operator (~:)
// ex) List(1,1,1,2,3) == 1 ~: List(2,3)
object ~: {
  def unapply(list:List[Int]):Option[(Int, List[Int])] = {
    list match {
      case Nil => None;
      case x::xs => Some((x, xs.dropWhile( _ == x )));
    }
  }
}
 
 
object AntSeq {
  def lookAndSay(list:List[Int]):List[Int] = {
    list match {
      case Nil => Nil;
      case x~:xs => x::(list.size-xs.size)::lookAndSay(xs)     //co-ons
    }
  }
}

 우선 정의한 ~: 를 살펴볼 필요가 있습니다. 개미 수열의 단위는 반복되는 특정수의 묶음 입니다. 예를 들어 List(1,1,1,2,2,3)을 놓고 보면, 개미수열을 만들기 위해서는 List(1,1,1), List(2,2), List(3)과 같이 나누어 각 수를 셈할 필요가 있습니다. (적어도 제 머리는 그렇게 수열을 해석하는 것 같습니다.)

 이렇게 "기준 묶음을 뽑아내어 개수를 읽고, 나머지는 같은 요령으로(재귀적으로)처리한다."는 것이 핵심입니다. 기준 묶음과 나머지로 분리하기 위해 리스트를 다뤄본 사람[각주:1]이라면 지겹게 봤을 :: (cons)와 유사한 기호의 ~:를 이름을 살짝 바꾸어(co-ons)라고 정의했습니다.

List(1,1,1,2,2,3) = 1~:List(2,2,3) = 1~:2~:3

 눈으로 보니 co-ons의 정의가 더 간단합니다. 이를 패턴 매칭에 활용하여 개미 수열을 읽으려고 했습니다. 실제로 해당 역할을 하는 단 한 줄(17번째 줄)이 문제 풀이의 핵심이네요.수행 결과는 다음과 같습니다.
scala> import AntSeq._
import AntSeq._
 
scala> lookAndSay(List(1,1,1,2,2,3))
res0: List[Int] = List(1, 3, 2, 2, 3, 1)

 패턴매칭을 잘 활용하면, 자신이 가진 생각을 간단한 기호나 패턴으로 만들고 추상화할 수 있습니다. 그리고 함수형 스타일로 프로그래밍하는데 익숙해지면 문제 해결이 좀 더 빨라집니다. 제 경우 함수형 프로그래밍에 그렇게 익숙한 편도 아닌데, co-ons연산자를 도출하는 과정까지 포함해서 문제 푸는데 걸린 시간은 그렇게 길지 않았습니다. "제 머리가 생각하는 방법과 실제 프로그래밍의 간극이 가까웠기 때문"이라 생각합니다. 만일 for나 중간의 각종 변수를 정의하는 등 imperative style로 풀었다면, (적어도 저의 경우엔) 훨씬 오래 걸렸을 듯합니다. 

 scala가 가진 표현력과 함수형 프로그래밍 스타일[각주:2]의 문제 해결 능력을 맛볼 수 있는 좋은 예제였습니다. 출제해 준 스터디 멤버에게 감사!
  1. lisp 방언이나 hakell 등을 배워본 경험이 있다면 cons가 익숙할 겁니다. 심지어 lisp은 문법 트리조차 cons를 기반으로 표현되는데, 이는 http://en.wikipedia.org/wiki/Homoiconicity를 참고합니다. [본문으로]
  2. 참고로 scala는 functional style과 impertative style을 모두 지원하는 hybrid 언어입니다. [본문으로]
저작자 표시 비영리 변경 금지
신고

Actor의 react와 receive

Posted 2010.08.08 00:07
Actor의 개념도 생소하지만, 특히 메시지 수신에 사용하는 reactor, receive 메서드는 헷갈리기 쉬운 듯합니다. stackoverflow에 일목요연하게 정리된 답변이 올라와 번역한 뒤 설명을 추가해 봤습니다. 스터디에서 해당 링크를 알려준 명수 맏형께도 감사합니다. 도움이 되었으면 좋겠군요. 본문에서는 존칭을 생략합니다.
 Actor의 기본적인 내용을 알고 있다고 가정하고, 메세지 수신에 사용되는 receive, react 두 개의 메서드를 비교해본다.

First, each actor waiting on receive is occupying a thread. If it never receives anything, that thread will never do anything. An actor on react does not occupy any thread until it receives something. Once it receives something, a thread gets allocated to it, and it is initialized in it.

Now, the initialization part is important. A receiving thread is expected to return something, a reacting thread is not. So the previous stack state at the end of the last react can be, and is, wholly discarded. Not needing to either save or restore the stack state makes the thread faster to start.

There are various performance reasons why you might want one or other. As you know, having too many threads in Java is not a good idea. On the other hand, because you have to attach an actor to a thread before it can react, it is faster to receive a message than react to it. So if you have actors that receive many messages but do very little with it, the additional delay of react might make it too slow for your purposes.
우선 receive로 동작하는 Actor 는 하나의 스레드를 차지한다. 만일 어떠한 메시지도 수신하지 않는다면, 해당 스레드는 아무 것도 하지 않을 것이다. 반면 react에 기반한 Actor는 메시지를 수신하기 전까지는 스레드를 차지하지 않는다. 메시지를 수신하면 비로소 스레드가 할당되고, 초기화를 수행한다.

초기화는 중요한 부분이다. receive를 사용하는 스레드는 무언가를 리턴한다고 가정하지만, react를 사용하는 스레드는 리턴을 아예 하지 않는다고 가정한다.

그렇다면 왜 두 가지 선택 사항이 존재하는가? 여기에는 성능과 관련된 여러 이유가 있다. 알고 있듯이, 자바에서 많은 스레드를 사용하는 것은 좋은 방법이 아니다. 하지만 react 기반의 actor는 react 수행 전 actor를 할당해야 하기 때문에, receive를 사용하는 쪽이 react를 사용하는 것보다 속도가 빠르다. 만일 많은 메세지를 수신하는데, 수신한 메시지를 기반으로 아주 작은 일만을 수행한다면, react에서 발생하는 추가적인 delay는 성능저하를 일으킬 수도 있다. 

 두 메서드는 일단 메서드의 반환 타입부터가 다르다. 특히 react는 다음과 같이 정의되어 있다.
def react(f : scala.PartialFunction[scala.Any, scala.Unit]) : scala.Nothing
 메서드가 Nothing 타입을 반환한다는 사실의 의미를 생각해보자. Nothing은 bottom type이기 때문에 Nothing을 상속한 서브 클래스는 존재할 수 없으며, Nothing 자체를 반환하려고 해도 abstract 클래스이기 때문에 불가능하다. 따라서 react 메서드는 값을 반환할 수 없고, react 내부에서는 예외를 발생시키거나 무한히 실행해야 한다. 애당초 react 메서드는 메서드를 종료하지 못해 해당 스레드를 유지할 수 밖에 없는 불쌍한(?) 운명인 것이다.

다음 코드를 실행해보자. react 종료 후 println("message processed!")는 수행되지 않는다. 물론 react대신 receive를 사용하면 이야기는 달라진다.
import scala.actors.Actor._

actor { 
  loop { 
    react { 
      case any => println(any) 
    } 
    println("message processed!"); 
}}
참고로 Actor.actor 메서드는 Actor를 생성하고 즉시 수행한다. 


저작자 표시 비영리 변경 금지
신고
« PREV : 1 : 2 : 3 : 4 : 5 : 6 : ··· : 44 : NEXT »

티스토리 툴바