Что-то среднее между «dotimes» и «for» функциональностью?

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

Answer 3

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

пример:

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

дает:

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

Answer 4

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

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

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

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

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

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

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

Answer 5

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

По сути, это список, к которому можно обратиться до конца.