Clojure 프로그램 최적화

요즘 뜨고 있는 Clojure 프로그래밍 언어.

하지만 Clojure 프로그램은 대개 느리다.

Clojure 프로그램 최적화 기법이다.

Project Euler Problem 10을 예제로 사용한다.

[코드 시작]

(ns Euler.core (:gen-class))
(set! *warn-on-reflection* true)
(defn prime? [n]
  (loop [i 2]
    (if (<= (* i i) n)     
      (if (zero? (mod n i)) 
        false
        (recur (inc i)))
      true)))

(defn problem10 []
  (println (apply + (filter prime? (range 2 2000000)))))  

(defn primesUnder [limit]
  (let [p (transient (apply vector (repeat limit true)))]
    (doseq [i (range 2 (Math/sqrt limit))]
      (when (p i)
        (doseq [j (range (* 2 i) limit i)] (assoc! p j false))))
    (filter #(p %) (range 2 limit))))

(defmacro loopwhile [init-symbol init whilep step & body]
  `(loop [~init-symbol ~init]
     (when ~whilep ~@body (recur (+ ~init-symbol ~step)))))

(defn primesUnderb [limit]
  (let [p (boolean-array limit true)]
    (loopwhile i 2 (< i (Math/sqrt limit)) 1
               (when (aget p i)
                 (loopwhile j (* i 2) (< j limit) i (aset p j false))))
    (filter #(aget p %) (range 2 limit))))

(defn sum-primes-under [limit]
  (let [p (boolean-array limit true)]
    (loopwhile i 2 (< i (Math/sqrt limit)) 1
               (when (aget p i)
                 (loopwhile j (* i 2) (< j limit) i (aset p j false))))
    (loop [i 2, sum 0]
      (if (< i limit)
        (recur (inc i) (if (aget p i) (+ sum i) sum))
        sum))))

(defn sum-primes-under2 [^long limit]
  (let [p (boolean-array limit true)]
    (loopwhile i 2 (< i (Math/sqrt limit)) 1
               (when (aget p i)
                 (loopwhile j (* i 2) (< j limit) i (aset p j false))))
    (loop [i 2, sum 0]
      (if (< i limit)
        (recur (inc i) (if (aget p i) (+ sum i) sum))
        sum))))

(defn problem10a []
  (println (apply + (primesUnder 2000000))))
(defn problem10b []
  (println (apply + (primesUnderb 2000000))))
(defn problem10c []
  (println (sum-primes-under 2000000)))
(defn problem10d []
  (println (sum-primes-under2 2000000)))

;(time (problem10))
;(time (problem10a))
;(time (problem10b))
(time (problem10c))
(time (problem10d))

[코드 끝]

실행 결과:

142913828922
"Elapsed time: 52338.147726 msecs"
142913828922
"Elapsed time: 4935.037833 msecs"
142913828922
"Elapsed time: 834.170544 msecs"
142913828922
"Elapsed time: 513.571139 msecs"

142913828922
"Elapsed time: 115.802428 msecs"

먼저

(problem10): Clojure다운 가장 기본적인 방법이다. primes?를 써서 filter하고 합계

(problem10a)

그러나 소수를 구하는 빠른 방법은 Sieve of Eratosthenes를 사용하는 것이다.

=> 10배 향상

(problem10b)

loop를 doseq에서 일반 recur로 바꾸었다. doseq은 range로 만들어진 시퀀스를 순회하기 때문에..

중복 코드가 있어서 매크로를 작성하였다. (C의 for 문 흉내내기)

(defmacro loopwhile [init-symbol init whilep step & body]
  `(loop [~init-symbol ~init]
     (when ~whilep ~@body (recur (+ ~init-symbol ~step)))))

에라토스테네스의 체의 배열은 자바의 array를 사용하였다. (aget, aset)

=> 5배 향상 ㅋ

(problem10c)

우리가 필요한 것은 소수들의 합이지 소수들 목록이 아니다. 바로 합계를 내자.

=> 1.6배 향상 ㅋ

(problem10d)

type hint를 주었다. let 같은 데에서는 symbol의 type을 바로 알아내는데, 함수의 인자는 그렇지 않다. 함수의 인자로는 기본적으로 여러 타입이 넘어 올 수 있다고 보기 때문에 (set! *warn-on-reflection* true) 를 켜도 경고가 안 뜬다.

=> 4.5배 향상 ㅋ

그런데 이렇게 작성한 프로그램은 C로 짠 것과 비슷해지고 결국 Clojure의 장점을 살리지는 못하게 되는 결과를 초래한다. 오히려 C 버전보다 가독성이 떨어질 수도 있다.

(참고: C# 버전. 짝수 최적화가 들어가 있다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Euler {
    class Program {
        static void Main(string[] args) {
            const long pmax = 2000000;

            bool[] isPrime = new bool[pmax];
            for (long i = 2; i < pmax; i++) {
                isPrime[i] = true;
            }

            {
                const long i = 2;
                for (long j = 2 * i; j < pmax; j += i) {
                    isPrime[j] = false;
                }
            }

            for (int i = 3; i * i<= pmax; i += 2) {
                if (!isPrime[i]) continue;
                for (long j = 2 * i; j < pmax; j += i) {
                    isPrime[j] = false;
                }                
            }

            long sum = 0;
            for (int i = 2; i < pmax; i++) {
                if (isPrime[i]) sum += i;
            }
            Console.WriteLine(sum);
        }
    }
}

)