Параллельная сортировка, не находя верхние числа

Question

Я пишу программу, которая должна найти 25 верхних чисел в большом массиве, используя потоки. Мой алгоритм работает нормально, однако при сравнении результата с Arrays.sort-ed версией исходного массива кажется, что мой лучший 25-список пропускает некоторые из чисел. Мне очень жаль публиковать этот код в вопросе, но я полностью застрял в этом и уже пару часов. Мне хотелось бы помочь выяснить, что случилось. Вот мои классы:

Main.java

import java.util.Arrays; 
import java.util.Random; 

public class Main { 
    public static void main(String[] args) { 
     final int NUM_THRS = 4; 

     int[] numbers = new int[500]; 
     Random generator = new Random(500); 

     for(int i = 0; i < numbers.length; i++) { 
      numbers[i] = Math.abs(generator.nextInt()); 
     } 

     Thread[] thrs = new Thread[NUM_THRS]; 
     NumberThread[] nthrs = new NumberThread[NUM_THRS]; 

     long startTime = System.currentTimeMillis(); 

     for(int i = 0; i < thrs.length; i++) { 
      int start = getStart(i, thrs.length, numbers.length); 
      int stop = getStop(i, thrs.length, numbers.length); 

      nthrs[i] = new NumberThread(numbers, start, stop); 
      thrs[i] = new Thread(nthrs[i]); 
      thrs[i].start(); 
     } 

     for (int i = 0; i < thrs.length; i++) { 
      try { 
       thrs[i].join(); 
      } catch (InterruptedException e) { 
       e.printStackTrace(); 
      } 
     } 

     int[] top = new int[25]; 
     int[] indices = new int[NUM_THRS]; 

     for (int i = 0; i < indices.length; i++) { 
      indices[i] = 24; 
     } 


     for(int i = 0; i < top.length; i++) { 
      top[i] = getMax(nthrs, indices); 
     } 

     for (int i = 0; i < top.length; i++) { 
      System.out.println(top[i]); 
     } 

    } 

    public static int getMax(NumberThread[] thrs, int[] indices) { 
     int maxNum = 0; 
     int maxIdx = 0; 
     for(int i = 0; i < indices.length; i++) { 
      if(indices[i] >= 0) { 
       if(thrs[i].topNums[indices[i]] > maxNum) { 
        maxNum = thrs[i].topNums[indices[i]]; 
        maxIdx = i; 
       } 
      } 
     } 
     System.out.println("iterate"); 
     indices[maxIdx] = indices[maxIdx]-1; 
     return maxNum; 
    } 

    public static int getStart(int i, int total, int len) { 
     return i*len/total; 
    } 

    public static int getStop(int i, int total, int len) { 
     if(i != total-1) { 
      return (i+1)*len/total; 
     } 

     return len-1; 
    } 
} 

NumberThread.java

public class NumberThread implements Runnable { 

    int start, stop; 
    int[] numbers; 
    int[] topNums; 

    public NumberThread(int[] numbers, int start, int stop) { 
     this.numbers = numbers; 
     this.start = start; 
     this.stop = stop; 
     this.topNums = new int[25]; 

     System.out.println(start + " " + stop); 
    } 

    @Override 
    public void run() { 
     for (int i = start; i <= stop; i++) { 
      inner: for (int j = topNums.length-1; j > 0; j--) { 
       if(numbers[i] > topNums[j]) { 
        topNums[j] = numbers[i]; 
        break inner; 
       } 
      } 
     } 
    } 
} 

Цифры, напечатанные после магистралью не являются такими же, как верхние числа, когда я Массивы. сортируйте массив чисел и распечатайте верхнюю часть 25. Некоторые цифры, кажется, отсутствуют.

Большое спасибо.

Answer 1

Я думаю, что ваш метод RunType класса NumberThread не делает то, что он должен делать. Он должен найти 25 самых больших номеров в разделе, который вы ему назначили, например, если массив, который вы ищете, уже отсортирован, тогда 25 самых больших чисел могут быть в 1 разделе, но то, что он на самом деле делает, это перезапись первого найденного им числа это меньше, чем текущее число, поэтому вы получаете менее 25 номеров, и они могут быть не самыми большими.

Для примера рассмотрим последовательность 98 99 1 2 3 ... 98 получили бы написал topNums [19], но затем переписывается 99.

Я также не уверен, что функции getMax, кажется, пытайтесь объединить различные массивы topNums вместе; однако массивы не сортируются, поэтому я не вижу, как это может работать.