Работа с удивительным отсутствием ParList в scala.collections.parallel

Question

Итак, scala 2.9 недавно появился в тестировании Debian, принеся с собой новомодные параллельные коллекции.

Предположим, у меня есть некоторый код, эквивалентный

  def expensiveFunction(x:Int):Int = {...}

  def process(s:List[Int]):List[Int} = s.map(expensiveFunction)

, из крошечного бита IЯ собирал информацию о параллельных коллекциях до того, как документы действительно появились на моей машине, я ожидал распараллелить это, просто переключив Список на ParList ... но, к моему удивлению, его нет!(Просто ParVector, ParMap, ParSet ...).

В качестве рабочей среды это (или эквивалент в одну строку), кажется, работает достаточно хорошо:

  def process(s:List[Int]):List[Int} = {
    val ps=scala.collection.parallel.immutable.ParVector()++s
    val pr=ps.map(expensiveFunction)
    List()++pr
  }

, что позволило повысить производительность моего тестового кода примерно в 3 раза и значительно увеличить загрузку ЦП (четырехъядерный процессор плюс гиперпоточность i7).Но это кажется неуклюжим.

Мой вопрос является своего рода агрегированным:

• Почему нет ParList?
• Учитывая, что нетParList, есть ли лучший шаблон / идиома, которую я должен принять, чтобы я не чувствовал, что они пропали?
• Я просто "отсталый", часто использую списки в моемпрограммы scala (как и все книги о Scala, которые я купил за 2,7 дня, научили меня), и мне действительно нужно больше использовать Vectors?(Я имею в виду, что в земле C ++ мне обычно нужна довольно веская причина для использования std::list сверх std::vector).

Answer 1

List с хороши, когда вам нужно сопоставление с образцом (то есть case x :: xs) и для эффективного добавления / повторения.Однако они не так хороши, когда требуется быстрый доступ по индексу, или разбиение на куски, или объединение (т. Е. xs ::: ys).

Следовательно, не имеет особого смысла (иметь параллель List) когда вы думаете, что такого рода вещи (расщепление и соединение) равны точно , что необходимо для эффективного параллелизма.Использование:

xs.toIndexedSeq.par

Answer 2

Сначала позвольте мне показать вам, как создать параллельную версию этого кода:

def expensiveFunction(x:Int):Int = {...}

def process(s:List[Int]):Seq[Int] = s.par.map(expensiveFunction).seq

Это поможет Scala разобраться с вами - и, между прочим, использует ParVector. Если вы действительно хотите List, звоните .toList вместо .seq.

По вопросам:

• Не существует ParList, потому что List - это внутренне непараллельная структура данных, потому что любая операция над ней требует обхода.

• Вы должны кодировать черты вместо классов - Seq, ParSeq и GenSeq, например. Даже рабочие характеристики List гарантируются LinearSeq.

• Все книги до Scala 2.8 не имели в виду новую библиотеку коллекций. В частности, коллекции действительно не имели единого и полного API. Теперь они это делают, и вы получите много пользы от этого.

  Кроме того, в Scala 2.7 не было коллекции, подобной Vector, - это неизменяемая коллекция с (почти) постоянным индексированным доступом.

Answer 3

A List не может быть легко разделен на различные подсписки, что затрудняет распараллеливание.Для одного это имеет O (n) доступ;Кроме того, List не может обрезать хвост, поэтому необходимо включить параметр длины.

Я думаю, лучше взять Vector.

Обратите внимание, что Scala's Vector отличается от std::vector.Последний в основном является оберткой вокруг стандартного массива, непрерывного блока в памяти, который нужно копировать время от времени при добавлении или удалении данных.Scala Vector - это специализированная структура данных, которая позволяет эффективно копировать и разбивать, сохраняя неизменность самих данных.