Как построить ленивую последовательность совершенного числа в Clojure?

Question

Я пытался найти список идеального числа таким образом:

(defn classify [num] 
    (let [factors (->> (range 1 (inc num)) 
        (filter #(zero? (rem num %)))) 
     sum (reduce + factors) 
     aliquot-sum (- sum num)] 
    (cond 
     (= aliquot-sum num) :perfect 
     (> aliquot-sum num) :abundant 
     (< aliquot-sum num) :deficient))) 

(defn is-p [n] 
    (= :perfect (classify n))) 

(defn list-perfect [n] 
    (filter is-p (range 1 (inc n)))) 

Вопрос:

1. Как построить ленивый последовательность совершенных чисел, так что я могу использовать (take n ...) легко получить список.

2. Является ли этот код идиоматичным и эффективным? Любое улучшение?

Заранее спасибо.

Answer 1

list-perfect уже ленивый из-за ваше использование filter:

(фильтр) пред сб

Возвращает ленивую последовательность элементов в Coll, для которых (пункт преда) возвращает истину. pred должно быть свободным от побочных эффектов.

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

Answer 2

Ваш алгоритм очень неэффективен, это O(n).

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

Так изменить его на:

(defn classify [num] 
    (let [factors (->> (range 1 (max 2 (inc (quot num 2)))) 
    ;; ... 

Однако ... вы можете изменить его на O(sqrt n) который магнитуды быстрее. См. Мои тайминги ниже.

Реальная эффективность заметив, что факторы в парах [x (quot num x)], а затем только проверить первый (sqrt num) (или чуть больше):

(defn perfect? [n] 
    (let [r (range 2 (+ 2 (int (Math/sqrt n)))) 
     s (set (mapcat #(if (zero? (rem n %)) 
          [% (quot n %)]) 
         r)) 
     t (reduce + 1 s)] 
    (= n t))) 

Я разделить его на отдельные расчеты, так что вы можете проверить каждый этап ,

Диапазон может быть уменьшен с 2 .. ((sqrt n) + 2) и инициализировать сокращение с помощью 1 (что всегда является фактором).

Это изменяет проблему с O (n) до O (sqrt n), поэтому, если вы проверяете большие числа, это имеет огромное значение.

В качестве иллюстрации здесь в несколько раз на больших значений для п на моем MBP:

  n   "n/2"  "sqrt n" 
     33550336  1,172.5ms  2.85ms 
    8589869056  274,346.6ms 16.76ms 
    137438691328  didn't time 44.27ms 

поэтому использование корневой версии был 16,369 раз быстрее 6 совершенное число. См. http://en.wikipedia.org/wiki/List_of_perfect_numbers для более подробной информации.

EDIT:

Почему (интермедиат (корень п)) + 2? И почему `[x (n n)]?

Когда вы работаете факторы число п, то, если вы найдете один (скажем, a), то n/a также фактор (назовем его b), потому что n = a * b

например глядя на 28, первый соответствующий коэффициент равен 2, и, очевидно, 28/2 = 14 также является фактором. Поэтому вам не нужно проверять 14, вы уже знаете, что это фактор из-за того, что 2.

, как мы пошагово проверки чисел от 2 вверх, мы попутно находя все большего числа сходящий:

2 is a factor, 28/2 = 14 -> [a, b] = [2, 14] 
4 is a factor, 28/4 = 7 -> [a, b] = [4, 7] 
7 is a factor, 28/7 = 4 -> [a, b] = [7, 4] - wait a minute... 

The [a,b] пары здесь в [% (quot n %)] в функции mapcat, например, когда диапазон в настоящее время итерируя значение 2, то % является 2 внутри Fuction, и так (quot n %) является (quot 28 2), который является 14, таким образом, [% (quot n %)] просто вектор [2 14], который затем будет добавлен к набору после того, как сплющенные к 2 и 14 как значения. Позже, когда значение диапазона составляет 4, тогда [% (quot n %)] - [4 (quot 28 4)], который равен [4 7], и снова сплющается mapcat как цифры 4 и 7.

Таким образом, мы добавляем каждую пару чисел (сплющенных через mapcat) к нашему набору, включаем номер 1 и заканчиваем #{1 2 14 4 7}, которые являются факторами 28. (На самом деле, я не ставил 1 в набор как мне не нужно, вместо этого я начинаю сокращение суммирования на 1, что является таким же эффектом).

Но в какой момент они обернутся? то есть, когда мы узнаем, что [7,4] уже были включены в комплект как [4,7]?

ясно, что это a>b, потому что при поиске наименьших чисел мы всегда находим с ним наибольшее число, поэтому мы можем закончить проверку на этом этапе.

но что это точка? это просто, если идеальное число было квадратным числом, то a и b были бы равны, то есть a * a = n, поэтому a = sqrt (n).

Таким образом, наибольшее значение a необходимо проверить, это целое число, которое больше, чем корень n.

например. для 28, sqrt (28) = 5,292, поэтому мы должны проверить 6, чтобы убедиться, что мы включили самое низкое возможное число, которое может быть фактором, который имеет парный коэффициент.

так что нам нужно (INT (SQRT п)) + 1.

Я всегда делаю это в случае, если расчет корень 1,9999999999 ... и округляет неправильный путь, так что добавление 1 больше гарантирует, что вы устранить любые ошибки округления ,

но в диапазоне, если вы хотите включить это число, вам нужно добавить еще 1 к нему (диапазон уменьшает высокое число, (диапазон 6) = (0 1 2 3 4 5)), следовательно, почему он добавляет 2 к значению: 1 для диапазона, 1, чтобы обеспечить его над закругленным корнем.

Хотя, сказав это, я проверил идеальные номера до 2305843008139952128, и он работает с +1 вместо +2, а не с тем, что это огромная экономия. Вероятно, потому что не идеальные числа близки к идеальным квадратам в тех, которые я проверил, поэтому в (int (sqrt n)) ошибки округления нет.

Если вы заинтересованы в совершенных чисел, я рекомендую прочитать http://britton.disted.camosun.bc.ca/perfect_number/lesson1.html