Параллельный алгоритм декартова произведения в Clojure
Есть ли хороший алгоритм для вычисления декартова произведения три seqs одновременно в Clojure?
Я работаю над маленьким проектом хобби в Clojure, главным образом как средство выучить язык и его функции параллелизма. В моем проекте я должен вычислить декартово произведение три seqs (и делают что-то с результатами).
Я нашел cartesian-product функция в clojure.contrib.combinatorics, который работает вполне прилично. Однако вычисление декартова произведения оказывается узким местом программы. Поэтому я хотел бы выполнить вычисление одновременно.
Теперь, для map функция, существует удобное pmap альтернатива, которая волшебно делает вещь параллельной. Который прохладен :). К сожалению, такая вещь не существует для cartesian-product. Я посмотрел на исходный код, но я не могу найти простой способ сделать его параллельным сам.
Кроме того, я попытался реализовать алгоритм сам с помощью map, но я предполагаю, что мои алгоритмические навыки не то, чем они раньше были. Мне удалось придумать что-то ужасное для два seqs, но три был определенно мост слишком далеко.
Так, кто-либо знает об алгоритме, это уже параллельно, или то, которое я могу параллелизировать сам?
Править
Другими словами то, чего я действительно пытаюсь достигнуть, должно достигнуть чего-то подобного этому коду Java:
for (ClassA a : someExpensiveComputation()) {
for (ClassB b : someOtherExpensiveComputation()) {
for (ClassC c : andAnotherOne()) {
// Do something interesting with a, b and c
}
}
}
1 ответ
Если логика, которую вы используете для обработки декартова произведения, не является последовательной по своей сути, тогда возможно, вы могли бы просто разделить свои входные данные на половины (возможно, разделив каждую входную последовательность на две), вычислить 8 отдельных декартовых произведений (первая половина x первая половина x первая половина, первая половина x первая половина x вторая половина,. ..), обработайте их, а затем объедините результаты. Я ожидал, что это уже даст вам хороший импульс. Что касается настройки производительности самого декартова продукта, я не эксперт, но у меня есть некоторые идеи и наблюдения (иногда нужно вычислять кросс-продукт для Project Euler), поэтому я попытался резюмировать их ниже.
Прежде всего, я считаю функцию c.c.combinatorics немного странной с точки зрения производительности. В комментариях говорится, что это взято у Кнута, я полагаю, так что возможно одно из следующих достижений: (1) он будет очень производительным с векторами, но стоимость векторизации входных последовательностей убивает его производительность для других типов последовательностей; (2) этот стиль программирования не обязательно хорошо работает в Clojure в целом; (3) совокупные накладные расходы, понесенные из-за выбора конструкции (например, наличия этой локальной функции), велики; (4) Мне не хватает чего-то действительно важного. Итак, хотя я не хотел бы исключать возможность того, что это может быть отличная функция для использования в некоторых случаях использования (определяемых общим количеством задействованных последовательностей, количеством элементов в каждой последовательности и т. Д.), Во всех моих ( ненаучные) измерения, простые для кажутся лучше.
Кроме того, есть две мои функции, одна из которых сравнима с для (я думаю, несколько медленнее в более интересных тестах, хотя на самом деле она кажется несколько быстрее в других ...не могу сказать, что чувствую себя готовым провести полностью обоснованное сравнение), второй, по-видимому, быстрее с длинной начальной последовательностью ввода, поскольку это параллельная версия с ограниченной функциональностью первой. (Подробности ниже.) Итак, сначала тайминги (добавьте случайные (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 можно было бы расширить для обработки большего количества последовательностей или сделать более сложным способ разделения рабочей нагрузки, но это то, что я придумал в первом приближении ... возможно, адаптируя его к вашим потребностям, конечно), мне было бы очень любопытно узнать результаты.