При распараллеливании быстрой сортировки в Java потоки никогда не возвращаются обратно при join (). Зачем?

Question

У меня есть простой код паралеллизации алгоритма QuickSort в Java, в методе run я каждый раз создаю два отдельных новых потока для распараллеливания обработки элементов Array. Но поскольку он встречает операторы join () для обоих созданных потоков, потоки никогда не возвращаются назад и не останавливаются в joins (), кажется, что join () никогда не освобождает их.

Ниже приведен код.

class StartJoinQuickSort implements Runnable 
{
    private int m_Low, m_High;
    private int[] m_Array = null;

    private final static int NR_OF_VALUES = 10; // TOTAL_NO_VALUES
    private int PivotElement;   
    private static Random m_random = new Random( );


    public StartJoinQuickSort(int[] a_Array,int a_Low,int a_High)
    {
        this.m_Array = a_Array;
        this.m_Low = a_Low;
        this.m_High = a_High;
    }
    private void SwapArrayElements(int a_i,int a_j)
    {
        int temp = this.m_Array[a_i];
        this.m_Array[a_i] = this.m_Array[a_j];
        this.m_Array[a_j] = temp;

    }// end of SwapArrayElements

    private static int nextRandomFunctionValue(int aStart, int aEnd)
    {
        if ( aStart > aEnd )
        {
           throw new IllegalArgumentException("Start cannot exceed End.");
        }

        //get the range, casting to long to avoid overflow problems
        long range = (long)aEnd - (long)aStart + 1;

        // compute a fraction of the range, 0 <= frac < range

        long fraction = (long)(range * m_random.nextDouble());
        int randomNumber =  (int)(fraction + aStart);    
        return randomNumber;

    }// end of nextRandomFunctionValue

    private static int[] GetArrayWithRandomValues()
    {
        int[] ArrayToBePopulatedWithRandomValues  = new int[NR_OF_VALUES];
        for(int index =0; index<NR_OF_VALUES;index++)
        {
            int RandomValue = StartJoinQuickSort.nextRandomFunctionValue(0,NR_OF_VALUES);
            ArrayToBePopulatedWithRandomValues[index] =  RandomValue;

        }//end of for

        return ArrayToBePopulatedWithRandomValues;

    }//end of GetArrayWithRandomValues
    private int middleIndex(int left, int right) 
    {
        return left + (right - left) / 2;
    }
    public int Partition(int a_Start,int a_end)
    {
    //  System.out.println("Partition ..thId : " + Thread.currentThread().getId());
        int pivotIndex = 0;

        int i = a_Start;
        int j = a_end;

        try
        {
            pivotIndex = middleIndex(a_Start , a_end);
            this.PivotElement = this.m_Array[pivotIndex];

            do
            {
                while(this.m_Array[i] < PivotElement )
                    i++;

                if(j>0)
                {
                    try
                    {
                        while( this.m_Array[j] > PivotElement )
                            j--;
                    }
                    catch(Exception ex){System.out.println(" j : " + j);}

                }//end of if

                if(i<=j)
                {
                    SwapArrayElements(i,j);

                //  System.out.println("Swap .." + + Thread.currentThread().getId());

                    i++;
                    j--;

                }//end of if

            }while(i<=j);
        }
        catch(Exception except)
        {
            System.out.println("exception in Partition " + except);
        }
        return j;
    }

    public void run()  
    {

        //System.out.println("in run..");


        //System.out.println("after PARTITION");

        StartJoinQuickSort oStartQuickSort_1 = null;
        StartJoinQuickSort oStartQuickSort_2 = null;



        if(this.m_Low < this.m_High )
        {
            int Index = Partition(this.m_Low,this.m_High);



            Thread thPart_1 = new Thread ( new StartJoinQuickSort( this.m_Array,this.m_Low,Index ) );
            Thread thPart_2 = new Thread ( new StartJoinQuickSort( this.m_Array,Index + 1,this.m_High ) );

            thPart_1.start();   thPart_2.start();


        //}//end of if
        //if( Index + 1 < this.m_High)
        //{         
            try
            {           
                    thPart_1.join(); thPart_2.join();

            }catch (InterruptedException e) { e.printStackTrace();}         
        }
    }//end of run

С уважением Усман

Answer 1

Что произойдет, если у вас, например, низкий = 0, высокий = 1?Если ваш Раздел возвращает 1, у вас будет бесконечный цикл потоков, верно?

Answer 2

Хммм, никогда не стоит реализовывать рекурсивный алгоритм параллельно таким образом. В конечном итоге вы создадите огромное количество потоков (экспоненциальных на каждом уровне) и в конечном итоге перепишете систему.

Лучшая идея - иметь точку отсечения, которая, скажем, равна количеству доступных ядер. Затем, когда текущий уровень рекурсии имеет количество ветвей, равное точке среза, переключается на последовательную быструю сортировку. Какой-то очень грубый псевдокод потока:

parallel_quicksort(level, interval) {
    // compute subintervals interval1, interval2
    if(level < cutoff) { 
        spawn1: parallel_quicksort(level + 1, interval1);
        spawn2: parallel_quicksort(level + 1, interval2);

        join1();     
        join2();
    } else {
        quicksort(interval1);
        quicksort(interval2);
    }
}

Также посмотрите на эту реализацию, чтобы увидеть, что вы что-то пропустили: http://www.inf.fh -flensburg.de / lang /gorithmen / sortieren / quick / quicken.htm

Answer 3

Спасибо всем за ваши добрые предложения и советы.Я сам обнаружил проблему.это было с функцией Partition, которая не работала нормально, у нее были некоторые проблемы, я выбрал другую, и она работала нормально для меня ..

Процедура создания нового раздела:

public int Partition (int [] a_Array, int a_Left, int a_Right) {// выбрал среднее значение диапазона для нашего пивота int pivotValue = a_Array [middleIndex (a_Left, a_Right)];

    --a_Left;
    ++a_Right;

    while (true)
    {
        do
            ++a_Left;
        while (a_Array[a_Left] < pivotValue);

        do
            --a_Right;
        while (a_Array[a_Right] > pivotValue);

        if (a_Left < a_Right)           
            SwapArrayElements(a_Left,a_Right);
        else
        {
            return a_Right;
        }
    }
}

Answer 4

join () блокирует, если ваш поток не заканчивается. Вы должны определить, почему ваши темы не заканчиваются. Можете ли вы попробовать отладить вашу программу с помощью отладчика?