Haskell을 사용하면서 리스트를 사용하지 않는 경우는 거의 없다고 볼 수 있다.
리스트는 다루기 쉽고 강력한 자료 구조이지만, 만능은 아니다.
특히나 함수형 언어는 성능이 떨어진다고 비판을 받고는 하는데, 리스트는 그 구조 때문에 함수형 언어와 관계없이 느리다.
그러므로 성능이 신경 쓰인다면 리스트의 특성을 잘 이해하고서 사용해야 한다.
그 한 가지 예로서, 리스트를 다룰 때 자주 사용하는 함수 중 하나인 length
를 살펴보자.
Definition of length
함수 length
는 주어진 리스트의 길이를 재는 함수이다.
Haskell의 리스트는 길이 정보를 별도로 저장하지 않는 단순한 구현이다.
그도 그럴 것이 지연 계산법의 특성상, 리스트의 길이가 얼마나 될지는 그 리스트가 주어진 시점에서는 알 수 없기 때문이다.
거기에 무한 리스트도 당연하다시피 다루고 있는데, 리스트의 길이를 미리 파악할 수 없는 이상, 길이 정보가 리스트에 포함되지 않는 것은 당연하다고 볼 수 있다.
하지만 리스트의 길이는 자주 사용할 일이 있으니까 재어 볼 필요는 있고, 그를 위해서 length
함수가 존재한다.
그런데 이 length
함수로 길이를 재는 것이 비효율적이거나, 불가능한 경우가 있다.
length
함수의 구현은 매우 단순해서, 앞에서부터 하나하나 세어가는 재귀함수이다.
최신 버전의 length
는 다음과 같이 구현되어 있다.
length :: t a -> Int length = foldl' (\c _ -> c+1) 0
이 구현은 옛 버전에 비해서 일반화되었다1.
초심자가 읽고서 이해하기 힘든 괴기 무쌍한 정의인지라, 좀 더 옛날의 정의를 살펴보자.
length :: [a] -> Int length l = len l 0# where len :: [a] -> Int# -> Int len [] a# = I# a# len (_:xs) a# = len xs (a# +# 1#)
이건 최적화를 위해 몇 가지 손을 본 구현인데, 이건 copy & paste 해도 동작하지 않는다.2
최적화된 부분을 복원(…)하면 다음과 같다.
length :: [a] -> Int length l = len l 0 where len [] a = a len (_:xs) a = len xs (a + 1)
즉, 리스트의 요소를 하나하나 세어가면서 길이를 재는 것이다.
이것만 보면 당연하고 의심할 바 없는 정의이지만, 이게 문제가 되는 경우가 많다는 것이다.
언제 문제가 될까?
이 length
함수를 손쉽게 사용할 때 일어날 수 있는 잠재적인 문제점들은 매우 많다.
이 글에서는 지연 계산법에 관한 부분은 간단히 언급만 하고, 연산량에 관련된 부분만을 살펴보기로 하자.
Case 1: 지연 계산법 (lazy evaluation)
먼저, 지연 계산법에 관련된 부분이다.
다음과 같은 조건을 살펴보자.
if length [1..] == 1 then ... else ...
이건 당연히 False
이지만, 리스트의 길이가 무한하고, length
함수는 그 리스트를 무한히 따라가기 때문에 정지하지 않는다.
이 외에도 계산할 필요가 없어서 error를 발생시킬 필요가 없는데, length
함수를 사용해서 error를 발생시키는 경우가 있다.
사실 이 지연 계산법에 관한 부분을 더 깊게 다루어야 하지만, 상당히 길어지고 length
함수만이 관련된 것도 아니기에 다른 글에서 다루도록 하겠다.
Case 2: 연산량 문제 – 길이가 1인지 아닌지만 확인하고 싶은데
length
함수는 if
의 조건문 안에서 자주 사용하게 된다.
이를테면 일직선 상에 있는 바위의 위치가 들어있는 리스트를 받으면 그 바위 간의 거리를 돌려주는 함수를 생각해보자.
머리를 잘 쓰면 다음과 같은 구현을 작성하지 않고 훨씬 더 보기 좋게 만들 수 있지만, 초심자가 쓸 것 같이 써봤다.
getDistances list | null list = [] -- (1) | length list == 1 = [] -- (2) | otherwise = (second - first) : getDistances (tail list) -- (3) where first = head list second = head (tail list)
이 함수의 구현 자체에는 아무런 문제도 없다.
하지만 조건문을 하나하나 자세히 살펴보면 문제가 있다는 것을 알 수 있다.
먼저, (1)은 아무런 문제가 없다.
null
함수는 빈 리스트인지 아닌지를 확인하는 함수로, O(1)의 엄청나게 싼 연산이다.
(2)는 잠시 내버려두고 (3)을 살펴보자.
where
안에서 정의한 것을 몇 개 사용하고 있지만, (3)도 전부 O(1)의 엄청나게 싼 연산이다.
문제는, (2)의 조건문 length list == 1
이다.
length
함수는 그 구현을 보면 알겠지만, O(n)이다. (n은 리스트의 길이)
getDistances
함수는 (2)번 조건문에서 length
함수를 n번 불러내기 때문에, 결과적으로 getDistances
의 연산량은 O(n^2)가 된다.
간단한 함수가 말도 안 되는 연산량을 가지게 된 것이다.
물론 getDistances
의 구현 자체를 바꾸어버리면 되지만, 이번에는 length
의 문제를 살펴보는 게 목적이니까 내버려두자.
자, 생각해보면 어떤 리스트의 길이가 1인지 아닌지를 살펴보는 것은 역시 상당히 싼 연산일 것이 분명하다.
그렇다면, 어떤 리스트의 길이가 주어진 길이인지 아닌지만 살펴보는 함수를 만들면 될 것 갈다.
길이를 측정하는 함수 isLength
isLength
함수를 다음과 같이 구현해보았다.
isLength [] 0 = True -- (1) isLength [] _ = False -- (2) isLength _ 0 = False -- (3) isLength list len = isLength (tail list) (len-1) -- (4)
이 함수의 연산량은 O(min(n,len))이다. 위의 getDistances
에서 사용하는 경우에는 당연히 O(1)이다.
(3)은 없어도 동작하지만, 매우 긴 리스트가 올 경우를 생각하면 O(n)이 되기 때문에 있어야 한다.
isLength
를 사용한 getDistances
getDistances list | null list = [] -- (1) | isLength list 1 = [] -- (2) | otherwise = (second - first) : getDistances (tail list) -- (3) where first = head list second = head (tail list)
당연하지만, 거의 바뀐 점이 없다.
하지만 length
대신에 isLength
를 사용한 것 때문에 연산량은 O(n^2)에서 O(n)으로 획기적으로 줄어들었다.
Conclusion 1
기본적으로 제공되는 함수라고 하더라도 꼭 그 함수가 어떻게 구현되었는지 살펴보자.
Hackage에서 받은 라이브러리라면, 그 구현을 쉽게 찾아볼 수 있다. 하나하나 책갈피도 잘 달려있으니까 소스 코드를 검색할 필요도 없다.
Appendix 1: getDistances
의 다른 구현을 생각해보자.
더 나은 구현이 있다고 주장했으니까, 예를 하나 정도 들어야 할 것 같다.
일단 간략한 구현의 예를 들어보자.
Trial 1: use pattern matching
Pattern matching을 사용하면 길이를 잴 필요가 없다.
다음은, getDistances
를 pattern matching을 사용해서 그대로 옮겨놓은 구현이다.
getDistances' [] = [] getDistances' (_:[]) = [] getDistances' (x:y:zs) = (y - x) : getDistances' (y:zs)
Trial 2: one more step
getDistances'
를 살펴보면 알겠지만, 위에서부터 두 개의 조건은 한 개로 합칠 수 있다.
고쳐 써보면 다음과 같다.
getDistances'' (x:y:zs) = (y - x) : getDistances'' (y:zs) getDistances'' _ = []
확인해보면 잘 동작한다.
Question 1: 새로운 구현 getDistances''
와 length
를 개선한 본래의 getDistances
, 어느 쪽이 더 성능이 좋을까?
getDistances''
의 구현은 간단하고 보기 좋지만(?), 하나 걱정되는 부분이 있다.
문제는 patttern matching의 비용이 얼마나 되는지 잘 모르겠다는 것이다.
특히나 이건 컴파일러와 그 최적화 방법에 따라서 바뀔 수 있는 부분이기에 항상 맞아들어가지는 않는다.
criterion으로 측정해보면, 그렇게 큰 차이는 없지만, pattern matching을 사용하는 getDistances''
가 getDistances
보다 조금 더 빠르다. 측정 오차 수준은 아니지만, 유의미한 수준이기는 하다. 다만 아주 조금 빠르다.
Appendix 2: 비교 함수를 만들어보자.
isLength
는 길이가 딱 얼만큼인가만 확인할 수 있다.
하지만 당연하게도 길이가 더 긴지 짧은지를 확인하고 싶은 경우도 있다.
더 긴지 확인하는 경우와 짧은지를 확인하는 경우의 경계 조건이 미묘하게 다르지만, 그 정도는 모두 알고 있을 테니까 isShorter
의 경우만 소개한다.
isShorter _ 0 = False isShorter [] _ = True isShorter list n = isShorter (tail list) (n-1)
실제로 사용할때는 주어진 길이가 음수인지를 확인한다든지, 인수를 정격(strict)화 한다든지 몇 가지 간단한 최적화를 할 필요가 있다.