почему эта функция цикла такая медленная по сравнению с картой?

Я просмотрел исходный код карт, который в основном продолжает создавать ленивые последовательности. Я бы подумал, что перебор коллекции и добавление к переходному вектору будет быстрее, но, очевидно, это не так. Что я не понимаю в поведении производительности clojures?

;=> (time (do-with / (range 1 1000) (range 1 1000)))
;"Elapsed time: 23.1808 msecs"
;
; vs
;=> (time (doall (map #(/ %1 %2) (range 1 1000) (range 1 1000))))
;"Elapsed time: 2.604174 msecs"
(defn do-with
  [fn coll1 coll2]
  (let [end (count coll1)]
    (loop [i   0
           res (transient [])]
        (if
          (= i end)
            (persistent! res)
            (let [x (nth coll1 i)
                  y (nth coll2 i)
                  r (fn x y)]
              (recur (inc i) (conj! res r))) 
                  ))))

clojure lazy-sequences
person Core    schedule 05.08.2013    source источник

Ответы (1)


arrow_upward
14
arrow_downward

В порядке предполагаемого влияния на относительные результаты:

  1. Ваша функция do-with использует nth для доступа к отдельным элементам во входных коллекциях. nth работает в линейном времени на диапазонах, делая do-with квадратичным. Излишне говорить, что это убьет производительность на больших коллекциях.

  2. range создает фрагментированные последовательности, а map обрабатывает их чрезвычайно эффективно. (По сути, он создает фрагменты до 32 элементов — здесь их фактически будет ровно 32 — путем последовательного выполнения жесткого цикла по внутреннему массиву каждого входного фрагмента, помещая результаты во внутренние массивы выходных фрагментов.)

  3. Сравнительный анализ с помощью time не дает стабильной производительности. (Вот почему действительно следует использовать подходящую библиотеку для тестирования; в случае с Clojure стандартным решением является Criterium.)

Кстати, (map #(/ %1 %2) xs ys) можно просто записать как (map / xs ys).

Обновление:

Я сравнил версию map, исходную версию do-with и новую версию do-with с помощью Criterium, используя (range 1 1000) в качестве обоих входных данных в каждом случае (как в тексте вопроса), получив следующие средние значения времени выполнения:

;;; (range 1 1000)
new do-with           170.383334 µs
(doall (map ...))     230.756753 µs
original do-with       15.624444 ms

Кроме того, я повторил тест, используя вектор, хранящийся в Var, в качестве входных данных, а не диапазоны (то есть с (def r (vec (range 1 1000))) в начале и с использованием r в качестве обоих аргументов коллекции в каждом тесте). Неудивительно, что исходный do-with появился первым — nth очень быстро работает с векторами (плюс использование nth с вектором позволяет избежать всех промежуточных распределений, связанных с обходом последовательности).

;;; (vec (range 1 1000))
original do-with       73.975419 µs
new do-with            87.399952 µs
(doall (map ...))     153.493128 µs

Вот новый do-with с линейной временной сложностью:

(defn do-with [f xs ys]
  (loop [xs  (seq xs)
         ys  (seq ys)
         ret (transient [])]
    (if (and xs ys)
      (recur (next xs)
             (next ys)
             (conj! ret (f (first xs) (first ys))))
      (persistent! ret))))
person Michał Marczyk    schedule 05.08.2013
comment
Спасибо за подробный и развернутый ответ. Похоже, мне нужно больше знать о том, какой тип операции я выполняю с какой структурой данных. - person Core; 05.08.2013