与 Java 期货合并排序

Question

我正在尝试编写一个使用 java 期货的合并排序算法。我目前使用期货的程序比标准合并排序算法慢。我更愿意使用 java 期货而不是 fork join，因为我目前正在学习 java 期货。我正在尝试在并行流中工作，建议最好在未来有一半的工作，一半的工作在主线程中。


import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class MParallelSorter1 implements Sorter {
    
    private static final ExecutorService pool = Executors.newFixedThreadPool(10);
    private MSequentialSorter s = new MSequentialSorter();

  @Override
  public <T extends Comparable<? super T>> List<T> sort(List<T> list) {
      
      if(list.size() < 2){
          
          return list;
      }else {
      int mid = list.size()/2;
      Future<List<T>> left = pool.submit(()->sort(list.subList(0, mid)));
      List<T> right = sort(list.subList(mid, list.size()));
      
      return mergeSort(get(left), right);
          
      }
    }
  

  public <T extends Comparable<? super T>> List<T> mergeSort(List<T> left, List<T> right) {
        int i = 0, j = 0, k = 0;
        List<T> toReturn = new ArrayList<>();
            
  
      while (i < left.size() && j < right.size()) {
            if (left.get(i).compareTo(right.get(j)) < 0)  {
                toReturn.add(k, left.get(i));
                i++;
            } else {
                toReturn.add(k, right.get(j));
                j++;
            }
            k++;
        }

        while (i < left.size()) {
            toReturn.add(k, left.get(i));
            i++;
            k++;
        }

        while (j < right.size()) {
            toReturn.add(k, right.get(j));
            j++;
            k++;
        }
  
        
    return toReturn;   
}


  public static <T> T get (Future<T> f) {
      try {
          return f.get();
      }
      catch (InterruptedException e) {
        Thread.currentThread().interrupt();
        throw new Error(e);
    }
    catch (ExecutionException e) {
        Throwable t = e.getCause();
        if(t instanceof RuntimeException rt) {
            throw rt;
        }
        if(t instanceof Error et) {
            throw et;
        }
        throw new Error("Unexpected Checked Exception", t);
    }
    
  }
}```

Answer 1

您是否尝试过将 Executors.newFixedThreadPool(10) 更改为 Executors.newWorkStealingPool()？

与 Java 期货合并排序

Merge Sort with Java Futures

java

mergesort

concurrent.futures