Быстрая векторная математика в Clojure / Incanter
В настоящее время я рассматриваю Clojure и Incanter как альтернативу R. (Не то, чтобы я не любил R, но просто интересно пробовать новые языки.) Мне нравится Incanter, и синтаксис мне нравится, но векторизованные операции довольно медленны по сравнению с например, для R или Python.
В качестве примера я хотел получить разность первого порядка вектора, используя векторные операции Incanter, карту Clojure и R. Ниже приведен код и сроки для всех версий. Как видите, R явно быстрее.
Заклинатель и Clojure:
(use '(incanter core stats))
(def x (doall (sample-normal 1e7)))
(time (def y (doall (minus (rest x) (butlast x)))))
"Elapsed time: 16481.337 msecs"
(time (def y (doall (map - (rest x) (butlast x)))))
"Elapsed time: 16457.850 msecs"
Р:
rdiff <- function(x){
n = length(x)
x[2:n] - x[1:(n-1)]}
x = rnorm(1e7)
system.time(rdiff(x))
user system elapsed
1.504 0.900 2.561
Так что мне было интересно, есть ли способ ускорить векторные операции в Incanter/Clojure? Также приветствуются решения, включающие использование циклов, массивов Java и / или библиотек из Clojure.
Я также опубликовал этот вопрос в группе Google Incanter, но пока без ответов.
ОБНОВЛЕНИЕ: Я отметил ответ Джоуни как принятый, см. Ниже мой собственный ответ, где я немного очистил его код и добавил некоторые тесты.
6 ответов
Вот реализация Java-массивов, которая в моей системе работает быстрее, чем ваш код R (YMMV). Обратите внимание на включение предупреждений об отражении, что важно при оптимизации производительности, и повторяющуюся подсказку типа на y (та, что в def, похоже, не помогла aset) и приведение всего к примитивным двойным значениям (dotimes гарантирует, что я примитивен).
(set! *warn-on-reflection* true)
(use 'incanter.stats)
(def ^"[D" x (double-array (sample-normal 1e7)))
(time
(do
(def ^"[D" y (double-array (dec (count x))))
(dotimes [i (dec (count x))]
(aset ^"[D" y
i
(double (- (double (aget x (inc i)))
(double (aget x i))))))))
Мои окончательные решения
После всех испытаний я нашел два слегка отличающихся способа сделать расчет с достаточной скоростью.
Сначала я использовал функцию diff с различными типами возвращаемых значений ниже приведен код, возвращающий вектор, но я также рассчитал версию, возвращающую двойной массив (заменить (vec y) на y) и Incanter.matrix (заменить (vec y) на матрицу y), Эта функция основана только на массивах Java. Это основано на коде Jouni с некоторыми дополнительными подсказками типа.
Другой подход заключается в выполнении вычислений с массивами Java и сохранении значений в переходном векторе. Как видно из таймингов, это немного быстрее, чем подход 1, если вы не хотите возвращать функцию и массив. Это реализовано в функции difft,
Таким образом, выбор действительно зависит от того, что вы не хотите делать с данными. Я думаю, что хорошим вариантом было бы перегрузить функцию, чтобы она возвращала тот же тип, который использовался в вызове. Фактически передача массива Java вместо diff вместо вектора делает ~1с быстрее.
Сроки для различных функций:
разность, возвращающая вектор:
(time (def y (diff x)))
"Elapsed time: 4733.259 msecs"
diff возвращает Incanter.matrix:
(time (def y (diff x)))
"Elapsed time: 2599.728 msecs"
diff возвращает двойной массив:
(time (def y (diff x)))
"Elapsed time: 1638.548 msecs"
difft:
(time (def y (difft x)))
"Elapsed time: 3683.237 msecs"
Функции
(use 'incanter.stats)
(def x (vec (sample-normal 1e7)))
(defn diff [x]
(let [y (double-array (dec (count x)))
x (double-array x)]
(dotimes [i (dec (count x))]
(aset y i
(- (aget x (inc i))
(aget x i))))
(vec y)))
(defn difft [x]
(let [y (vector (range n))
y (transient y)
x (double-array x)]
(dotimes [i (dec (count x))]
(assoc! y i
(- (aget x (inc i))
(aget x i))))
(persistent! y)))
Не относится к вашему примеру кода, но так как это превратилось в обсуждение производительности Clojure, вам может понравиться эта ссылка: Clojure - это быстро
В блоге Брэдфорда Кросса есть куча сообщений об этом (он использует этот материал для стартапа, он работает над текстом ссылки. В целом, используя переходные процессы во внутренних циклах, подсказывает тип (через *warn-on-reflection*) и т. д. все хорошо для увеличения скорости. В Joy of Clojure есть отличный раздел, посвященный настройке производительности, который вы должны прочитать.
Вот решение с переходными процессами - привлекательное, но медленное.
(use 'incanter.stats)
(set! *warn-on-reflection* true)
(def x (doall (sample-normal 1e7)))
(time
(def y
(loop [xs x
xs+ (rest x)
result (transient [])]
(if (empty? xs+)
(persistent! result)
(recur (rest xs) (rest xs+)
(conj! result (- (double (first xs+))
(double (first xs)))))))))
Пока все комментарии сделаны людьми, у которых, кажется, нет большого опыта в ускорении кода Clojure. Если вы хотите, чтобы код Clojure выполнялся так же, как и в Java, имеются возможности для этого. Тем не менее, может иметь больше смысла откладывать до зрелости библиотеки Java, такие как Colt или Parallel Colt, для векторной математики. Возможно, имеет смысл использовать массивы Java для итерации с абсолютной наивысшей производительностью.
Ссылка @ Шейна настолько полна устаревшей информации, что вряд ли стоит на нее смотреть. Также комментарий Шейна о том, что код медленнее, чем в 10 раз, просто неточен (и не поддерживается http://shootout.alioth.debian.org/u32q/compare.php?lang=clojure, и эти тесты не учитывают виды оптимизации возможны в 1.2.0 или 1.3.0-alpha1). Приложив немного усилий, обычно легко получить код Clojure с 4X-5X. Помимо этого обычно требуется более глубокое знание быстрых путей Clojure - что-то не так широко распространено, так как Clojure - довольно молодой язык.
Clojure довольно быстро. Но изучение того, как сделать это быстро, потребует небольшой работы / исследований, поскольку Clojure препятствует изменчивым операциям и изменяемым структурам данных.