Выполнение функции в Clojure 1.3

Question

Мне было интересно, может ли кто-нибудь помочь мне с производительностью этого фрагмента кода в Clojure 1.3.Я пытаюсь реализовать простую функцию, которая принимает два вектора и делает сумму продуктов.

Итак, предположим, что векторами являются X (размер 10 000 элементов) и B (размер 3 элемента), а сумма произведений хранится в векторе Y, математически это выглядит так:

Y0 = B0 * X2 + B1 * X1 + B2 * X0

Y1 = B0 * X3 + B1 * X2 + B2 * X1

Y2 = B0 * X4 + B1 * X3 + B2 *X2

и т. Д. ...

В этом примере размер Y в конечном итоге составит 9997, что соответствует (10 000 - 3).Я настроил функцию для принятия любого размера X и B.

Вот код: он в основном берет (count b) элементов за один раз из X, обращает его, отображает * на B и суммысодержимое результирующей последовательности для создания элемента Y.

(defn filt [b-vec x-vec]
  (loop [n 0 sig x-vec result []]
    (if (= n (- (count x-vec) (count b-vec)))
      result
      (recur (inc n) (rest sig) (conj result (->> sig
                                                  (take (count b-vec))
                                                  (reverse)
                                                  (map * b-vec)
                                                  (apply +)))))))

Если X равен (vec (range 1 10001)), а B равно [1 2 3], эта функция запускается приблизительно за 6 секунд.Я надеялся, что кто-то может предложить улучшения во время выполнения, будь то алгоритмическая или, возможно, языковая деталь, которой я мог бы злоупотреблять.

Спасибо!

PS Я сделал (set! *warn-on-reflection* true), но донне получите никаких предупреждений об отражении.

Answer 1

Вы используете количество раз, ненужное. Ниже код рассчитать счет только один раз

(defn filt [b-vec x-vec]
  (let [bc (count b-vec) xc (count x-vec)]
    (loop [n 0 sig x-vec result []]
        (if (= n (- xc bc))
          result
          (recur (inc n) (rest sig) (conj result (->> sig
                                                  (take bc)
                                                  (reverse)
                                                  (map * b-vec)
                                                  (apply +)))))))) 


(time (def b (filt [1 2 3] (range 10000))))
=> "Elapsed time: 50.892536 msecs"

Answer 2

Если вы действительно хотите максимальной производительности для такого рода расчетов, вы должны использовать массивы, а не векторы. Массивы имеют ряд преимуществ производительности:

• Они поддерживают индексированный поиск и запись O (1) - незначительно лучше, чем векторы, которые O (log32 n)
• Они являются изменяемыми, поэтому вам не нужно постоянно создавать новые массивы - вы можете просто создать один массив, который будет служить в качестве выходного буфера
• Они представлены в виде Java-массивов под капотом, так что воспользуйтесь различными оптимизациями массивов, встроенными в JVM
• Вы можете использовать примитивные массивы (например, Java double), которые намного быстрее, чем если вы используете объекты в штучной упаковке

Код будет выглядеть примерно так:

(defn filt [^doubles b-arr 
            ^doubles x-arr]
     (let [bc (count b-arr) 
           xc (count x-arr)
           rc (inc (- xc bc))
           result ^doubles (double-array rc)]
       (dotimes [i rc]
         (dotimes [j bc]
           (aset result i (+ (aget result i) (* (aget x-arr (+ i j)) (aget b-arr j))))))
       result))

Answer 3

Чтобы следовать превосходному ответу Анкура, вы также можете избежать повторных обращений к функции реверса, что дает нам еще большую производительность.

(defn filt [b-vec x-vec]
  (let [bc (count b-vec) xc (count x-vec) bb-vec (reverse b-vec)]
    (loop [n 0 sig x-vec result []]
        (if (= n (- xc bc))
          result
          (recur (inc n) (rest sig) (conj result (->> sig
                                                  (take bc)
                                                  (map * bb-vec)
                                                  (apply +))))))))