Водохранилище выборки в Clojure


Я учусь в Clojure и решил начать с попытки написать решение довольно простой алгоритм, отбор проб водохранилища. Как я уже говорил, Я учусь в Clojure конкретно и решения задач в функциональных языка в целом. Может кто-то пожалуйста, взгляните на мой код и критику на это "clojureness". Использую ли я право идиоматических конвенций, есть способ, который работает лучше (и почему), форматирование, ничего.

(defn sample-seq [size data]
  (loop [sample (transient (vec (take size data)))
         idx size
         data (drop size data)]
    (if (empty? data)
      (persistent! sample)
      (let [rand-num (rand-int idx)
            new-sample (if (< rand-num size) 
                         (assoc! sample rand-num (first data)) 
                         sample)]
        (recur new-sample (inc idx) (rest data))))))
(println (sample-seq 4 [2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0]))


591
12
задан 2 февраля 2011 в 09:02 Источник Поделиться
Комментарии
2 ответа

Я думаю, что ваш код довольно читаемый и выглядит достаточно идиоматические Clojure, в код1. Так что с точки зрения читабельности кода, кажется, хорошо. Однако выполнение ДОЦ на вектор длиной N не берет o(зарегистрируйте N) времени, так что времени будет в О(N записей N) против o(п), которой необходимо реализация будет.

Однако существует не так много вы можете сделать об этом, кроме, возможно, его принудительно при помощи Java массивы, но это будет очень unidiomatic код на Clojure. И за o(n записей N) не так уж и плохо (наверняка не так плохо, как о(N^2) я неправильно утверждал раньше).

(Обратите внимание, что мое предыдущее замечание о переходных процессах ошибся в ДОЦ! на временной Вектор имеет ту же сложность выполнения, как на постоянный вектор).


1 Как правило, вы бы не на основе индексов петли везде, где только можно, но природа делает алгоритм, что практически невозможно здесь.

10
ответ дан 3 февраля 2011 в 12:02 Источник Поделиться

sepp2k критику неверна - доцент по вектору берет o(зарегистрируйте N) времени, а не о(n) времени, потому что Clojure использует постоянные векторы. Вы должны избегать использования ассоц! потому что это стиль в Clojure, чтобы избежать излишне деструктивного поведения.

Для более стойких векторов увидеть:
http://blog.higher-order.net/2009/02/01/understanding-clojures-persistentvector-implementation/

1
ответ дан 18 февраля 2011 в 10:02 Источник Поделиться