게으른 것이 나쁜 것만은 아닙니다.
Laziness, 즉 게으름은 보통 사람들에게 매우 부정적으로 인식되는 단어입니다. 비록 필연적으로 대부분의 사람들이 조금씩 게으름을 갖고 있으나 모두 극복해야 할 것으로만 생각하죠. 하지만 프로그래밍에서는 사뭇 다른 의미로 다가오는 단어입니다.
프로그래밍에서 게으르다는 것은 선언한 모든 것을 즉시 계산하여 메모리에 저장하는 것이 아니라 필요한 때가 되어서야 계산을 하는 것을 의미합니다. 마치 과제를 마감시간이 되어서야 몰아서 하는 우리의 모습과 비슷하죠. 그럼 당연하게도 의문점이 하나 생깁니다.
예를 하나 들어서 다음의 코딩 과제가 있다고 가정합시다.
코드는 참 간결합니다만, 이 코드를 실행시키면 Memory Error가 일어납니다. 1000억짜리 배열을 부지런히 만들고나서 첫 번째를 출력해야하는데 부지런히 만들다가 뻗어버린 것이죠. 보통의 언어들에서 위와 같은 코드를 짜면 대부분 에러를 출력할 것입니다. 대부분의 언어들은 부지런하기 때문이죠. 하지만 게으른 언어의 대표격인 Haskell에서는 심지어 무한 개의 수열에서도 첫 번째를 시간 하나 안들이고 출력할 수 있습니다.
코드는 아주 간결합니다. 실행도 아주 잘 됩니다. (head는 머리를 뜻하므로 배열의 맨 앞에 있는 값을 의미합니다.) Haskell은 모든 것이 게으르므로 필요하지 않은 것은 계산하지 않습니다. 우리에게 필요한 것은 head이므로 그 외에 나머지는 계산조차 하지 않죠. 마치 잔머리가 발달한 얌체를 보는 듯 하지만, 덕택에 좀 더 효율적인 작업이 가능해졌습니다. 하지만 신봉하는 것은 곤란합니다. 항상 게으른 것이 좋은 것은 아니니까요.
여하튼 좀 더 고급스러운 예시를 봅시다. Euler Project의 3번 문제입니다.
(Haskell 코드가 HTML에 먹혀 화살표는 진짜 화살표로 대체해야 했습니다.) 코드를 보면 알겠지만 primes는 isPrime을 호출하고 isPrime은 primes를 호출하는 상호재귀를 사용하고 있습니다. 그리고 Haskell에서 이는 아주 놀랍게도 정상작동합니다. 그것도 아주 빠르게 말이죠. 비법은 all함수와 takeWhile에 있습니다. 총 n개를 검사해야하는 것을 sqrt n개로 감소시킨 후 하나라도 만족하지 못한다면 false를 남발하는 all함수를 사용하면 아주 빠르게 검사가 가능하죠. (주어진 연속적인 구간에서 보통 소수보다 소수가 아닌 수가 많습니다.) 이것으로 코드를 짠다면 다음을 생각해 볼 수 있습니다.
takeWhile로 순회하는 시간이 4초가량 소요되고 코드 전체의 시간도 4초가량이므로 합리적입니다. 자 그럼 여기에 하나의 함수를 추가하여 봅시다.
간단히 요약하면 배열의 제일 앞에 있는 값 p에 대해 p가 m의 약수이면 m에서 p를 나눈 몫과 p를 다시 비교하고 그렇지 않다면 그 다음 값으로 넘어가서 다시 비교하자는 함수입니다. 이것으로 코드를 다시 짜면 다음과 같습니다.
어쨌거나 이 함수도 비교를 해야하는 함수니 기대되는 시간은 4초이상입니다. 하지만 실행해보면 0.01초 라는 경악스러운 결과가 나옵니다. 비법은 m이 p의 제곱보다 작을 때 [m]으로 하자는 첫째줄에 있습니다. m이 계속 나눠지다 p의 제곱보다 작아지는 그 순간, 모든 iteration은 멈추게 됩니다. 따라서 아무리 takeWhile이 계산하라고 강요해도 이 게으른 언어는 모든 작동을 멈춥니다. 뒤에 것들은 필요가 없으니까요. 마치 우리가 초등학교 중학교때 배웠던 소인수분해와 같죠.
이 게으름은 최신 개념인 것 같지만 나온 지 상당히 오래된 개념입니다. 하지만 공학이나 자연과학 계열의 사람들에게 낯선 개념인 것은 분명합니다. 하지만 분명히 쓰일 여지는 많습니다. 하나의 기대되는 바로 입자물리학을 하다보면 재규격화에서 무한대를 매번 다루게 되는데 계산하지 않고 마지막에 유효한 부분만을 대입하는 것을 보면 게으른 언어들과 일맥상통하므로 사용될 여지가 많을 것 같습니다. 자세한 건 시도해봐야 알겠지만 분명한 건 배워서 안 좋을 것은 없습니다.
프로그래밍에서 게으르다는 것은 선언한 모든 것을 즉시 계산하여 메모리에 저장하는 것이 아니라 필요한 때가 되어서야 계산을 하는 것을 의미합니다. 마치 과제를 마감시간이 되어서야 몰아서 하는 우리의 모습과 비슷하죠. 그럼 당연하게도 의문점이 하나 생깁니다.
몰아서 하는 것은 안 좋은 것 아닌가?언뜻 그렇게 생각할 수 있으나 좀 더 깊이 생각해봅시다. 미리미리 할 때의 우리는 시간이 많으므로 그 것이 나중에 어떻게 쓰일 지 모르지만 일단 하게 됩니다. 하지만 몰아서 할 때의 우리는 시간이 아주 부족하므로 요령을 부려 필요한 것만을 하게 됩니다. 그리고 그 것은 컴퓨터도 마찬가지입니다.
예를 하나 들어서 다음의 코딩 과제가 있다고 가정합시다.
1부터 1000억개의 배열의 맨 앞을 출력하여라.이것은 당연하게도 1입니다.하지만 코딩을 시키는 순간, 문제가 벌어집니다. 예시로 파이썬을 들어봅시다.
print [i for i in range(1,100000000001)][0]코드는 참 간결합니다만, 이 코드를 실행시키면 Memory Error가 일어납니다. 1000억짜리 배열을 부지런히 만들고나서 첫 번째를 출력해야하는데 부지런히 만들다가 뻗어버린 것이죠. 보통의 언어들에서 위와 같은 코드를 짜면 대부분 에러를 출력할 것입니다. 대부분의 언어들은 부지런하기 때문이죠. 하지만 게으른 언어의 대표격인 Haskell에서는 심지어 무한 개의 수열에서도 첫 번째를 시간 하나 안들이고 출력할 수 있습니다.
print $ head [1..]코드는 아주 간결합니다. 실행도 아주 잘 됩니다. (head는 머리를 뜻하므로 배열의 맨 앞에 있는 값을 의미합니다.) Haskell은 모든 것이 게으르므로 필요하지 않은 것은 계산하지 않습니다. 우리에게 필요한 것은 head이므로 그 외에 나머지는 계산조차 하지 않죠. 마치 잔머리가 발달한 얌체를 보는 듯 하지만, 덕택에 좀 더 효율적인 작업이 가능해졌습니다. 하지만 신봉하는 것은 곤란합니다. 항상 게으른 것이 좋은 것은 아니니까요.
여하튼 좀 더 고급스러운 예시를 봅시다. Euler Project의 3번 문제입니다.
간단히 번역하면 가장 큰 소인수를 찾는 문제입니다. 그냥 For문 등의 Iteration을 쓰면 간단하겠지만, 소수를 찾는 과정 자체에 또 Iteration이 들어가므로 6000억단위를 계산하다가는 Memory Error를 또 볼 수 있게 됩니다. 이는 상호재귀 를 이용함으로써 효율적으로 해결이 가능한데 Haskell 코드는 다음과 같습니다.The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
primes = 2 : [x | x ← [3..], isPrime x]
isPrime x = all (\p → rem x p > 0) (factorsToTry x)
where
factorsToTry x = takeWhile (\p→ p*p ≤ x) primes(Haskell 코드가 HTML에 먹혀 화살표는 진짜 화살표로 대체해야 했습니다.) 코드를 보면 알겠지만 primes는 isPrime을 호출하고 isPrime은 primes를 호출하는 상호재귀를 사용하고 있습니다. 그리고 Haskell에서 이는 아주 놀랍게도 정상작동합니다. 그것도 아주 빠르게 말이죠. 비법은 all함수와 takeWhile에 있습니다. 총 n개를 검사해야하는 것을 sqrt n개로 감소시킨 후 하나라도 만족하지 못한다면 false를 남발하는 all함수를 사용하면 아주 빠르게 검사가 가능하죠. (주어진 연속적인 구간에서 보통 소수보다 소수가 아닌 수가 많습니다.) 이것으로 코드를 짠다면 다음을 생각해 볼 수 있습니다.
primeFactors n = filter (\p → mod n p == 0) (takeWhile (\p → p*p ≤ n) primes)takeWhile로 순회하는 시간이 4초가량 소요되고 코드 전체의 시간도 4초가량이므로 합리적입니다. 자 그럼 여기에 하나의 함수를 추가하여 봅시다.
factors :: Integral a ⇒ a → [a] → [a]
factors 1 _ = []
factors m (p:ps) | m < p*p = [m]
| r==0 = p:factors q (p:ps)
| otherwise = factors m ps
where (q,r) = quotRem m p
간단히 요약하면 배열의 제일 앞에 있는 값 p에 대해 p가 m의 약수이면 m에서 p를 나눈 몫과 p를 다시 비교하고 그렇지 않다면 그 다음 값으로 넘어가서 다시 비교하자는 함수입니다. 이것으로 코드를 다시 짜면 다음과 같습니다.
primeFactors' n = factors n (takeWhile (\p → p*p ≤ n) primes)어쨌거나 이 함수도 비교를 해야하는 함수니 기대되는 시간은 4초이상입니다. 하지만 실행해보면 0.01초 라는 경악스러운 결과가 나옵니다. 비법은 m이 p의 제곱보다 작을 때 [m]으로 하자는 첫째줄에 있습니다. m이 계속 나눠지다 p의 제곱보다 작아지는 그 순간, 모든 iteration은 멈추게 됩니다. 따라서 아무리 takeWhile이 계산하라고 강요해도 이 게으른 언어는 모든 작동을 멈춥니다. 뒤에 것들은 필요가 없으니까요. 마치 우리가 초등학교 중학교때 배웠던 소인수분해와 같죠.
이 게으름은 최신 개념인 것 같지만 나온 지 상당히 오래된 개념입니다. 하지만 공학이나 자연과학 계열의 사람들에게 낯선 개념인 것은 분명합니다. 하지만 분명히 쓰일 여지는 많습니다. 하나의 기대되는 바로 입자물리학을 하다보면 재규격화에서 무한대를 매번 다루게 되는데 계산하지 않고 마지막에 유효한 부분만을 대입하는 것을 보면 게으른 언어들과 일맥상통하므로 사용될 여지가 많을 것 같습니다. 자세한 건 시도해봐야 알겠지만 분명한 건 배워서 안 좋을 것은 없습니다.
댓글
댓글 쓰기