Многопоточная сортировка массива 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

Хорошо, есть несколько проблем:

Сначала ваш размер массива слишком велик. Вот почему вам не хватает памяти (8000000), следует попробовать с небольшим числом, скажем, 1000. Даже с этим ваш код, вероятно, потерпит крах в другом месте, как он есть.

Во-вторых, ваш код имеет мало смысла, поскольку вы используете смешанные статические и нестатические вызовы ... например, Thread.currentThread().sleep(1000) странно, вы не в текущей теме.

Создание потока, в котором вы выполняете Array.sort.

Я предлагаю сначала создать простую многопоточную программу, а затем заняться сортировкой. Также рекомендуется реализовать интерфейс Runnable, а не расширять класс Thread для создания рабочего класса.

Answer 2

Что ж, вам не хватает памяти, разрешенной для использования J.V.M ..

Я не проверял, что ваш алгоритм корректен, но вы должны попробовать код с гораздо меньшим массивом, чтобы увидеть, работает ли он нормально, скажем, 1000.

Вы делаете несколько копий массива (или хотя бы частичных копий) по всей вашей программе в виде потоков. Затем каждый поток выделяет большое количество данных. По этой причине вы можете пересмотреть свой дизайн, или вы по-прежнему столкнетесь с этой проблемой. Если вы не найдете способа сократить это распределение, и мой следующий абзац вам не поможет, вам, возможно, придется прибегнуть к использованию файлов для сортировки этих больших массивов, вместо того, чтобы пытаться хранить все в памяти сразу.

Вы можете увеличить размер кучи, следуя инструкциям на этой странице (первая ссылка, которую я нашел, но она содержит правильную информацию): http://viralpatel.net/blogs/2009/01/jvm-java-increase-heap-size-setting-heap-size-jvm-heap.html Это позволит вам выделить больше памяти из вашей Java-программы.

Answer 3

while (arrayFirst.length != 0 && arraySecond.length != 0){

здесь это входит в infinite loop, когда conditions удовлетворены и, следовательно, memory heap получает OutOfMemoryError

Это совсем не terminated, поэтому вы должны включить некоторый код в terminate этот цикл.