concurrent Threads Merge Сортировка

Question

Мне нужно закодировать параллельное приложение для сортировки слияния. Каждый раз, когда массив распадается, мне нужно создать новый поток для правой половины (максимальное число потоков - 5 -> так 5 раз), которое продолжает алгоритм Mergesort.

Вот моя программа:

class Mergesorts implements Runnable{ 

    private int[] internal; 

    Mergesorts(int[] arr) { 
     internal = arr; 
    } 

    private void processCommand(int [] array) { 
     if (array.length > 1) { 
      int[] left = leftHalf(array); 
      int[] right = rightHalf(array); 
      processCommand(left); 
      processCommand(right); 
      merge(array, left, right); 
     } 
    } 

    public int[] rightHalf(int[] array) { 
     int size1 = array.length/2; 
     int size2 = array.length - size1; 
     int[] right = new int[size2]; 
     for (int i = 0; i < size2; i++) { 
      right[i] = array[i + size1]; 
     } 
     return right; 
    } 

    public void run() { 
     processCommand(internal); 
    } 
} 

Как я могу переписать свой код, чтобы сортировать одновременно, как описано выше?

Как я могу изменить свой код, чтобы он создавал до 5 потоков и не более?

private void processCommand(int [] array) { 
    if (array.length > 1) { 


     int[] right = rightHalf(array); 
     int[] left = leftHalf(array); 


     Mergesorts worker2 = new Mergesorts(right); 
     Thread s = new Thread(worker2); 
     s.start(); 

     processCommand(left); 

     try { 
      s.join(); 
     } catch (InterruptedException e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
     } 

     merge(array, left, right);} 

} 

Answer 1

Начать новую тему в методе processCommand(), а не в методе rightHalf(). Если у вас есть потоки, то вместо строки, вызывающей processCommand (справа), создайте новый объект Mergesorts на right и начните с ним поток. Не забудьте вызвать join() в потоке, чтобы убедиться, что он завершен до слияния.

Чтобы улучшить параллелизм, вы можете начать новый поток в правой половине массива перед обработкой левой половины массива, так что оба выполняются одновременно - то есть, переместите processCommand (слева) на после block, который либо выполняет processCommand (справа), либо запускает новый поток. Вызов join() должен быть после завершения обеих половин, но перед слиянием.

Редактировать: вы приближаетесь; обратиться комментарий, вам нужно что-то вроде этого:

private void processCommand(int [] array) { 
    if (array.length <= 1) 
     {return;} 

    int[] left = leftHalf(array); 
    int[] right = rightHalf(array); 
    Thread rightThread = null; 

    if (b <= 5) { 
     ++b; 
     Mergesorts worker = new Mergesorts(right); 
     rightThread = new Thread(worker); 
     rightThread.start(); 
    } else { 
     processCommand(right); 
    } 

    processCommand(left); 

    if (null != rightThread) { 
     try { 
      rightThread.join(); 
      b-- 
     } catch (InterruptedException e) { 
      // TODO Auto-generated catch block 
      e.printStackTrace(); 
      // better error handling would be good 
     } 
    } 

    merge(array, left, right); 
} 

b также должна быть неустойчивыми, чтобы обеспечить различные темы можно увидеть, сколько потоков в текущий момент.