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

Question

Я делаю 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))))

Спасибо!

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

Михал прав насчет проблемы. Сито будет немного быстрее, так как не нужны вычисления 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))))