Параметры для вычисления параллельной параллельной обработки списков в F #

Question

async {} рабочий процесс прост в использовании и дает хорошие результаты при асинхронных операциях, таких как IO.Это хороший вариант также для чисто связанных данных операций?Есть также .NET ThreadPool и BackgroundWorker, это лучшие варианты для вычислений с привязкой к данным?

У меня есть большой список, в котором около 10000 строк уникальны.Для каждого элемента мне нужно сравнить строку вместе со всеми строками, которые идут после него в списке.Тип возвращаемого значения будет list<string * list<string>>, содержащий каждый из исходных элементов вместе со списком возможных решений (возможные совпадения строк, основанные на каком-то конкретном алгоритме приложения).

Первоначально я думал использовать ansyc {} рабочий процесс, но я не уверен, будет ли эта проблема более подходящей для других параллельных технологий, или даже если она должна быть парализована.

Answer 1

Есть несколько вариантов, но первый вопрос заключается в том, хотите ли вы использовать решение на основе задач или параллельное использование данных. Недавно я написал несколько статей о параллельном программировании на F # , так что вы можете найти несколько статей из этой серии полезными.

Данные Параллельное . Если у вас есть чисто привязанная к процессору операция, параллельная данным , то лучшие варианты -

• Используйте модуль PSeq из F # PowerPack , если у вас есть более сложная декларативная обработка данных. Вы можете найти введение в моей статье Использование PLINQ и Задачи из F # .
• Используйте функцию Array.Parallel.map из стандартного библиотеки F #, если вам нужна простая операция map .

На основе задач, связанных с процессором . Если параллельная обработка данных не очень хорошо подходит для вашей проблемы, вы можете использовать задачи .NET 4.0 или асинхронные рабочие процессы F # и член StartAsChild. Задачи не поддерживают отмену и выглядят немного уродливо в F #, но они, вероятно, более оптимизированы (если вы хотите создать действительно большое их количество). С другой стороны, асинхронные рабочие процессы F # выглядят более элегантно в F #. Я написал две статьи, которые сравнивают варианты. первый объясняет основные функции, а второй говорит об отмене.

Существует также передача сообщений с использованием агентов F #, которые могут работать довольно хорошо, если у вас есть что-то, что требует сложной координации (и было бы иначе написано с использованием большого количества примитивов синхронизации и изменяемого состояния)

Answer 2

Ваша проблема связана с интенсивным использованием ЦП, поскольку у вас есть все данные в памяти, а основная стоимость ЦП - это настроенный вами алгоритм сопоставления строк.

Вы можете использовать Parallel.For , что немного быстрее, чем Async для параллельных задач, связанных с процессором.

Answer 3

Async предназначен как для параллельных операций с процессором, так и для асинхронных операций ввода-вывода, и хорошо работает для обоих.У Дона Сайма есть сообщение в блоге об этом.Операции по-прежнему будут выполняться в пуле потоков, поэтому вы не откажетесь от этого с помощью async.

Answer 4

async {} рабочий процесс прост в использовании и дает хорошие результаты при асинхронных операциях, таких как IO.Является ли это хорошим вариантом также для операций с чисто данными?

Нет.Async для параллельного ввода-вывода, который полностью отличается от вашей проблемы, которая заключается в параллельных вычислениях с привязкой к процессору.

Есть также .NET ThreadPool и BackgroundWorker, эти лучшие варианты для вычислений с привязкой данных?

Чуть лучше, но они все еще не созданы для этого.

list<(string * list)

Это недопустимый тип.

Моей первоначальной мыслью было использование рабочего процесса ansyc {},

Плохая идея.

, но я не уверен, что эта проблема больше подойдет длядругие параллельные методы, или даже если они должны быть парализованы.

Сначала напишите правильную серийную версию и, если она слишком медленная, оптимизируйте ее и, возможно, распараллелите.Например, вы вряд ли увидите значительные выгоды от параллелизма, когда вы все еще используете связанные списки.

Описанный вами алгоритм может быть реализован следующим образом в F #:

let rec f p a = function
  | [] -> List.rev a
  | x::xs -> f p ((x, List.filter (p x) xs)::a) xs

где p - это произвольная предикатная функция, над которой работает ваш алгоритм.Например, следующее находит все последующие строки, равные каждой строке заголовка:

> f (=) [] ["a"; "b"; "c"; "a"; "c"];;
val it : (string * string list) list =
  [("a", ["a"]); ("b", []); ("c", ["c"]); ("a", []); ("c", [])]

Выполнение этого на 10000 строк на моем нетбуке занимает менее 6 секунд.Это достаточно быстро?