View Problem
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)
In other words, a list of random strings.
-Output-
(In python syntax)
In other words, all possible permutations of each input string are computed.
java
java
cpp OpenMP
fsharp
fsharp .NET 4
fantom
Submit a new solution for java, csharp, cpp, erlang ...
There are 8 other solutions in additional languages (clojure, groovy, haskell, 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.
public class ParallelPermutations {
final AtomicInteger cnt = new AtomicInteger(0);
final List<Set<String>> permutations = new ArrayList<Set<String>>();
public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}
public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}
synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}
System.out.println(permutations);
}
}
final AtomicInteger cnt = new AtomicInteger(0);
final List<Set<String>> permutations = new ArrayList<Set<String>>();
public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}
public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}
synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}
System.out.println(permutations);
}
}
public class ParallelPermutations {
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};
ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);
for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());
System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}
private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();
public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}
private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}
public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));
Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();
String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}
private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}
/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}
/** the word this task is working on*/
public String getWord() {
return word;
}
/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}
/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}
/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}
final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}
/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;
/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};
ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);
for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());
System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}
private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();
public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}
private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}
public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));
Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();
String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}
private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}
/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}
/** the word this task is working on*/
public String getWord() {
return word;
}
/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}
/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}
/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}
final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}
/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;
/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}
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;
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;
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
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
// 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
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
using concurrent
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
const class PermGen : Actor
{
new make(ActorPool pool) : super(pool) {}
Void permutations(Str prefix, Str w, Str[] pset)
{
n := w.size
if (n == 0)
{
if (!pset.contains(prefix))
pset.add(prefix)
return
}
n.times { permutations(prefix + w[it..it], w[0..<it] + w[it+1..<n], pset) }
}
override Obj? receive(Obj? msg)
{
Str word := msg
wordSubPerm := Str[,]
for (Int i := 0; i < word.size; i++)
for (Int j := i; j < word.size; j++)
permutations("", word[i..j], wordSubPerm)
return wordSubPerm
}
}
class SolutionXX
{
static Void main()
{
pool := ActorPool() { maxThreads = 8 }
futures := Future[,]
["ab", "we", "tfe", "aoj"].each { futures.add(PermGen(pool).send(it)) }
futures.each { echo(it.get) }
}
}
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
const class PermGen : Actor
{
new make(ActorPool pool) : super(pool) {}
Void permutations(Str prefix, Str w, Str[] pset)
{
n := w.size
if (n == 0)
{
if (!pset.contains(prefix))
pset.add(prefix)
return
}
n.times { permutations(prefix + w[it..it], w[0..<it] + w[it+1..<n], pset) }
}
override Obj? receive(Obj? msg)
{
Str word := msg
wordSubPerm := Str[,]
for (Int i := 0; i < word.size; i++)
for (Int j := i; j < word.size; j++)
permutations("", word[i..j], wordSubPerm)
return wordSubPerm
}
}
class SolutionXX
{
static Void main()
{
pool := ActorPool() { maxThreads = 8 }
futures := Future[,]
["ab", "we", "tfe", "aoj"].each { futures.add(PermGen(pool).send(it)) }
futures.each { echo(it.get) }
}
}
Submit a new solution for java, csharp, cpp, erlang ...
There are 8 other solutions in additional languages (clojure, groovy, haskell, python ...)
