java - Java多线程数组排序

Question

你好!

我正在尝试使用多个线程对 int 数组进行排序。现在我得到了这样的东西:

import java.util.Arrays;


public class MultiTread extends  Thread{

int sizeOfArray;
public static int treadsN = 4;
public  static  int sortFrom;
public  static  int sortTo;

public MultiTread(int sizeOfArray, int treadsN) {
    this.sizeOfArray = sizeOfArray;
    this.treadsN = treadsN;
}

public MultiTread(int[] arrayToSort, int sizeOfArray) {
    this.sizeOfArray = sizeOfArray;
}



public static int [] creatingArray(int sizeOfArray) {
    int [] arrayToSort = new int[sizeOfArray];
    int arrayLength = arrayToSort.length;
    for (int counter = 0; counter<arrayLength; counter++){
        arrayToSort[counter] = (int)(8000000*Math.random());
    }
    return arrayToSort;
}

public  static  int [] sortInSeveralTreads(final int [] arrayToSort){
    int [] newArr = new int[arrayToSort.length];
    int numberOfThreads = treadsN;
    if (numberOfThreads == 0){
        System.out.println("Incorrect value");
        return arrayToSort;
    }
    if (numberOfThreads == 1){
        Arrays.sort(arrayToSort);
        System.out.println("Array sorted in 1 thread");
    } else {
         final int lengthOfSmallArray = arrayToSort.length/numberOfThreads;
        sortFrom = 0;
        sortTo = lengthOfSmallArray;
        for (int progress = 0; progress < numberOfThreads; progress++){
            final int [] tempArr = Arrays.copyOfRange(arrayToSort,sortFrom,sortTo);
            new Thread(){public void run() {
                Arrays.sort(tempArr);
            }}.start();
            sortFrom = sortTo;
            sortTo += lengthOfSmallArray;
            newArr =  mergeSort(newArr, tempArr);
        }
        new Thread(){public void run() {
            Arrays.sort(Arrays.copyOfRange(arrayToSort, arrayToSort.length-lengthOfSmallArray, arrayToSort.length));
        }}.start();
        newArr = mergeSort(newArr, arrayToSort);
    }
    return newArr;
}

public static  int [] mergeSort(int [] arrayFirst, int [] arraySecond){
    int [] outputArray = new  int[arrayFirst.length+arraySecond.length];
    while (arrayFirst.length != 0 && arraySecond.length != 0){
        int counter = 0;
        if (arrayFirst[0] < arraySecond[0]){
            outputArray[counter] = arrayFirst[0];
            counter++;
            arrayFirst = Arrays.copyOfRange(arrayFirst, 1, arrayFirst.length);
        }else {
            outputArray[counter] = arraySecond[0];
            counter++;
            arraySecond = Arrays.copyOfRange(arraySecond, 1, arraySecond.length);
        }
    }
    return outputArray;
}


public static void main(String[] args){
    long startTime;
    long endTime;
    int [] a = creatingArray(8000000);
    startTime = System.currentTimeMillis();
    a =  sortInSeveralTreads(a);
    endTime = System.currentTimeMillis();
    System.out.println(Thread.activeCount());
    System.out.printf("Sorted by: %d treads in %.7f seconds %n", treadsN, (float)(endTime-startTime)*1e-6);
    try {
        Thread.currentThread().sleep(1000);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(Thread.activeCount());
}
}

我知道这不是很好的实现。一切正常，但合并排序工作太糟糕 - 它崩溃了......错误应该在该行中:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:3137)
at MultiTread.mergeSort(MultiTread.java:78)
at MultiTread.sortInSeveralTreads(MultiTread.java:61)
at MultiTread.main(MultiTread.java:94)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

我做错了什么？

Answer 1

好吧，您已经用完了 JVM 允许使用的内存..

我还没有检查您的算法是否正确，但您应该使用更小的数组尝试代码，看看它是否正常工作，例如 1000。

您可以在整个程序的线程中制作数组的多个副本(或至少部分副本)。然后每个线程都分配大量数据。因此，您可能希望重新考虑您的设计，否则您将继续遇到此问题。如果您找不到减少此分配的方法，并且我的下一段对您没有帮助，那么您可能需要使用文件来对这些大数组进行排序，而不是尝试一次将所有内容保存在内存中。

您可以按照本页上的说明增加堆大小(我找到的第一个链接，但它具有正确的信息): http://viralpatel.net/blogs/2009/01/jvm-java-increase-heap-size-setting-heap-size-jvm-heap.html这将允许您从 Java 程序中分配更多内存。