Вы генерируете множество ленивых последовательностей, которые занимают пространство стека.
разбив его:
user=> (iterate inc 3)
;; produces first lazy seq (don't run in repl!)
(3 4 5 6 7 8 9 10 11 12 13 ...)
user=> (filter odd? (iterate inc 3))
;; again, don't run in repl, but lazy seq #2
(3 5 7 9 11 13 ...)
лично я сделал бы (iterate #(+ 2 %) 3) вырезать последовательность, но это капля в море по сравнению с общей проблемой.
Теперь мы начинаем в решето, который начинает создавать новый ленивый SEQ для нашего выхода
(lazy-seq
(cons 3 (sieve (drop-while nil? (assoc-nth '(5 7 9 ...) 3 nil)))))
Прыжков в ассоциативный энном, мы начинаем создавать более ленивые последовательности
user=> (partition 3 [5 7 9 11 13 15 17 19 21 23 25 ...])
;; lazy seq #4
((5 7 9) (11 13 15) (17 19 21) (23 25 27) ...)
user=> (map #(take 2 %) '((5 7 9) (11 13 15) (17 19 21) (23 25 27) ...))
;; lazy seq #5
((5 7) (11 13) (17 19) (23 25) ...)
user=> (interleave '((3 5) (9 11) (15 17) (21 23) ...) (repeat [nil]))
;; lazy seq #6 + #7 (repeat [nil]) is a lazy seq too
((5 7) [nil] (11 13) [nil] (17 19) [nil] (23 25) [nil] ...)
user=> (apply concat ...
;; lazy seq #8
(5 7 nil 11 13 nil 17 19 nil 23 25 nil ...)
Так уже у вас есть 8 ленивых последовательностей, и мы применили только первое сито.
Вернуться к решету, и это делает каплю в то время, которое производит ленивый порядковый номер 9
user=> (drop-while nil? '(5 7 nil 11 13 nil 17 19 nil 23 25 nil ...))
;; lazy seq #9
(5 7 11 13 17 19 23 25 ...)
Таким образом, для одной итерации решета, мы генерируемые 9 последовательностей.
В следующей итерации сита вы создаете новый ленивый seq (а не оригинал!), И процесс начинается снова, генерируя еще 7 последовательностей в петлю.
Следующая проблема заключается в эффективности вашей функции assoc-nth. Последовательность чисел и nils не является эффективным способом для обозначения кратных значений конкретного фактора. Вы очень быстро закончите очень много длинных последовательностей, которые не могут быть выпущены, в основном заполнены нулями, и вам нужно прочитать более длинные и длинные последовательности, чтобы решить, является ли кандидат фактором или нет - это неэффективно для ленивые последовательности, которые считывают фрагменты из 32 записей, чтобы быть эффективными, поэтому, когда ваш факторинг из 33 и выше, вы тянете несколько фрагментов последовательности для работы.
Также каждый раз, когда вы делаете это в совершенно новой последовательности.
Добавление некоторой отладки к вашему ассоциированному-n-му и ее запуск на небольшом образце быстро иллюстрируют это.
user=> (sieve (take 50 (iterate #(+ 2 %) 3)))
assoc-nth n: 3 , coll: (5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101)
returning r: (5 7 nil 11 13 nil 17 19 nil 23 25 nil 29 31 nil 35 37 nil 41 43 nil 47 49 nil 53 55 nil 59 61 nil 65 67 nil 71 73 nil 77 79 nil 83 85 nil 89 91 nil 95 97 nil)
assoc-nth n: 5 , coll: (7 nil 11 13 nil 17 19 nil 23 25 nil 29 31 nil 35 37 nil 41 43 nil 47 49 nil 53 55 nil 59 61 nil 65 67 nil 71 73 nil 77 79 nil 83 85 nil 89 91 nil 95 97 nil)
returning r: (7 nil 11 13 nil 17 19 nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 49 nil 53 nil nil 59 61 nil nil 67 nil 71 73 nil 77 79 nil 83 nil nil 89 91 nil nil)
assoc-nth n: 7 , coll: (nil 11 13 nil 17 19 nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 49 nil 53 nil nil 59 61 nil nil 67 nil 71 73 nil 77 79 nil 83 nil nil 89 91 nil nil)
returning r: (nil 11 13 nil 17 19 nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 nil nil 53 nil nil 59 61 nil nil 67 nil 71 73 nil nil 79 nil 83 nil nil 89 nil)
;; ...
assoc-nth n: 17 , coll: (19 nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 nil nil 53 nil nil 59 61 nil nil)
returning r: (19 nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 nil nil)
assoc-nth n: 19 , coll: (nil 23 nil nil 29 31 nil nil 37 nil 41 43 nil 47 nil nil)
returning r:()
(3 5 7 11 13 17 19)
Это показывает, как вам нужно все больше и больше элементов последовательности для получения списка простых чисел, так как я начал с нечетными номерами 3 до 99, но только в конечном итоге с простыми числами 3 до 19 лет, но на последнем итерации n = 19, в моей конечной последовательности было недостаточно элементов, чтобы вывести дальнейшие кратные.
Есть ли решение?
Я думаю, что вы ищете ответы на вопрос «как сделать ленивые последовательности лучше делать то, что я хочу?». В этом случае ленивые последовательности будут компромиссом. Ваш алгоритм работает, но генерирует слишком много стека. Вы не используете какой-либо recur, поэтому вы генерируете последовательности последовательностей. Первое, на что нужно обратить внимание, - это сделать ваши методы более рекурсивными и потерять некоторые последовательности. Я не могу предлагать решения для этого здесь, но я могу связать другие решения с одной и той же проблемой и посмотреть, есть ли области, которые они делают лучше, чем ваши.
Есть 2 достойных решения по номерам this implementation of Eratosthenes primes. Один использует диапазон и просеивает его, а другой использует массивы булевых (что на 40 раз быстрее). associated article с ним (в Japenese, но google хорошо переводится в Chrome) хорошо читается и показывает время наивных подходов к очень сфокусированной версии, используя массивы напрямую и набирайте подсказки, чтобы избежать дальнейших проблем с распаковкой в jvm.
Существует another SO question, который имеет хорошую реализацию с использованием переходных значений для повышения эффективности. У этого метода есть похожие методы фильтрации.
В каждом случае используются разные методы просеивания, которые избегают ленивых последовательностей, однако, поскольку существует предел сверху на простые числа, которые они генерируют, они могут обмениваться общими для эффективности.
Для несвязанного случая, посмотрите на this gist для бесконечной последовательности простых чисел. В моих тестах это было на 6 раз медленнее, чем предыдущий вопрос SO, но все еще довольно хорош. Однако реализация очень отличается.
Ваша реализация Сита Эратосфена не является хвостовой рекурсивной (функция 'recur' никогда не используется), поэтому это приведет к удалению стека. Clojure! = Lisp, поэтому, если вы скопировали реализацию из другой версии Lisp, вам придется переработать ее, чтобы сделать ее хвостовой рекурсивной в Clojure (и, честно говоря, я не вижу, как это было бы хвостом рекурсивно в другом Lisp) .. На первый взгляд кажется, что 'sieve' нужно будет переделать, чтобы сделать его хвостовым рекурсивным. Удачи. –
lazy-seq может устранить эту проблему с помощью непрямого обращения, так что здесь есть и другая проблема. – noisesmith
Мне не удалось воспроизвести переполнение стека, и ваш код кажется прекрасным. Когда я увеличиваю лимит от 500 до 1000, программа становится слишком медленной, чтобы я был достаточно терпелив, а использование кучи огромно. – Davyzhu