Как выполнить две функции одновременно в f #?

Question

Я пытаюсь заставить мою программу быстрой сортировки работать на F # параллельно, заставляя две задачи выполняться параллельно.Я попытался просмотреть онлайн-документацию Microsoft, но она мне не помогла!Вот мой код без параллелизма:

let rec quicksort (list: int list) =
  match list with
  | [] -> [] // if empty list, yield nothing
  // otherwise, split the list into a head and tial, and the head is the pivot value
  | pivot :: tail ->
      // Using List.partition to partition the list into lower and upper
      let lower, upper = List.partition (fun x -> x < pivot) tail
      // Recursive calls, final product will be low list + pivot + high list
      quicksort lower @ [pivot] @  quicksort upper

Я пытался реализовать что-то вроде

Async.Parallel [quicksort lower; @ [pivot] @ quicksort upper;] |> Async.RunSynchronously

Но я получаю синтаксические ошибки, относящиеся к типу.Что мне здесь не хватает?

Answer 1

Как уже упоминалось @hvester, добавление распараллеливания к быстрой сортировке таким образом вам мало чем поможет.Реализация медленная, потому что она использует списки и распределения, а не из-за фактических ограничений ЦП.

Тем не менее, если бы это была просто иллюстрация, показывающая различные способы распараллеливания кода F #, то хорошей альтернативой использованию Array.Parallel.map было бы использование задач:

open System.Threading.Tasks

let rec quicksort (list: int list) =
  match list with
  | [] -> [] 
  | pivot :: tail ->
      let lower, upper = List.partition (fun x -> x < pivot) tail
      let lowerRes = Task.Factory.StartNew(fun _ -> quicksort lower)
      let upperRes = quicksort upper
      lowerRes.Result @ [pivot] @ upperRes

Задачипозвольте вам начать работу в фоновом режиме, используя StartNew, а затем дождитесь результата, открыв свойство Result.Я думаю, что это было бы более уместно в подобных сценариях.Array.Parallel.map больше предназначен для параллельной обработки больших массивов.

Answer 2

Распараллеливание кода, связанного с вычислениями, такого как сортировка, следует выполнять скорее с Array.Parallel.map вместо Async.Parallel, что предназначено для повышения пропускной способности кода, связанного с вводом-выводом.

Вы можете распараллелить вашу функцию какследует с Array.Parallel.map.

let rec quicksort (list: int list) =
    match list with
    | [] -> [] /
    | pivot :: tail ->
        let lower, upper = List.partition (fun x -> x < pivot) tail
        let sortedArrays = Array.Parallel.map quicksort [| lower; upper |]
        sortedArrays.[0] @ [pivot] @ sortedArrays.[1]

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

Если вы хотите ускорить алгоритм быстрой сортировки, можно добиться наибольшего выигрыша, избегая выделения объектов (списков) во время алгоритма.Использование массива и изменение его на месте - вот путь:)