java - 在 Java 中并行化快速排序时，线程永远不会在 join() 处返回。为什么？

Question

我有在 Java 中并行化 QuickSort 算法的简单代码，在运行方法中我每次都创建两个单独的新线程来并行化处理数组元素。但是当它遇到两个创建的线程的 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

嗯，像这样并行实现递归算法从来都不是一个好主意。您最终将创建大量线程(在每个级别呈指数级增长)并最终超额订阅系统。

最好的想法是有一个截止点，假设它等于可用内核的数量。然后，当当前递归级别的分支数等于截止点时，切换到顺序快速排序。流程的一些非常粗略的伪代码:

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/algorithmen/sortieren/quick/quicken.htm