Различные решения для Clojure реализации проблемы

Question

Вот проблема Положение:

Определите процедуру, которая принимает три числа в качестве аргументов и возвращает сумму квадратов двух больших чисел.

Решение длинное,

(defn large [x y]
(if (> x y) x y))

(defn large-3 [x y z]
(if(> (large x y) z) (large x y) z))

(defn small [x y]
(if (< x y) x y))

(defn small-3 [x y z]
(if (< (small x y) z ) (small x y) z))

(defn second-largest [x y z]
  (let [greatest (large-3 x y z)
    smallest (small-3 x y z)]
    (first (filter #(and (> greatest %) (< smallest %)) [x y z]))))

(defn square [a]
  (* a a)
)

(defn sum-of-square [x y z]
  (+ (square (large-3 x y z)) (square (second-largest x y z))))

Просто хотел узнать, какими разными / лаконичными способами можно решить эту проблему в Clojure.

Answer 1

(defn foo [& xs]
  (let [big-xs (take 2 (sort-by - xs))]
    (reduce + (map * big-xs big-xs))))

Answer 2

; почему только 3? как насчет N

(defn sum-of-squares [& nums]  
  (reduce + (map #(* % %) (drop 1 (sort nums)))))

или, если хотите, "сумма двух самых больших чисел:

(defn sum-of-squares [& nums]  
  (reduce + (map #(* % %) (take 2 (reverse (sort nums))))))

(взять 2 (обратный (сортировка чисел))) из ответа Михаила Марчика.

Answer 3

(См. Последовательную версию проблемы вместе с отложенным решением во втором обновлении этого ответа ниже.)

(defn square [n]
  (* n n))

;; generalises easily to larger numbers of arguments
(defn sum-of-larger-squares [x y z]
  (apply + (map square (take 2 (reverse (sort [x y z]))))))

;; shorter; generalises easily if you want
;; 'the sum of the squares of all numbers but n smallest'
(defn sum-of-larger-squares [x y z]
  (apply + (map square (drop 1 (sort [x y z])))))

Обновление:

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

(defn sum-of-larger-squares [n & xs]
  (apply + (map square (take n (reverse (sort xs))))))

Вторая версия прямо обобщает версию, опубликованную тем временем Артуром:

(defn sum-of-larger-squares [n & xs]
  (apply + (map square (drop n (sort xs)))))

Кроме того, я видел точно такую ​​же проблему, решаемую в Схеме, возможно, даже в SO ... Она включала несколько забавных решений, таких как вычисление некоторых из всех трех квадратов, затем вычитание наименьшего квадрата (это очень прямолинейно выразить с помощью примитивов Scheme). Это «неэффективно» в том смысле, что он вычисляет один дополнительный квадрат, но он, безусловно, очень удобочитаемый. К сожалению, сейчас не могу найти ссылку.

Обновление 2:

В ответ на комментарий Артура Ульфельдта по этому вопросу, ленивое решение (надеюсь, забавной) другой версии проблемы . Сначала код, пояснение ниже:

(use 'clojure.contrib.seq-utils) ; recently renamed to clojure.contrib.seq

(defn moving-sum-of-smaller-squares [pred n nums]
  (map first
       (reductions (fn [[current-sum [x :as current-xs]] y]
                     (if (pred y x)
                       (let [z (peek current-xs)]
                         [(+ current-sum (- (* z z)) (* y y))
                          (vec (sort-by identity pred (conj (pop current-xs) y)))])
                       [current-sum
                        current-xs]))
                   (let [initial-xs (vec (sort-by identity pred (take n nums)))
                         initial-sum (reduce + (map #(* % %) initial-xs))]
                     [initial-sum initial-xs])
                   (drop n nums))))

Библиотека clojure.contrib.seq-utils (или c.c.seq) предназначена для функции reductions. Вместо этого можно использовать iterate, но не без некоторой дополнительной сложности (если только вы не захотите вычислить длину последовательности чисел, которая будет обрабатываться в начале, что будет противоречить с целью остаться как можно более ленивым ).

Пояснение с примером использования:

user> (moving-sum-of-smaller-squares < 2 [9 3 2 1 0 5 3])
(90 13 5 1 1 1)

;; and to prove laziness...
user> (take 2 (moving-sum-of-smaller-squares < 2 (iterate inc 0)))
(1 1)

;; also, 'smaller' means pred-smaller here -- with
;; a different ordering, a different result is obtained
user> (take 10 (moving-sum-of-smaller-squares > 2 (iterate inc 0)))
(1 5 13 25 41 61 85 113 145 181)

Как правило, (moving-sum-of-smaller-squares pred n & nums) генерирует ленивую последовательность сумм квадратов n пред-наименьших чисел во все более длинных начальных фрагментах оригинальной последовательности чисел, где «пред-наименьшее» означает наименьшее в отношении порядка вызвано предикатом pred. При pred = > вычисляется сумма n наибольших квадратов.

Эта функция использует трюк, который я упомянул выше, при описании решения Схемы, который суммировал три квадрата, затем вычитал наименьший и поэтому может корректировать текущую сумму на правильную величину, не пересчитывая ее на каждом шаге.

С другой стороны, он выполняет большую сортировку; Я считаю, что на самом деле не стоит пытаться оптимизировать эту часть, так как сортируемые seqs всегда имеют длину n элементов и на каждом шаге может быть не более одной операции сортировки (ни одной, если сумма не требует корректировки).