我正在尝试使用合并排序来实现多线程。我让它在将数组切成两半的地方创建新线程。
该数组的排序取决于:
[数组的大小] vs [创建新线程的次数]
例如:如果我让它在大小为 70 的数组上仅创建两个线程,则该数组将被排序,但如果我让它创建 6 个线程,它将返回未排序的状态。我认为可能的一件事是线程没有同步,但我使用了 threadName.join()
这里是一些代码:merge.java
import java.util.Random;
public class merge implements Runnable {
int[] list;
int length;
int countdown;
public merge(int size, int[] newList, int numberOfThreadReps, int firstMerge) {
length = size;
countdown = numberOfThreadReps;
list = newList;
if (firstMerge == 1)
threadMerge(0, length - 1);
}
public void run() {
threadMerge(0, length - 1);
}
public void printList(int[] list, int size) {
for (int i = 0; i < size; i++) {
System.out.println(list[i]);
}
}
public void regMerge(int low, int high) {
if (low < high) {
int middle = (low + high) / 2;
regMerge(low, middle);
regMerge(middle + 1, high);
mergeJoin(low, middle, high);
}
}
public void mergeJoin(int low, int middle, int high) {
int[] helper = new int[length];
for (int i = low; i <= high; i++) {
helper[i] = list[i];
}
int i = low;
int j = middle + 1;
int k = low;
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
list[k] = helper[i];
i++;
} else {
list[k] = helper[j];
j++;
}
k++;
}
while (i <= middle) {
list[k] = helper[i];
k++;
i++;
}
helper = null;
}
public void threadMerge(int low, int high) {
if (countdown > 0) {
if (low < high) {
countdown--;
int middle = (low + high) / 2;
int[] first = new int[length / 2];
int[] last = new int[length / 2 + ((length % 2 == 1) ? 1 : 0)];
for (int i = 0; i < length / 2; i++)
first[i] = list[i];
for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
last[i] = list[i + length / 2];
merge thread1 = new merge(length / 2, first, countdown, 0);// 0
// is
// so
// that
// it
// doesn't
// call
// threadMerge
// twice
merge thread2 = new merge(length / 2
+ ((length % 2 == 1) ? 1 : 0), last, countdown, 0);
Thread merge1 = new Thread(thread1);
Thread merge2 = new Thread(thread2);
merge1.start();
merge2.start();
try {
merge1.join();
merge2.join();
} catch (InterruptedException ex) {
System.out.println("ERROR");
}
for (int i = 0; i < length / 2; i++)
list[i] = thread1.list[i];
for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
list[i + length / 2] = thread2.list[i];
mergeJoin(low, middle, high);
} else {
System.out.println("elsd)");
}
} else {
regMerge(low, high);
}
}
}
proj4.java
import java.util.Random;
public class proj4 {
public static void main(String[] args) {
int size = 70000;
int threadRepeat = 6;
int[] list = new int[size];
list = fillList(list, size);
list = perm(list, size);
merge mergy = new merge(size, list, threadRepeat, 1);
// mergy.printList(mergy.list,mergy.length);
for (int i = 0; i < mergy.length; i++) {
if (mergy.list[i] != i) {
System.out.println("error)");
}
}
}
public static int[] fillList(int[] list, int size) {
for (int i = 0; i < size; i++)
list[i] = i;
return list;
}
public static int[] perm(int[] list, int size) {
Random generator = new Random();
int rand = generator.nextInt(size);
int temp;
for (int i = 0; i < size; i++) {
rand = generator.nextInt(size);
temp = list[i];
list[i] = list[rand];
list[rand] = temp;
}
return list;
}
}
所以 TL;DR 我的数组没有根据数组的大小和使用线程拆分数组的次数通过多线程合并排序进行排序...这是为什么?
最佳答案
哇。这是一种有趣的受虐行为。我确信你已经继续前进,但我为子孙后代着想......
代码中的错误位于 mergeJoin
与 middle
争论。这对于 regMerge
来说很好。但在 threadMerge
中间传入的是(low + high) / 2
而不是(length / 2) - 1
。自从threadMerge
low
始终为 0 且 high
是 length - 1
和 first
数组有 (length / 2)
尺寸。这意味着对于具有奇数个条目的列表,它通常会失败,具体取决于随机化。
还有一些风格问题使该程序变得更加复杂且容易出错:
- 当 Java 有一个方便的
list.length
时,代码会传递数组的大小。打电话会更直接、更安全。 - 该代码在许多地方重复计算(请参阅
length/2
)。 - 代码应该能够在数组内部进行排序,而无需创建子数组。
- 类应以大写字母开头(
Merge
而不是merge
) -
firstMerge
应该是一个 boolean 值 - 代码名称为
Thread
变量merge1
和merge
变量thread1
。咕噜咕噜。 merge
构造函数调用threadMerge(0,length -1)
很奇怪。我只是将该调用放在new
之后回拨proj4
。然后firstMerge
可以删除。- 我会考虑改用
high
超过最大值而不是最大值。我们倾向于这样思考for (int i = 0; i < 10; i++)
超过i <= 9
。那么代码可以有j
从low
开始至< middle
和k
来自middle
至< high
。更好的对称性。
祝你好运。
关于java - 使用 Runnable 或 Thread 的 Java 线程问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4121779/