langref.org - csharp, erlang, cpp, fsharp ... - Parallel | Pool of Workers | Subdivide A Problem To A Pool Of Workers (No Shared Data)

View Problem

Parallel

Subdivide A Problem To A Pool Of Workers (No Shared Data)

Take a hard to compute problem and split it up between multiple worker threads. In your solution, try to fully utilize available cores or processors. (I'm looking at you, Python!)

Note: In this question, there should be no need for shared state between worker threads while the problem is being solved. Only after every thread completes computation are the answers recombined into a single output.

Example:

-Input-

(In python syntax)

["ab", "we", "tfe", "aoj"]

In other words, a list of random strings.

-Output-

(In python syntax)

[ ["ab", "ba", "aa", "bb", "a", "b"], ["we", "ew", "ww", "ee", "w", "e"], ...

In other words, all possible permutations of each input string are computed.

cpp OpenMP

vector<string> input;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");

// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}

cout << output << endl;

fsharp

open System
let input = [| "ab"; "we"; "tfe"; "aoj" |]

/// Computes all permutations of an array
let rec permute = function
| [| |] -> [| [| |] |]
| a ->
a
|> Array.mapi (fun i ai ->
// Take all elements in the array apart from the i.th, compute
// their permutations, then attach element i at the front of each perm
Array.sub a 0 i
|> Array.append (Array.sub a (i + 1) (a.Length - i - 1))
|> permute
|> Array.map (fun perm -> Array.append [| ai |] perm)
)
|> Array.concat

/// Computes all permutations of a string
let permuteString (s: string) =
s.ToCharArray()
|> permute
|> Array.map (fun p -> new String(p))

let output =
input
|> Array.map (fun word -> async { return (permuteString word) })
|> Async.Parallel
|> Async.RunSynchronously

fsharp .NET 4

// like the Java and Groovy solutions, does not duplicate letters
open System
open System.Threading.Tasks

let input = [| "ab"; "we"; "tfe"; "aoj" |]

let factorial n =
seq { 1 .. n } |> Seq.reduce (*)

let swap (arr:'a[]) i j =
[| for k = 0 to arr.Length - 1 do
yield if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a[]) =
if j = (r.Length + 1) then r
else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a[]) = seq {
for k = 0 to (factorial source.Length) - 1 do
yield permutation (k,2) source
}

let permute (word:string) =
let letters = word.ToCharArray()
permutations letters
|> Seq.map (fun chars -> String(chars))
|> Array.ofSeq

let tasks =
input |> Array.map (fun word -> Task.Factory.StartNew(fun () -> permute word))

let taskResult (t:Task<_>) =
t.Result

let output = Task.Factory.ContinueWhenAll(tasks, fun ts -> Array.map taskResult ts).Result

groovy

// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]
def threads = []

void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}

words.each { word ->
def t = Thread.start {
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
threads << t
}

threads.each{ it.join() }
println ans

groovy with gpars

// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
def ans = [].asSynchronized()
def words = ["ab", "we", "tfe", "aoj"]

void permutations(String prefix, String w, Set<String> permSet) {
int n = w.size()
if (!n) permSet << prefix
else n.times { i ->
permutations(prefix + w[i], w[0..<i] + w[i+1..<n], permSet)
}
}

withParallelizer {
words.eachParallel { word ->
def wordAns = [] as Set
for (int i = 0; i < word.size(); i++)
for (int j = i + 1; j <= word.size(); j++)
permutations("", word[i..<j], wordAns)
ans << wordAns
}
}

println ans

Submit a new solution for csharp, erlang, cpp, fsharp ...
There are 9 other solutions in additional languages (clojure, fantom, haskell, java ...)