Почему это не работает в постоянном пространстве (и как я могу это сделать так)?

Я запускаю Project Euler для изучения Clojure.

Цель этой функции - вычислить lcm набора целых чисел от 1 до m.

(lcm 10) возвращает 2520

Это довольно грубый способ сделать это. Теоретически мы проходим каждое число от m до бесконечности и возвращаем первое число, для которого все значения 1 через m равномерно делят это число.

Если я понимаю, что "ленивый" означает правильно (и если я действительно ленив здесь), тогда это должно работать в постоянном пространстве. Нет необходимости хранить больше, чем список чисел от 1 до m и 1 значение от бесконечного набора чисел, которые мы перебираем.

Я получаю 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))))

Спасибо!

Ответ 1

Насколько я могу судить, ваш код на самом деле ленив (также в том смысле, что он не спешит достичь ответа...;-) - см. ниже), однако он генерирует сваи на сваи на сваях мусора. Просто подумайте, что (lvm 17) составляет более 1,2 миллиона ленивых фильтрующих операций на (range 1 18). Я не могу воспроизвести вашу проблему с отсутствием памяти, но я предположительно предположил, что это может быть проблемой с настройками вашей памяти и GC.

Теперь, хотя я понимаю, что ваш вопрос на самом деле не связан с алгоритмами, обратите внимание, что производство всего этого мусора, выполнение всех этих фильтрующих операций и т.д. не только полностью уничтожают космическую сложность этого, но и сложность времени как Что ж. Почему бы не использовать фактический алгоритм LCM? Как и тот, который использует lcm(X) = gcd(X) / product(X) для X набор натуральных чисел. GCD можно вычислить с помощью алгоритма Евклида.

(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)))

С учетом вышеизложенного (apply lcm (range 1 18)) даст вам ваш ответ в коротком порядке.

Ответ 2

Я получаю тот же OutOfMemoryError на Clojure 1.1, но не на 1.2.

Я предполагаю, что это ошибка в версии 1.1, где for содержит больше мусора, чем необходимо.

Поэтому я предполагаю, что исправление заключается в обновлении Clojure. Или использовать алгоритм Михала для ответа за долю времени.

Ответ 3

Хотя я признаю, что это признано грубой силой, я дрожу от идеи. Для набора последовательных чисел, который работает до 50, lcm равен 3099044504245996706400. Действительно ли вы хотите, чтобы цикл, который проверяет каждое число до этой точки, идентифицирует lcm набора?

Другие схемы выглядят намного лучше. Например, запомните каждый член последовательности, а затем просто подсчитайте максимальное количество вхождений каждого простого фактора. Или, постройте простое правое сито, которое одновременно множится в наборе чисел, позволяя вам учитывать коэффициенты кратности.

Эти схемы могут быть написаны как высокоэффективные. Или вы можете использовать грубую силу. Последнее кажется глупым здесь.

Ответ 4

Михал правильно относится к проблеме. Сито будет немного быстрее, так как никакие вычисления gcd не нужны:

EDIT. Этот код на самом деле ужасно ошибочен. Я оставил его здесь, чтобы напомнить себе, чтобы проверить свою работу дважды, если у меня такое похмелье.

(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))))