如何將全部和全部比較分成相同大小的塊進行並行化？

Question

我知道這一定是相當基本的用例，但我不知道要搜索什麼關鍵字。

給定一個嵌套的for循環是這樣的：

for (i = 0; i < size; i++) { 
    for (j = i+1; j < size; j++) { 
    doComparision(i, j); 
    } 
} 

我知道我可以計算，其中n =大小*（大小-1）/ 2。

的問題是比較的總數我想要並行化這個循環。每個線程只應該執行外部for-loop的一定範圍：

for (i = beginOffset; i <= endOffset; i++) { 
    for (j = i+1; j < size; j++) { 
    doComparision(i, j); 
    } 
} 

如何計算這些循環中的比較次數？

最後我想確保每個線程的工作量大致相同。

Answer 1

它可能會簡化這一點，但這裏是一個公式，應該工作：

n = (end-begin+1)*(size-begin-1) - (end-begin+1)*(end-begin)/2 

下面是每個術語，可能有助於理解爲什麼這個作品的描述：

• (end-begin+1)：外循環迭代
• (size-begin-1)：內循環迭代
• 的最大數量10：1 + 2 + ... +（end - begin）