多线程排序算法 [英] Multi-threading sorting algorithms
问题描述
我必须在Java中为我的算法类实现多线程合并排序和快速排序,并将它们与单线程版本进行比较.但是,我以前从未使用过多线程.
I have to implement a multi threaded Merge Sort and Quick sort in Java for my algorithms class and compare them to my single threaded versions. However, I have never multithreaded before.
是可以多线程处理的代码还是必须重新启动?
Is the code I have able to be multi threaded or do I have to start again?
这是我的单线程算法代码 合并排序. sort()方法是我必须实现的策略模式的一部分.
Here is my code for the single thread algorithms Merge Sort. the sort() method is part of the strategy pattern I have to implement.
@Override
public int[] sort(int[] list) {
int array_size = list.length;
list = msort(list, 0, array_size-1);
return list;
}
int[] msort(int numbers[], int left, int right) {
int mid;
if (left<right) {
mid = (right + left) / 2;
msort(numbers, left, mid);
msort(numbers, mid+1, right);
merge(numbers, left, mid, mid+1, right);
}
return numbers;
}
void merge(int numbers[], int startA, int endA, int startB, int endB) {
int finalStart = startA;
int finalEnd = endB;
int indexC = 0;
int[] listC = new int[numbers.length];
while(startA <= endA && startB <= endB){
if(numbers[startA] < numbers[startB]){
listC[indexC] = numbers[startA];
startA = startA+1;
}
else{
listC[indexC] = numbers[startB];
startB = startB +1;
}
indexC++;
}
if(startA <= endA){
for(int i = startA; i < endA; i++){
listC[indexC]= numbers[i];
indexC++;
}
}
indexC = 0;
for(int i = finalStart; i <= finalEnd; i++){
numbers[i]=listC[indexC];
indexC++;
}
}
这是我的快速排序
@Override
public int[] sort(int[] list) {
int[] array = quickSort(list, 0, list.length-1);
return array;
}
int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
int[] quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
return arr;
}
干杯!
推荐答案
简短的回答-是的,这些算法可以转换为多线程,而无需从头开始(据我所知).
Short answer - yes, these algorithms can be converted to be multi-threaded without starting from scratch (so far as I can see).
使这些易于"并行化的关键元素是:
The key elements that make these "easy" to parallelize are:
- 每个实现中有两个递归调用
- 这两个递归调用对单独的数据进行操作-它们不应彼此冲突(例如,即使在同一数组中进行操作,它们也将在不同的索引上进行操作)
- 进行两个递归调用的方法要等到两个都完成后才能继续进行
- 这两个呼叫的执行顺序无关紧要
希望能回答您的一些问题.
That's answered some of your questions, hopefully.
更多建议,不确定是否会有用:
Some more advice, not sure how useful this will be:
- 如果将两个递归调用都放入一个新线程中,则当前线程将在等待它们都完成时处于空闲状态
- 当要处理的元素数量很少时,线程的开销可能会比获得的开销高.
- 您可能通常希望限制用于此任务的线程数-您可能希望使用某种形式的线程池或工作队列,并且线程数固定.
这篇关于多线程排序算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!