Вопрос новичка о куче и мусоре в Clojure - PullRequest
Новая
       33

Вопрос новичка о куче и мусоре в Clojure

7 голосов
/ 11 августа 2010

У меня есть вопрос о Clojure: я пытаюсь выучить язык, пройдя через Project Euler , и я не понимаю, что происходит под капотом: следующий код предназначен для использования returnсписок всех простых чисел до lim.Я бы подумал, что это должно быть O (n) в пространстве кучи, потому что я составляю список всех чисел до lim, а затем отфильтровываю их одно за другим, перемещая первое в новый список.(Я знаю, что я на самом деле делаю новые списки каждый раз, но я не думал, что они будут занимать больше памяти?) В любом случае, я запускаю это с 

(defn getAllPrimes [lim] 
  (defn getPrimes [primes numlist]
    (if (not-empty numlist) ;base case;
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
           (filter
        (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist
        (rest numlist)))
      primes)); return the primes
  (getPrimes () (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be emptied

И у меня остается все меньше места,Я звоню 

(apply + (getAllPrimes 2000000))

, но мне не хватает места на 

(apply + (filter even? (range 2000000)))

Так что я думаю, что я не должен понимать, как списки собирают мусор в вызовах для повторения ифактически используя O (n * n) кучу или что-то в этом роде.

1 Ответ

6 голосов
/ 11 августа 2010

Я считаю, что проблема в том, что с каждым повторением вы создаете новую ленивую последовательность, ссылающуюся на последнюю, поэтому после нескольких итераций вы держите seq, который содержит заголовок seq, который содержит заголовок последовательность, которая содержит голову последовательности. ... Все промежуточные последовательности заполняют вашу кучу.

Хотя написание простого сита является полезным упражнением, но если вы хотите получить ответ, Clojure действительно включает последовательность простых чисел в своей стандартной библиотеке: clojure.contrib.lazy-seqs / primes. Стандартное решение этой частной проблемы Эйлера - однострочник.

Как стиль, внутренняя защита не очень хорошая идея. Практический эффект такой же, как если бы defn находился на верхнем уровне, но если я не ошибаюсь, var переназначается при каждом вызове getAllPrimes, и переопределение vars во время выполнения очень сильно не рекомендуется. Поскольку код просто определяет переменную, getPrimes по-прежнему так же видим, как и getAllPrimes. В этом случае getPrimes может быть легко переписан как цикл / рекурс без внутренней функции, анонимной или именованной. Это не помогает вашей проблеме цепочки ленивых-seqs, но делает код немного более стандартным: 

(defn getAllPrimes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (filter (fn [x] (not (div? x (first numlist))))
                     (rest numlist)))
      primes)))

Я бы также избегал использования camelCase. Стандартное имя Clojure для этой функции: get-all-primes.

Однако, возвращаясь к практической проблеме, наименьшая работа, которую вы могли бы сделать, чтобы ваш код работал, заключалась в том, чтобы принудительно вызывать каждый seq на каждой итерации, т.е. заключать вызов фильтра в doall. Я попробовал это, и хотя он все еще работает медленно, он по крайней мере работает до завершения, не исчерпав кучи: 

(defn get-all-primes [lim]
  (loop [primes ()
         numlist (range 2 lim)]
    (if (not-empty numlist)
      (recur (cons (first numlist) primes)
             (doall (filter #(not (div? % (first numlist)))
                            (rest numlist))))
      primes)))
...