Shuffling an array in multiple threads

Question

I have an array of size N. I want to shuffle its elements in 2 threads (or more). Each thread should work with its own part of the array.

Suppose that the first thread shuffles items from 0 to K, and the second thread moves items from K to N (where 0 <K <N). So it might look like this:

//try-catch stuff is ommited static void shuffle(int[] array) { Thread t1 = new ShufflingThread(array, 0, array.length / 2); Thread t2 = new ShufflingThread(array, array.length / 2, array.length); t1.start(); t2.start(); t1.join(); t2.join(); } public static void main(String[] args) { int array = generateBigSortedArray(); shuffle(array); } 

Are there any guarantees from the JVM that after shuffling I will see the changes to the array from the main method?

How do I implement ShufflingThread (or how do I run it, possibly in a synchronized block or something else) to get such guarantees?

Answer 1

Thread.start () and Thread.join () are enough to give you the relationship between initializing the array, sending it to threads, and then reading it in the main method.

Actions that trigger occur earlier than those described here .

As mentioned elsewhere, ForkJoin is very well suited for this type of separation and subjugation algorithm and frees you from the large amount of accounting that you would need to implement.

Answer 2

The join() call is sufficient to ensure memory consistency: when t1.join() returns, the main thread "sees" any operations that are performed in the t1 array.

In addition, Java guarantees that there are no word breaks on arrays: separate threads can use separate elements of the same array without the need for synchronization.

Answer 3

I think this is a good exercise in thread management, where (1) the task can be divided into several parts (2) the parts can be executed independently and asynchronously and (3) the main thread controls the completion of all such tasks in the corresponding threads. All you need is for this main thread to wait () and be notified () - ed by the task when the thread terminates each time. Here is an example of code that you can compile / run. Uncomment println () to see more.

Notes: [1] The JVM does not guarantee the execution order of the threads [2]. You need to synchronize when your main thread accesses a large array so as not to have any corrupted data ....

public class ShufflingArray {

 private int nPart = 4, // Count of jobs distributed, resource dependent activeThreadCount, // Currently active, monitored with notify iRay[]; // Array the threads will work on public ShufflingArray (int[] a) { iRay = a; printArray (a); } private void printArray (int[] ia) { for (int i = 0 ; i < ia.length ; i++) System.out.print (" " + ((ia[i] < 10) ? " " : "") + ia[i]); System.out.println(); } public void shuffle () { int startNext = 0, pLen = iRay.length / nPart; // make a bunch of parts for (int i = 0 ; i < nPart ; i++, activeThreadCount++) { int start = (i == 0) ? 0 : startNext, stop = start + pLen; startNext = stop; if (i == (nPart-1)) stop = iRay.length; new Thread (new ShuffleOnePart (start, stop, (i+1))).start(); } waitOnShufflers (0); // returns when activeThreadCount == 0 printArray (iRay); } synchronized private void waitOnShufflers (int bump) { if (bump == 0) { while (activeThreadCount > 0) { // System.out.println ("Waiting on " + activeThreadCount + " threads"); try { wait(); } catch (InterruptedException intex) { }}} else { activeThreadCount += bump; notify(); }} public class ShuffleOnePart implements Runnable { private int startIndex, stopIndex; // Operate on global array iRay public ShuffleOnePart (int i, int j, int k) { startIndex = i; stopIndex = j; // System.out.println ("Shuffler part #" + k); } // Suppose shuffling means interchanging the first and last pairs public void run () { int tmp = iRay[startIndex+1]; iRay[startIndex+1] = iRay[startIndex]; iRay[startIndex] = tmp; tmp = iRay[stopIndex-1]; iRay[stopIndex-1] = iRay[stopIndex-2]; iRay[stopIndex-2] = tmp; try { // Lets imagine it needs to do something else too Thread.sleep (157); } catch (InterruptedException iex) { } waitOnShufflers (-1); }} public static void main (String[] args) { int n = 25, ia[] = new int[n]; for (int i = 0 ; i < n ; i++) ia[i] = i+1; new ShufflingArray(ia).shuffle(); 

}}

Answer 4

using the ExecutorService from the java.util.Concurrent package along with the Callable Task to return a portion of the array from each thread run as soon as both threads are completed is another way to do this for consistent behavior.

Answer 5

Well, they cannot BOTH access the same array, and if you use a lock, or a mutex or some other synchronization mechanism, you can lose the strength of the threads (since you have to wait for another one, either to finish the shuffle or finish a bit shuffling). Why don't you just split the array in half, give each thread its array bit and then combine the two arrays?