Почему этот код сообщает о переполнении стека в Clojure - PullRequest
Новая
       15

Почему этот код сообщает о переполнении стека в Clojure

0 голосов
/ 29 августа 2018

Это простая попытка воспроизвести некоторый код, который Росс Ихака привел в качестве примера низкой производительности R. Мне было любопытно, будут ли постоянные структуры данных Clojure улучшаться. (https://www.stat.auckland.ac.nz/~ihaka/downloads/JSM-2010.pdf)

Тем не менее, я даже не добираюсь до первой базы, с сообщением о переполнении стека, и больше ничего не могу пройти. Есть идеи? Заранее извиняюсь, если на вопрос есть очевидный ответ, который я пропустил ... 

; Testing Ross Ihaka's example of poor R performance
; against Clojure, to see if persisntent data structures help

(def dd (repeat 60000 '(0 0 0 0)))

(defn repl-row [d i new-r]
   (concat (take (dec i) d) (list new-r) (drop i d)))

(defn changerows [d new-r]
  (loop [i 10000
         data d]
    (if (zero? i)
      data
      (let [j (rand-int 60000)
            newdata (repl-row data j new-r)]
        (recur (dec i) newdata)))))


user=> (changerows dd '(1 2 3 4))

StackOverflowError   clojure.lang.Numbers.isPos (Numbers.java:96)

Кроме того, если у кого-то есть идеи, как можно использовать постоянные функциональные структуры данных для наилучшего преимущества в приведенном выше примере, я бы очень хотел услышать. Ускорение, зарегистрированное не с использованием неизменяемых структур (ссылка выше), составило около 500%!

1 Ответ

0 голосов
/ 29 августа 2018

Если посмотреть на трассировку стека для StackOverflowError, это, кажется, проблема «взрывного потока» (отложенный / приостановленный расчет), которая явно не связана с рекурсией в вашем примере: 

java.lang.StackOverflowError
    at clojure.lang.RT.seq(RT.java:528)
    at clojure.core$seq__5124.invokeStatic(core.clj:137)
    at clojure.core$concat$cat__5217$fn__5218.invoke(core.clj:726)
    at clojure.lang.LazySeq.sval(LazySeq.java:40)
    at clojure.lang.LazySeq.seq(LazySeq.java:49)
    at clojure.lang.RT.seq(RT.java:528)
    at clojure.core$seq__5124.invokeStatic(core.clj:137)
    at clojure.core$take$fn__5630.invoke(core.clj:2876)

Изменение этой строки для преобразования newdata в вектор решает проблему: 

(recur (dec i) (vec newdata))

Этот обходной путь предназначен для использования concat в repl-row, заставляя ленивую последовательность concat реализовываться на каждом шаге. concat возвращает ленивые последовательности, и в ваших loop / recur вы передаете ленивые / неоцененные результаты предыдущих вызовов concat как входные данные для последующих вызовов concat, которые возвращают больше ленивых последовательностей на основе предыдущих, нереализованные ленивые последовательности. final concat -произведенная ленивая последовательность не реализуется до тех пор, пока цикл не завершится, что приводит к переполнению стека из-за его зависимости от тысяч предыдущих concat -произведенных ленивых последовательностей.

Кроме того, если у кого-то есть идеи, как можно использовать постоянные функциональные структуры данных для достижения максимального преимущества в приведенном выше примере, я бы очень хотел услышать.

Поскольку использование concat здесь, по-видимому, просто заменяет элемент в коллекции, мы можем получить тот же эффект, используя вектор и assoc -введя новый элемент в правильную позицию вектора: 

(def dd (vec (repeat 60000 '(0 0 0 0))))

(defn changerows [d new-r]
  (loop [i 10000
         data d]
    (if (zero? i)
      data
      (let [j (rand-int 60000)
            newdata (assoc data j new-r)]
        (recur (dec i) newdata)))))

Обратите внимание, что больше нет функции repl-row, мы просто assoc в data используем индекс и новое значение. После некоторого элементарного бенчмаркинга с time этот подход кажется во много раз быстрее: 

"Elapsed time: 75836.412166 msecs" ;; original sample w/fixed overflow
"Elapsed time: 2.984481 msecs"     ;; using vector+assoc instead of concat

И вот еще один способ решить эту проблему, рассматривая серию замен как бесконечную последовательность шагов замены, а затем производя выборку из этой последовательности: 

(defn random-replace [replacement coll]
  (assoc coll (rand-int (count coll)) replacement))

(->> (iterate (partial random-replace '(1 2 3 4)) dd)
     (drop 10000) ;; could also use `nth` function
     (first))
...