Время выполнения программы Clojure

Question

Это Clojure программа для чтения целых чисел из файла и подсчета количества инверсий, т.е. сколько раз большее число появляется перед меньшим числом в последовательности Он реализует алгоритм O (n ^ 2) и требует около 30 минут для запуска на входе размером 100 000.

(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, если хотите получить это ускорение.
• Сокращение по сравнению с субвеком в настоящее время создает много временных объектов.В работе есть патч, чтобы исправить это (http://dev.clojure.org/jira/browse/CLJ-894), но вам, возможно, придется подождать Clojure 1.4 или 1.5 для этого.
• Это помогает сделать (set! *unchecked-math* true), чтобы улучшить производительность целочисленных операций (очевидно,вам нужно быть немного более осторожным, если возможны переполнения)

Если бы я хотел, чтобы это работало очень быстро в Clojure, я бы, вероятно, прибегнул к примитивным массивам и циклически с примитивными индексами:

(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"

т.е. этот код подсчитывает все инверсии в 100 000 целых чисел примерно за 16 секунд на моем компьютере (с Clojure 1.3)