Параллельное сито Эратосфена с использованием редукторов Clojure

Я реализовал Решето Эратосфена, используя стандартную библиотеку Clojure.

(defn primes [below]
  (remove (set (mapcat #(range (* % %) below %)
                       (range 3 (Math/sqrt below) 2)))
          (cons 2 (range 3 below 2))))

Я думаю, что это должно быть поддается параллелизму, так как здесь нет рекурсии, и можно добавить редукторные версии remove и mapcat. Вот что я придумал:

(defn pprimes [below]
  (r/foldcat
   (r/remove
    (into #{} (r/mapcat #(range (* % %) below %)
                        (into [] (range 3 (Math/sqrt below) 2))))
    (into [] (cons 2 (range 3 below 2))))))

Я разлил исходный набор и сгенерированные множители в векторы, так как понимаю, что LazySeq не складывается. Кроме того, для окончательной реализации коллекции используется r / foldcat.

Моя проблема в том, что это немного медленнее, чем первая версия.

(time (first (primes  1000000))) ;=> approx 26000 seconds
(time (first (pprimes 1000000))) ;=> approx 28500 seconds

Слишком много накладных расходов от координирующих процессов или я неправильно использую редукторы?


reducers parallel-processing clojure primes sieve-of-eratosthenes
person thomasvarney723    schedule 02.12.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Благодаря Летвински, похоже, это сработало:

(defn pprimes2 [below]
  (r/foldcat
   (r/remove
    (into #{} (r/foldcat (r/map #(range (* % %) below %)
                                (into [] (range 3 (Math/sqrt below) 2)))))
    (into [] (cons 2 (range 3 below 2))))))

Очевидно, мне нужно было добавить еще одну операцию сворачивания, чтобы параллельно отображать #(range (* % %) below %).

(time (first (pprimes   1000000))) ;=> approx 28500 seconds
(time (first (pprimes2  1000000))) ;=> approx  7500 seconds

Изменить: приведенный выше код не работает. r/foldcat не объединяет составные числа, а просто возвращает вектор кратных для каждого простого числа. Конечный результат - вектор 2 и все нечетные числа. Замена r/map на r/mapcat дает правильный ответ, но снова медленнее, чем исходный primes.

person thomasvarney723    schedule 03.12.2015

arrow_upward
0
arrow_downward

насколько помните, r/mapcat и r/remove сами по себе не параллельны, они просто создают складываемые коллекции, которые, в свою очередь, могут быть распараллелены с помощью r/fold. в вашем случае единственной параллельной операцией является r/foldcat, что согласно документации «Эквивалентно (fold cat append! coll)», что означает, что вы просто потенциально можете выполнять append! параллельно, а это совсем не то, что вам нужно.

Чтобы сделать его параллельным, вам, вероятно, следует использовать r/fold с remove в качестве функции уменьшения и concat в качестве функции объединения, но я думаю, это не сделает ваш код быстрее, я думаю, из-за характера вашего алгоритма (я имею в виду, что вы попытаетесь удалить большой набор предметов из каждого фрагмента коллекции)

person leetwinski    schedule 02.12.2015
comment
Спасибо за ответ! Я знал, что r / mapcat, r / remove и т. Д. Были просто рецептами, которые нужно было выполнять в будущем, но у меня сложилось впечатление, что r / foldcat на конце будет запускать каждую операцию параллельно. Вы заставили меня подумать, что может понадобиться еще одна складка. В конце концов, сопоставление #(range (* % %) below %) с 2 ‹шансами‹ ниже было тем, что я действительно хотел сделать параллельно. - person thomasvarney723; 03.12.2015