Вопрос для начинающих о куче и мусоре в Clojure

Question

Вопрос для начинающих о куче и мусоре в Clojure

У меня вопрос по Clojure: Я пытаюсь выучить язык с помощью прохожу через Project Euler , и я не понимаю, что происходит под капотом: Следующий код предназначен для использования возврата списка всех простых чисел до 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) или что-то в этом роде.

7

clojure heap primes tail-recursion

задан Peter Mortensen 29 August 2010 в 23:53

1 ответ

Другие вопросы по тегам:

clojure heap primes tail-recursion

Похожие вопросы:

score 6 · Accepted Answer

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

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

С точки зрения стиля, внутреннее определение - не лучшая идея. Практический эффект такой же, как если бы defn был на верхнем уровне, но, если я не ошибаюсь, var переназначается каждый раз, когда вызывается getAllPrimes, и переопределение переменных во время выполнения очень не рекомендуется. Поскольку код просто определяет переменную, getPrimes по-прежнему отображается так же, как и getAllPrimes. В этом случае getPrimes можно легко переписать как цикл / повтор без внутренней функции, анонимной или именованной. Это не решает проблему с цепочкой lazy-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.

Возвращаясь к практической задаче, наименьшая работа, которую вы могли бы сделать, чтобы заставить ваш код работать, - это форсировать каждую последовательность на каждой итерации, то есть заключить вызов фильтра в 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)))