Алгоритм параллельного декартового произведения в Clojure

Question

Есть ли хороший алгоритм для вычисления декартового произведения трех seq с одновременно в Clojure?

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

Я нашел функцию cartesian-product в clojure.contrib.combinatorics, которая работает довольно хорошо. Однако расчет декартового произведения оказывается узким местом программы. Поэтому я бы хотел выполнить расчет одновременно.

Теперь для функции map есть удобная альтернатива pmap, которая волшебным образом делает эту вещь одновременно. Что круто :). К сожалению, такой вещи не существует для cartesian-product. Я посмотрел на исходный код, но не могу найти простой способ сделать его одновременно.

Кроме того, я сам пытался реализовать алгоритм, используя map, но я думаю, что мои алгоритмические навыки не те, что раньше. Мне удалось придумать что-то уродливое за две seq с, но три, безусловно, было слишком далеко.

Итак, кто-нибудь знает об алгоритме, который уже является параллельным, или о том, что я могу распараллелить себя?

---

EDIT

Другими словами, я действительно пытаюсь добиться чего-то похожего на этот код Java:

for (ClassA a : someExpensiveComputation()) {
    for (ClassB b : someOtherExpensiveComputation()) {
        for (ClassC c : andAnotherOne()) {
            // Do something interesting with a, b and c
        }
    }
}

Answer 1

Если логика, которую вы используете для обработки декартового произведения, не является по своей сути последовательной, то, возможно, вы могли бы просто разбить ваши входные данные на две части (возможно, разделив каждый входной последовательный на две части), рассчитать 8 отдельных декартовых произведений (сначала половина x первая половина x первая половина, первая половина x первая половина x вторая половина, ...), обработайте их и затем объедините результаты. Я ожидаю, что это уже даст вам толчок. Что касается настройки производительности самого декартового построения продукта, я не эксперт, но у меня есть некоторые идеи и наблюдения (иногда нужно рассчитать перекрестный продукт для Project Euler), поэтому я попытался обобщить их ниже.

Прежде всего, я нахожу функцию c.c.combinatorics немного странной в отделе производительности. В комментариях говорится, что это взято у Кнута, я полагаю, поэтому, возможно, получится одно из следующего: (1) оно будет очень производительным с векторами, но стоимость векторизации входных последовательностей убивает его производительность для других типов последовательностей; (2) этот стиль программирования не обязательно хорошо работает в Clojure в целом; (3) кумулятивные накладные расходы, понесенные из-за некоторого выбора конструкции (например, наличие этой локальной функции), велики; (4) Я упускаю что-то действительно важное. Поэтому, хотя я не хотел бы упускать из виду возможность использования этой функции для некоторых случаев использования (определяется общим количеством задействованных последовательностей, количеством элементов в каждом последующем и т. Д.), Во всех моих ( ненаучные) измерения простые for, кажется, лучше.

Тогда есть две мои функции, одна из которых сравнима с for (я думаю, что в более интересных тестах она несколько медленнее, хотя в других она кажется несколько более быстрой ... не могу сказать, что я чувствую, что вы готовы к полному обучению сравнения), другой, по-видимому, быстрее с длинной начальной последовательностью ввода, поскольку это параллельная версия первой с ограниченными функциональными возможностями. (Подробности следуют ниже.) Итак, сначала сроки (добавьте случайные (System/gc), если хотите повторить их):

;; a couple warm-up runs ellided
user> (time (last (doall (pcross (range 100) (range 100) (range 100)))))
"Elapsed time: 1130.751258 msecs"
(99 99 99)
user> (time (last (doall (cross (range 100) (range 100) (range 100)))))
"Elapsed time: 2428.642741 msecs"
(99 99 99)
user> (require '[clojure.contrib.combinatorics :as comb])
nil
user> (time (last (doall (comb/cartesian-product (range 100) (range 100) (range 100)))))
"Elapsed time: 7423.131008 msecs"
(99 99 99)
;; a second time, as no warm-up was performed earlier...
user> (time (last (doall (comb/cartesian-product (range 100) (range 100) (range 100)))))
"Elapsed time: 6596.631127 msecs"
(99 99 99)
;; umm... is syntax-quote that expensive?
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           `(~x ~x ~x)))))
"Elapsed time: 11029.038047 msecs"
(99 99 99)
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           (list x y z)))))
"Elapsed time: 2597.533138 msecs"
(99 99 99)
;; one more time...
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           (list x y z)))))
"Elapsed time: 2179.69127 msecs"
(99 99 99)

А теперь определения функций:

(defn cross [& seqs]
  (when seqs
    (if-let [s (first seqs)]
      (if-let [ss (next seqs)]
        (for [x  s
              ys (apply cross ss)]
          (cons x ys))
        (map list s)))))

(defn pcross [s1 s2 s3]
  (when (and (first s1)
             (first s2)
             (first s3))
    (let [l1 (count s1)
          [half1 half2] (split-at (quot l1 2) s1)
          s2xs3 (cross s2 s3)
          f1 (future (for [x half1 yz s2xs3] (cons x yz)))
          f2 (future (for [x half2 yz s2xs3] (cons x yz)))]
      (concat @f1 @f2))))

Я считаю, что все версии дают одинаковые результаты. pcross может быть расширен для обработки большего количества последовательностей или может быть более изощренным в способе разделения рабочей нагрузки, но это то, что я придумал в первом приближении ... Если вы все же протестируете это с помощью своей программы (возможно, адаптируете ее к Ваши потребности, конечно), мне было бы очень интересно узнать результаты.

Answer 2

'clojure.contrib.combinatorics имеет функцию декартовых произведений. Возвращает ленивую последовательность и может пересекать любое количество последовательностей.