0

我最近一直在处理线程，只是想就某事提出建议。我将函数代码放在这里只是为了解决任何歧义。

private void sort() throws FileNotFoundException, InterruptedException{

    int i;         
    int largest = data.get(0) ;
    int n = fullsize;//data.getsize
    int [ ] tmp = new int [ n ] ;

    for ( i = 1; i < n ; i++)
        if ( largest < data.get(i) )
        largest = data .get(i) ;
    int [ ] count = new int [ largest+1] ;

    for ( i = 0 ; i <= largest; i++)
        count [ i ] = 0 ;

    for ( i = 0 ; i < n ; i++)
        count [ data .get(i) ]++;

    for ( i =0+ 1 ; i <= largest; i++)
    {     
        count [ i ] =count[i]+count[i-1];
        output=  output.concat(Integer.toString(count[i]));
    }

    System.out.print("Thread "+Thread.currentThread().getId()+":"+ output+"\n");


    /* for(int b=0; i<count.length;b++)
          System.out.print(count[b]);*/
    for (i=n-1; i >= 0; i--)
    {
        tmp [count[data.get(i)] -1] = data.get(i);
        count[data.get(i)]--;
    }

    for ( i =0 ; i < n ; i++)
    { 
        data.add(i, tmp[i]);
    }


}

这个函数基本上只是以相当复杂的方式对链表进行排序，不过我必须使用这个函数。这就是我想做多线程的功能。但是现在我的问题是，如果每个线程或多或少地完成相同数量的工作，您将如何做到这一点？我有点想将数组拆分为多个部分，然后将每个部分发送到按线程排序？但我不确定这是否是这样做的。朝着正确方向的任何一点都会很棒。

4

1 回答 1

1

拆分数组允许并行排序，也允许并行合并。例如，考虑以下数组：

[3, 2, 6, 4, 9, 7, 12, 1]

这可以分成如下部分：

[3, 2, 6, 4], [9, 7, 12, 1]

从这里，双方可以并行排序。如果这些仍然太大，可以再次拆分它们。但是，第二次拆分可以并行进行。这将产生以下结果：

[3, 2], [6, 4], [9, 7], [12, 1]

这些都可以并行排序，产生：

[2, 3], [4, 6], [7, 9], [1, 12]

现在我们可以向后工作，并行合并。一个并行合并步骤可以产生：

[2, 3, 4, 6], [1, 7, 9, 12]

从这里开始，只剩下一个合并步骤，不能并行完成：

[1, 2, 3, 4, 6, 7, 9, 12]

一般的想法是拆分输入，直到它具有适当的大小以直接处理，然后对其进行排序。然后合并作为拆分的反面，就像拆分一样，它可以并行完成。

Java 的Fork/Join Pool特别适合这类问题，这里有一个关于它的使用教程。

于 2013-08-24T03:27:03.197 回答