1
我嘗試parallelize我merge sort實現：http://pastebin.com/2uMGjTxr。 我想創建儘可能多的Java-VM可以提供的線程。我想確定使用java.lang.Runtime的最大可能線程數。出並行合併時內存不足的錯誤排序
於是我想出了一個名爲MergeThread類：
public class MergeThread implements Runnable{
public int[] list;
int sIndex, eIndex;
public MergeThread(int[] pArray, int pStartIndex, int pEndIndex){
list = pArray;
sIndex = pStartIndex;
eIndex = pEndIndex;
}
public void run(){
list = mergeSort(list, sIndex, eIndex);
}
/**
* Merges two sorted int array into one new sorted array.
* @param lhs
* @param rhs
* @return
*/
private static int[] merge(int[] lhs, int[] rhs) {
int[] result = new int[lhs.length + rhs.length];
int leftIndex = 0;
int rightIndex = 0;
while(leftIndex < lhs.length && rightIndex < rhs.length) {
if(lhs[leftIndex] <= rhs[rightIndex]) {
result[leftIndex + rightIndex] = lhs[leftIndex];
leftIndex++;
} else {
result[leftIndex + rightIndex] = rhs[rightIndex];
rightIndex++;
}
}
while(leftIndex < lhs.length) {
result[leftIndex + rightIndex] = lhs[leftIndex];
leftIndex++;
}
while(rightIndex < rhs.length) {
result[leftIndex + rightIndex] = rhs[rightIndex];
rightIndex++;
}
return result;
}
/**
* Sorts an array from index <code>startIndex</code> (inclusive) to <code>endIndex</code> (exclusive).
* @param array
* @param startIndex
* @param endIndex
* @return new array that is sorted
*/
private static int[] mergeSort(int[] array, int startIndex, int endIndex) {
int length = endIndex - startIndex;
if(length == 0) {
return new int[]{};
}
if(length == 1) {
return new int[]{array[startIndex]};
}
int halfLength = length/2;
//int[] sortedLeftPart = mergeSort(array, startIndex, startIndex + halfLength);
MergeThread m1 = new MergeThread(array, startIndex, startIndex + halfLength);
Thread t1 = new Thread(m1);
t1.start();
//int[] sortedRightPart = mergeSort(array, startIndex + halfLength, endIndex);
MergeThread m2 = new MergeThread(array, startIndex + halfLength, endIndex);
Thread t2 = new Thread(m2);
t2.start();
try{
t1.join();
t2.join();
}catch(InterruptedException e){}
return merge(m1.list, m2.list);
}
}
而實際上啓動過程
import java.util.Random;
public class Aufg2 {
public static Random random = new Random(100);
public static void main(String[] args) {
int[] array = createRandomArray(10000000);
long time = System.currentTimeMillis();
int[] sortedArray = sort(array);
if(sortedArray.length != array.length || !isSorted(sortedArray)) {
System.err.println("Failed to sort given array! :-(");
return;
}
System.out.println("Success! Sorting took " + (System.currentTimeMillis() - time) + "ms.");
}
/**
* Creates a randomly filled array of given length
* @param length
* @return
*/
private static int[] createRandomArray(int length) {
int[] result = new int[length];
for(int i = 0; i < length; i++) {
result[i] = random.nextInt();
}
return result;
}
/**
* Checks whether a given int array is sorted in ascending order
* @param array
* @return <code>true</code> if the given int array is sorted; <code>false</code> otherwise.
*/
private static boolean isSorted(int[] array) {
for(int i = 1; i < array.length; i++) {
if(array[i] < array[i-1]) {
return false;
}
}
return true;
}
/**
* Sorts a given array (ascending order)
* @param array
* @return
*/
private static int[] sort(int[] array){
//TODO: use multiple threads to speed up the sorting
MergeThread m = new MergeThread(array, 0, array.length);
try{
Thread t1 = new Thread(m);
t1.start();
t1.join();
}catch(InterruptedException e){
}
return m.list;
}
}
類然而，這歸併排序不起作用。控制檯打印很多java.lang.OutOfMemmoryError's unable to create new native thread。
後來則消息變爲類似java heap。
我有什麼改變來排序得到的合併工作，我怎麼使用java.lang.Runtime中的是什麼？
將* exact *堆棧跟蹤複製到您的發佈中，然後突出顯示與該跟蹤對應的代碼行。 – Anon 2011-05-07 19:40:06
順便說一句，即使你已經正確地實現排序，如果你想並行的每一個分區，你會嘗試創建* O（NlogN）*線程。除了一個非常小的數組之外，哪個會失敗。線程是有限的資源。 – Anon 2011-05-07 19:44:05