Java - 多線程一個大循環

Question

這可能是一個非常簡單的問題，但是因爲我從未與線程一起工作過，所以我認爲最好問問題而不是嘗試完全依靠自己找到最佳解決方案。

我有一個巨大的for循環運行幾十億次。在循環運行中，根據當前的index，程序以數字形式計算最終結果。我只對存儲頂部result（或頂部x個結果）及其相應的索引感興趣。

我的問題很簡單，在線程中運行此循環的正確方式是什麼，因此它使用所有可用的CPU /內核。

int topResultIndex; 
double topResult = 0; 

for (i=1; i < 1000000000; ++i) { 
    double result = // some complicated calculation based on the current index 
    if (result > topResult) { 
     topResult = result; 
     topResultIndex = i; 
    } 
} 

該計算是完全獨立的每個索引，沒有資源共享。每個線程都會明顯訪問topResultIndex和topResult。

*更新：Giulio's和rolfl的解決方案都很好，也非常相似。只能接受其中之一作爲我的回答。

Answer 1

假設這個結果是由calculateResult(long)方法，它是私有的，靜態的計算，並且不訪問任何靜態字段，（也可以是非靜態的，但它仍然必須是線程安全的，併發可執行的，希望線程受限）。

然後，我認爲這會做骯髒的工作：

public static class Response { 
    int index; 
    double result; 
} 

private static class MyTask implements Callable<Response> { 
    private long from; 
    private long to; 

    public MyTask(long fromIndexInclusive, long toIndexExclusive) { 
     this.from = fromIndexInclusive; 
     this.to = toIndexExclusive; 
    } 

    public Response call() { 
     int topResultIndex; 
     double topResult = 0; 

     for (long i = from; i < to; ++i) { 
      double result = calculateResult(i); 
      if (result > topResult) { 
       topResult = result; 
       topResultIndex = i; 
      } 
     } 

     Response res = new Response(); 
     res.index = topResultIndex; 
     res.result = topResult; 
     return res; 
    } 
}; 

private static calculateResult(long index) { ... } 

public Response interfaceMethod() { 
    //You might want to make this static/shared/global 
    ExecutorService svc = Executors.newCachedThreadPool(); 

    int chunks = Runtime.getRuntime().availableProcessors(); 
    long iterations = 1000000000; 
    MyTask[] tasks = new MyTask[chunks]; 
    for (int i = 0; i < chunks; ++i) { 
     //You'd better cast to double and round here 
     tasks[i] = new MyTask(iterations/chunks * i, iterations/chunks * (i + 1)); 
    } 

    List<Future<Response>> resp = svc.invokeAll(Arrays.asList(tasks)); 
    Iterator<Future<Response>> respIt = resp.iterator(); 

    //You'll have to handle exceptions here 
    Response bestResponse = respIt.next().get(); 

    while (respIt.hasNext()) { 
     Response r = respIt.next().get(); 
     if (r.result > bestResponse.result) { 
      bestResponse = r; 
     } 
    } 

    return bestResponse; 
} 

從我的經驗，這種劃分成塊的速度要快得多，有一個任務，每個索引（尤其是如果每個單項指標的計算負載是小的，就像它可能是小的，我的意思是不到半秒）。然而，編碼有點困難，因爲你需要進行兩步最大化（首先是塊級，然後是全局級）。有了這個，如果計算純粹是基於cpu的（不推動ram太多），你應該得到的加速幾乎等於物理內核數量的80％。

Answer 2

最簡單的方法是使用ExecutorService並將您的任務作爲Runnable或Callable提交。您可以使用Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors())創建一個ExeuctorService，它將使用與處理器相同數量的線程。

Answer 3

除了觀察到使用OpenMP或某些其他並行計算擴展的C程序會是一個更好的想法之外，Java的方式是創建一個'Future'Task來計算問題的一個子集：

private static final class Result { 
    final int index; 
    final double result; 
    public Result (int index, double result) { 
     this.result = result; 
     this.index = index; 
    } 
} 

// Calculate 10,000 values in each thead 
int steps = 10000; 
int cpucount = Runtime.getRuntime().availableProcessors(); 
ExecutorService service = Executors.newFixedThreadPool(cpucount); 
ArrayList<Future<Result>> results = new ArrayList<>(); 
for (int i = 0; i < 1000000000; i+= steps) { 
    final int from = i; 
    final int to = from + steps; 
    results.add(service.submit(new Callable<Result>() { 
     public Result call() { 
       int topResultIndex = -1; 
       double topResult = 0; 
       for (int j = from; j < to; j++) { 
        // do complicated things with 'j' 
         double result = // some complicated calculation based on the current index 
         if (result > topResult) { 
          topResult = result; 
          topResultIndex = j; 
         } 
       } 
       return new Result(topResultIndex, topResult); 
     } 
    }); 
} 

service.shutdown(); 
while (!service.isTerminated()) { 
    System.out.println("Waiting for threads to complete"); 
    service.awaitTermination(10, TimeUnit.SECONDS); 
} 
Result best = null; 
for (Future<Result> fut : results) { 
    if (best == null || fut.result > best.result) { 
     best = fut; 
    } 
} 

System.out.printf("Best result is %f at index %d\n", best.result, best.index); 

Future<Result>