Clojure 프로그램의 실행 시간

Question

이것은 파일에서 정수를 읽고 역순 수, 즉 큰 숫자가 순서의 작은 숫자 앞에 나타나는 횟수를 계산하는 clojure 프로그램입니다. 그것은 O (n^2) 알고리즘을 구현하며, 크기가 100,000 인 입력을 실행하는 데 약 30 분이 걸립니다.

(defn count-inversions 
    [file] 
    (let [int-list (vec (map #(Integer/parseInt %) 
          (clojure.string/split (slurp file) #"\r\n")))] 
    (loop [c 0 
      t-list int-list] 
     (let [size (count t-list)] 
     (if (empty? t-list) 
     c 
     (recur (reduce #(if (< %2 (first t-list)) (inc %1) %1) c (subvec t-list 1 (dec size))) 
       (subvec t-list 1 (dec size)))))))) 

이 알고리즘은 Java에서 구현 될 때 완료하는 데 단지 몇 초가 걸립니다. 왜 그렇게 큰 차이가 있습니까? 나에게 잠재적으로 느린 볼

Answer 1

것들 (당신이 확실하게 벤치 마크해야하지만 ...)

• 귀하의 모든 번호가 박스된다. 이렇게하면 기본 요소를 사용하는 것보다 훨씬 느린 작업을 수행 할 수 있습니다. 그것은 매우 관용적이지는 않지만이 속도 향상을 원한다면 Clojure에서 원시 배열을 사용할 수 있습니다.
• subvec를 줄이면 현재 임시 개체가 많이 생성됩니다. 이 문제를 해결하기위한 패치가 있지만 (http://dev.clojure.org/jira/browse/CLJ-894) Clojure 1.4 또는 1.5를 기다려야 할 수도 있습니다.
는
• 은 정수 연산의 성능을 향상시키기 위해 (set! *unchecked-math* true)을하는 데 도움이 나는이 Clojure에 I에 정말 빨리 실행에 도착하고 싶다면 '

(분명히, 당신은 오버 플로우가 발생할 수있는 경우 좀 더 신중해야합니다) 아마 원시적 배열에 의존하고 원시적 인덱스 루핑 D : (Clojure의 1.3)이 코드 즉

(set! *unchecked-math* true) 

(defn count-inversions [coll] 
    (let [^ints integers (int-array coll) 
      size (long (count integers))] 
     (loop [c (long 0) 
       i (long 0)] 
     (if (>= i size) 
      c 
      (recur 
      (loop [c (long c) 
        v (aget integers i) 
        j (inc i)] 
       (if (>= j size) 
       c 
       (recur (long (if (> v (aget integers j)) (inc c) c)) v (inc j)))) 
      (inc i)))))) 

(time (count-inversions (for [i (range 100000)] (rand-int 100)))) 
"Elapsed time: 16036.651863 msecs" 

내 컴퓨터에 약 16 초 만에 10 만 개 정수의 모든 반전을 중요한 것은