I have to use N(i=1..N) threads to sort an array of M numbers,each thread start to sort the array from position (N*i)%m. Could anyone help me?
3 Answers
What you will want to do is use a divide and conquer sorting method like quick sort.
What you will want to do is partition the array, and then pass the two halves of the array off to another thread to do the processing.
Say you have the number:
11 43 24 56 12 65 90 12 53 23
In one thread, you will partition the numbers:
12 24 11 23 12 | 65 90 53 56 43
Then you can perform quick sort on each half of the array in a different thread.
Allow me to provide some code:
public void multiThreadSort(int threads, int[] arr, int start, int stop) {
if (threads > 1) {
int midpoint = partition(arr, start, stop);
new Thread(){public void run() {
multiThreadSort(threads - 1, arr, start, midpoint);
}}.start();
new Thread(){public void run() {
multiThreadSort(threads - 1, arr, midpoint, stop);
}}.start();
}
else
Arrays.sort(arr, start, stop);
}
public int partition(int[] arr, int start, int stop);
Then call it like so:
multiThreadSort(N, arr, 0, arr.length());
12 Comments
Anthony
I like that this answer actually answers the question, not try and tell the asker that its a bad idea (which for small cases, it is).
jjnguy
@Shy, yeah, in small cases it's a bad idea. But for large datasets and educational purposes, it's a good idea.
aioobe
Hmm.. What do you do when you have no more threads to "delegate" to? Do you start sorting the remaining chunks with a single-threaded algorithm?
jjnguy
@aioobe, yup. You just sort the remaining chunks on that thread. And, because everything is already partitioned, you don't have to merge.
Luke Hutteman
While this would indeed do a threaded sort of the array, it neither limits the sort to N threads, nor have threads start to sort at position (N*i)%m. The former could be fixed by utilize a fixedThreadPool(N), the latter cannot be fixed using quicksort.
|
You could let each thread sort its own portion of the array using Arrays.sort(arr, fromIndex, toIndex) and after all threads are done, simply use a merge sort to merge the different results. (Even this step could be parallelized by merging multiple portions at a time.)
Here is a related question / good answer.
6 Comments
jjnguy
If you are multi-threading for performance, performing full sorts on each part, and then merging them isn't the best option.
jjnguy
Well, there is a better option than fully sorting and then merging. A distributed quick sort will perform better. (on large data sets)
jjnguy
I see how this might better answer the specific question.
jjnguy
But, if each thread can only look at one small part of the array, it is impossible to properly sort the entire thing.
Luke Hutteman
@jinguy: mergesort uses a divide-and-conquer approach just like quicksort; the difference is that were quicksort uses an O(N) step to partition the array prior to spawning the left- and right- sorts, mergesort sorts both first and then uses an O(N) step to merge the sorted arrays.
|
Another question is why do you want to do this? Thread creation and destruction is rather heavy, sorting (if you can keep your set in-memory) is rather quick. Doing this make sense only if you have the threads pre-existing in a thread pool for some other reason, if the time to sort M is much greater than the time to create (and probably to destroy) a thread, or if this is an academic exercise to learn about thread manipulation (in which case you shouldn't be asking here). If the time to sort M is greater than the time to create a thread you are probably going to have part of your array in virtual memory and disk paging effects will dominate your performance.
Threads are very useful, even essential, for some algorithms. Sorting is not a good application. Except, as mentioned, as a learning exercise to get experience writing software where your threads play well together.
4 Comments
jjnguy
Giant arrays could benefit from being sorted in multiple threads.
aioobe
"Thread creation and destruction is rather heavy" you have a reference on that? I believe it is synchronization between threads that is expensive.
jjnguy
@aioobe, if you don't need to synchronize the threads, this isn't a problem.
verisimilidude
Creating a thread requires creation of a Thread object (which requires memory allocation and cycles to check its liveness), creation of an underlying OS thread (impact varies by OS), and adding the thread into the scheduler. None of these processor cycles are required when using a reasonable data structure to implement an in-process quicksort. And @jjnguy, I did say that large arrays could benefit when the time to sort is larger than the time to create a thread. Until you come up with some actual benchmark data I will stand by my assertion that multithreading and sorting don't go together.
(N*i)%Mand end at(N*i)%M + M/N).