Между функциями "dotimes" и "for"?

Я часто обнаруживаю, что хочу эффективно запускать функцию Clojure несколько раз с индексом целого числа (например, "dotimes" ), но также получать результаты как готовые последовательности/список (например, "для" ).

то есть. Я хотел бы сделать что-то вроде этого:

(fortimes [i 10] (* i i))

=> (0 1 4 9 16 25 36 49 64 81)

Ясно, что можно было бы сделать:

(for [i (range 10)] (* i i))

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

Какой лучший способ достичь этого в Clojure?

Ответ 1

Я написал итерационный макрос, который может сделать это и другие типы итераций очень эффективно. Пакет называется clj-iterate, как на github, так и на клоарах. Например:

user> (iter {for i from 0 to 10} {collect (* i i)})
(0 1 4 9 16 25 36 49 64 81 100)

Это не приведет к созданию временного списка.

Ответ 2

Создание диапазона в цикле for, как показано во втором примере, является идиоматическим решением для решения этой проблемы в Clojure.

Так как Clojure обоснован в функциональной парадигме, программирование в Clojure по умолчанию будет генерировать временные структуры данных, подобные этому. Однако, поскольку команда "range" и "for" работает с ленивыми последовательностями, запись этого кода не заставляет всю структуру данных временного диапазона существовать одновременно в памяти. При правильном использовании поэтому для ленивых seqs, используемых в этом примере, очень мало ресурсов памяти. Кроме того, вычислительные накладные расходы для вашего примера являются скромными и должны расти только линейно с размером диапазона. Это считается приемлемым накладным для типичного кода Clojure.

Соответствующий способ полностью избежать этих накладных расходов, если список временных диапазонов абсолютно, положительно неприемлем для вашей ситуации, заключается в том, чтобы написать код с помощью атомов или переходных процессов: http://clojure.org/transients. Это вы сделаете, однако, вы откажетесь от многих преимуществ модели программирования Clojure в обмен на несколько лучшую производительность.

Ответ 3

Я не уверен, почему вас беспокоит "создание и отбрасывание" ленивой последовательности, созданной функцией range. Ограниченная итерация, выполняемая dotimes, скорее всего, более эффективна, она является встроенным шагом и сравнивается с каждым шагом, но вы можете заплатить дополнительную стоимость, чтобы выразить свою собственную конкатенацию списка там.

Типичным решением Lisp является добавление новых элементов в список, который вы создаете по ходу, а затем реверсируйте этот застроенный список деструктивно, чтобы получить возвращаемое значение. Другие методы, позволяющие добавлять список в постоянное время, хорошо известны, но они не всегда оказываются более эффективными, чем подход с добавлением-потом-обращением.

В Clojure вы можете использовать переходные процессы, чтобы попасть туда, опираясь на деструктивное поведение функции conj!:

(let [r (transient [])]
  (dotimes [i 10]
    (conj! r (* i i))) ;; destructive
  (persistent! r))

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

Чтобы перегрузить r выше на новое значение, полученное каждым вызовом conj!, нам нужно будет использовать atom ввести еще один уровень косвенности. В этот момент мы, однако, сражаемся против dotimes, и лучше написать свою собственную форму с помощью loop и recur.

Было бы неплохо иметь возможность переназначить вектор того же размера, что и итерационная граница. Я не вижу способа сделать это.

Ответ 4

(defmacro fortimes [[i end] & code]
  `(let [finish# ~end]
     (loop [~i 0 results# '()]
       (if (< ~i finish#)
         (recur (inc ~i) (cons [email protected] results#))
         (reverse results#)))))

Пример:

(fortimes [x 10] (* x x))

дает:

(0 1 4 9 16 25 36 49 64 81)

Ответ 5

Хмм, я не могу ответить на ваш комментарий, потому что я не был зарегистрирован. Тем не менее, clj-iterate использует PersistentQueue, который является частью библиотеки времени выполнения, но не доступен через читателя.

В основном это список, по которому вы можете конгурировать до конца.