Почему это не работает в постоянном пространстве (и как я делаю его так, оно делает)?
Я делаю Euler Проекта для изучения Clojure.
Цель этой функции состоит в том, чтобы вычислить LCM набора целых чисел от 1 кому: m.
(lcm 10) возвраты 2520
Это - способ довольно "в лоб" сделать это. В теории мы проходим каждое число от m к бесконечности и возврату первое число, для который все значения 1 через m разделите то число равномерно.
Если я понимаю то, что 'ленивый' означает правильно (и если я действительно ленив здесь), то это должно работать в постоянном пространстве. Нет никакой потребности содержать больше, чем список чисел от 1 кому: m и 1 значение от бесконечного множества чисел, что мы - цикличное выполнение через.
Я, однако, получаю a java.lang.OutOfMemoryError: Java heap space в m значения, больше, чем 17.
(defn lcm [m]
(let [xs (range 1 (+ m 1))]
(first (for [x (iterate inc m) :when
(empty?
(filter (fn [y] (not (factor-of? y x))) xs))] x))))
Спасибо!
4 ответа
Насколько я могу судить, ваш код на самом деле ленив (также в том смысле, что он не торопится с ответом ... ;-) - см. ниже), однако он создает груды за кучей мусора. Просто учтите, что (lvm 17) составляет более 1,2 миллиона операций ленивой фильтрации на (диапазон 1 18) . Я не могу воспроизвести вашу проблему нехватки памяти, но я предварительно предполагаю, что это может быть проблема с вашей памятью и настройками GC.
Теперь, хотя я понимаю, что ваш вопрос на самом деле не об алгоритмах, обратите внимание, что производство всего этого мусора, выполнение всех этих операций фильтрации и т. Д. Не только полностью разрушает пространственную сложность этого, но и временную сложность как хорошо. Почему бы не использовать реальный алгоритм LCM? Подобно тому, который использует lcm (X) = gcd (X) / product (X) для X набор натуральных чисел. НОД можно рассчитать с помощью алгоритма Евклида.
(defn gcd
([x y]
(cond (zero? x) y
(< y x) (recur y x)
:else (recur x (rem y x))))
([x y & zs]
(reduce gcd (gcd x y) zs)))
(defn lcm
([x y] (/ (* x y) (gcd x y)))
([x y & zs]
(reduce lcm (lcm x y) zs)))
С учетом вышеизложенного, (примените lcm (диапазон 1 18)) даст вам ваш ответ в кратчайшие сроки.
Я получаю ту же ошибку OutOfMemoryError на Clojure 1.1, но не на 1.2.
Я полагаю, что это ошибка в версии 1.1, когда для хранит больше мусора, чем необходимо.
Итак, я полагаю, что исправление заключается в обновлении Clojure. Или использовать алгоритм Михала для ответа за очень короткое время.
Михал прав насчет проблемы. Сито будет немного быстрее, так как вычисления GCD не требуются:
РЕДАКТИРОВАТЬ : Этот код на самом деле ужасно неверен. Я оставил это здесь, чтобы напомнить себе, что нужно дважды проверить свою работу, если у меня такое похмелье.
(ns euler (:use clojure.contrib.math))
(defn sieve
([m] (sieve m (vec (repeat (+ 1 m) true)) 2))
([m sieve-vector factor]
(if (< factor m)
(if (sieve-vector factor)
(recur m
(reduce #(assoc %1 %2 false)
sieve-vector
(range (* 2 factor) (+ 1 m) factor))
(inc factor))
(recur m sieve-vector (inc factor)))
sieve-vector)))
(defn primes [m] (map key (filter val (seq (zipmap (range 2 m) (subvec (sieve m) 2))))))
(defn prime-Powers-LCM [m] (zipmap (primes m) (map #(quot m %) (primes m))))
(defn LCM [m] (reduce #(* %1 (expt (key %2) (val %2))) 1 (seq (prime-Powers-LCM m))))
Хотя я согласен с тем, что это признано грубой силой, меня трясет от этой идеи. Для набора последовательных чисел, достигающего 50, lcm будет 3099044504245996706400. Вы действительно хотите, чтобы цикл, проверяющий каждое число до этого момента, определял lcm набора?
Другие схемы кажутся намного лучше. Например, разложите на множители каждый член последовательности, а затем просто подсчитайте максимальное количество вхождений каждого простого множителя. Или постройте простое сито простых чисел, которое одновременно множит множество чисел, позволяя вам подсчитывать кратности множителей.
Эти схемы можно записать так, чтобы они были высокоэффективными. Или вы можете использовать грубую силу. Последнее здесь кажется глупым.