我的多線程程序出了什麼問題？

Question

我想寫希爾排序的multhithreaded版本Java的

這是單線程版本

import java.util.*; 
import java.util.Scanner.*; 

class Test 
{   
    public static void main (String [] args) 
    { 
     double [] list = new double [10000]; 
     for (int i = 0; i < 10000; i++) 
      list[i] = 10000 - i; 
     long startTime = System.currentTimeMillis(); 
     shellSort(list); 
     int elapsedTime = (int) (System.currentTimeMillis() - startTime); 
     System.out.println ("Time = " + elapsedTime); 
     for (double i : list) 
      System.out.print (i + " "); 

    } 
    public static void shellSort(double [] list) 
    { 
     int i, increment; 
     int [] k = {1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484}; 
     for (i = k.length - 1; k[i] > list.length; i--); 
     for (i--; i >= 0; i--) 
     { 
      increment = k[i]; 
      int upper = 2 * increment; 
      for (int count = increment; count < upper; count++) 
       insertionSort(list, increment, count); 
     } 
    } 
    public static void insertionSort(double [] list, int increment, int position) 
    { 
     for (int top = position; top < list.length;) 
     { 
      double item = list[top]; 
      int i = top; 
      while (i - increment >= 0 && item < list[i - increment]) 
      { 
       list[i] = list[i - increment]; 
       i -= increment; 
      } 
      list[i] = item; 
      top += increment; 
     } 
    } 

} 

代碼這是多線程版本

import java.util.*; 
import java.util.Scanner.*; 

class MT extends Thread 
    { 
     double[] list; 
     int increment, position; 
     MT (double [] a, int b, int c) 
     { 
      list = a; 
      increment = b; 
      position = c; 
     } 
     public void run() 
     { 
      for (int top = position; top < list.length;) 
      { 
       double item = list[top]; 
       int i = top; 
       while (i - increment >= 0 && item < list[i - increment]) 
       { 
        list[i] = list[i - increment]; 
        i -= increment; 
       } 
       list[i] = item; 
       top += increment; 
      } 
     } 
    } 


class Test 
{ 
    public static void main (String [] args) 
    { 
     double [] list = new double [10000]; 
     for (int i = 0; i < 10000; i++) 
      list[i] = 10000 - i; 
     long startTime = System.currentTimeMillis(); 
     shellSort(list); 
     int elapsedTime = (int) (System.currentTimeMillis() - startTime); 
     System.out.println ("Time = " + elapsedTime); 
     for (double i : list) 
      System.out.print (i + " "); 

    } 
    public static void shellSort(double [] list) 
    { 
     int i, increment; 
     int [] k = {1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484}; 
     for (i = k.length - 1; k[i] > list.length; i--); 
     for (i--; i >= 0; i--) 
     { 
      increment = k[i]; 
      int upper = 2 * increment; 
      for (int count = increment; count < upper; count+=2) 
      { 
       new MT(list, increment, count).start(); 
       new MT(list, increment, count + 1).start(); 
      } 
     } 
    }  
} 

代碼

多線程版本比單線程版本花費的時間要長得多。兩者都提供正確的輸出，多線程版本使用我的3個內核而不是2個。什麼導致我的多線程程序放緩？我能想到的唯一的事情是，當我打電話給MT課程時，我正在創建包含數字的數組？

謝謝。

Answer 1

創建新的Thread的開銷非常大。它看起來像您可以在包含

new MT(list, increment, count).start(); 

考慮使用thread pool減少初始化開銷嵌套for語句創建了一堆線程。

Answer 2

這是我用來創建多線程處理循環的模式。我已經使用了幾十次，非常成功。該模式總是相同的：shel

public class Test { 

    // the Task encapsulates the work to be done 
    public static class TestTask extends FutureTask<Doulbe[]> { 
     public TestTask(TestWorker worker) { 
      super(worker); 
     } 
    } 

    // the worker does the work, extends Callable 
    public static class TestWorker extends Callable<Double[]> { 
     public Double[] unsortedList; 
     public Double[] call() throws Exception { 
       // do the work, return the array of Doubles... 
       Double[] results = shellSort(unsortedList); 
       // do other stuff 
       return results; 
     }  
    } 

    public static void main (String [] args) { 

     BlockingQueue<Runnable> queue = new LinkedBlockingDeque<Runnable>(); 
     // use a constant sized thread pool of 15 threads 
     ThreadPoolExecutor tpe = new ThreadPoolExecutor(15, 15, 1000L, TimeUnit.SECONDS, queue); 
     CopyOnWriteArrayList<TestTask> allTasks = new CopyOnWriteArrayList<TestTask>(); 
     for (int i = 0; i < 10000; i++) { 
      TestWorker worker = new TestWorker(); 
      worker.unsortedList = // your list to be sorted... 
      TestTask task = new TestTask(worker); 
      allTasks.add(task); 
      tpe.execute(task); 
     } 

     do { 
      // basically just loop until all tasks are finished. 
      // might be good to throw in a Thread.sleep(10000) here too 
      for (TestTask task : allTasks) { 
       if (task.isDone()) { 
        // if the task is done, remove it from the arraylist 
        // remember to remove the task before getting the results 
        allTasks.remove(task); 
        try { 
         Double[] sortedList = task.get(); 
         // do something with the output. 
        } catch (Exception e) { 
         LOGGER.error("Task threw exception...", e); 
        } 
       } 
      } 
     } while (allTasks.size() > 0); 



    } 

}