我是這個小組的新手，所以我相信有可能在這里獲得幫助，因為我在 Google 上找不到關于我的問題的任何資訊。
我正在嘗試并行實作 Java EvenOdd 轉置排序。因此，在我的演算法中，我認為劃分為磁區將是一個好主意：
- 如何知道我應該劃分我的陣列串列多少部分？例如，我現在使用 17 個元素以使其更易于理解。
- 另外，我不知道我是否應該使用名為 ExecutorService 的東西或只是正常創建執行緒。
我在這里添加我當前的邏輯：從奇數階段開始，分成兩部分并分配兩個執行緒進行這些比較，然后創建一個屏障來等待執行緒，因此啟動其他執行緒以類似地使用偶數索引。感謝您能給我的任何幫助。目前，我不知道如何實作這個演算法，所以任何話都可能會有所幫助。
uj5u.com熱心網友回復：
歡迎來到 StackOverflow！
如何知道我應該劃分我的陣列串列多少部分？例如，我現在使用 17 個元素以使其更易于理解。
您將陣列劃分為子陣列的直覺是正確的，因為它通常是并發排序演算法的基礎。正如你已經知道的演算法，我們只需要討論實作：
thread直觀的解決方案是為每個奇數索引創建一個，start()所有這些索引都用于比較和交換，并將join()它們發送到主執行緒以等待結果。沖洗并重復這N一次。然而，這是非常低效的，因為創建和啟動所有O(N^2)執行緒的開銷對于快速比較和交換來說非常大。- 我們還可以為每個奇數索引創建執行緒，并讓它們在左右之間反復比較和交換。這是有問題的，因為我們必須反復鎖定左右（以防止資料競爭），這會導致調度程式產生大量無用的開銷，并且我們不知道何時完成。
- 最后，我們可以為每個奇數索引創建執行緒，也可以讓它們在左右之間反復交替，并且每次都讓它們在屏障上等待。這對我來說似乎是正確的選擇，因為它最大限度地減少了執行緒管理開銷，也限制了無用的比較和資料競爭。
這導致我們得到以下代碼：
import java.util.Arrays;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
public class OddEvenSort {
public static void main(String[] args) {
int[] arr = {83, 71, 72, 26, 6, 81, 53, 72, 20, 35, 40, 79, 3, 90, 89, 52, 30};
sortArr(arr);
System.out.println(Arrays.toString(arr));
}
public static void sortArr(int[] arr) {
int threadNum = arr.length/2;
CyclicBarrier barr = new CyclicBarrier(threadNum);
Thread[] threads = new Thread[threadNum];
for (int i = 0; i < threadNum; i ) {
threads[i] = new Thread(new CompareSwapThread(arr, 2*i 1, barr));
threads[i].start();
}
for (int i = 0; i < threadNum; i ) {
try {
threads[i].join();
} catch (InterruptedException e) {e.printStackTrace();}
}
}
}
class CompareSwapThread implements Runnable {
private int[] arr;
private int index;
private CyclicBarrier barr;
public CompareSwapThread(int[] arr, int index, CyclicBarrier barr) {
this.arr = arr;
this.index = index;
this.barr = barr;
}
@Override
public void run() {
for (int i = 0; i < arr.length; i ) {
if (arr[index - 1] > arr[index]) {
int t = arr[index - 1];
arr[index - 1] = arr[index];
arr[index] = t;
}
try {
barr.await();
} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}
if (index 1 < arr.length && arr[index] > arr[index 1]) {
int t = arr[index];
arr[index] = arr[index 1];
arr[index 1] = t;
}
try {
barr.await();
} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}
}
}
}
請注意，該演算法的運行時間O(n)對于這種并行演算法來說并不是最佳的。您可以嘗試并行實作的另一種演算法是MergeSort演算法。有很多事情可以用這個并行化，但最重要的是合并，因為它是順序演算法的瓶頸。您可以查看Batcher Odd-Even Mergesort或查看其他并行合并。
另外，我不知道我是否應該使用名為 ExecutorService 的東西或只是正常創建執行緒。
Java 提供了許多不同的并行工具，它們在不同的抽象級別上運行。可以說它ExecutorService比基本執行緒更“高級”，因為它簡化了執行緒管理。它還將優化任務的調度，以使執行更好。
這是我們的實作，使用ExecutorService：
import java.util.Arrays;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class OddEvenSort {
public static void main(String[] args) {
int[] arr = {83, 71, 72, 26, 6, 81, 53, 72, 20, 35, 40, 79, 3, 90, 89, 52, 30};
sortArr(arr);
System.out.println(Arrays.toString(arr));
}
public static void sortArr(int[] arr) {
int threadNum = arr.length/2;
CyclicBarrier barr = new CyclicBarrier(threadNum);
ExecutorService exec = Executors.newFixedThreadPool(threadNum);
Future<?>[] awaits = new Future<?>[threadNum];
for (int i = 0; i < threadNum; i ) {
awaits[i] = exec.submit(new CompareSwapThread(arr, 2*i 1, barr));
}
for (int i = 0; i < threadNum; i ) {
try {
awaits[i].get();
} catch (InterruptedException | ExecutionException e) {e.printStackTrace();}
}
}
}
class CompareSwapThread implements Runnable {
private int[] arr;
private int index;
private CyclicBarrier barr;
public CompareSwapThread(int[] arr, int index, CyclicBarrier barr) {
this.arr = arr;
this.index = index;
this.barr = barr;
}
@Override
public void run() {
for (int i = 0; i < arr.length; i ) {
if (arr[index - 1] > arr[index]) {
int t = arr[index - 1];
arr[index - 1] = arr[index];
arr[index] = t;
}
try {
barr.await();
} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}
if (index 1 < arr.length && arr[index] > arr[index 1]) {
int t = arr[index];
arr[index] = arr[index 1];
arr[index 1] = t;
}
try {
barr.await();
} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}
}
}
}
如您所見，我們使用執行緒工廠 newFixedThreadPool靜態方法來生成和實體化所有執行緒。然后我們將任務添加到執行緒池中，執行緒池將回傳一個Future變數。當執行緒完成時（在我們的例子中為 null）， AFuture將保存該值。呼叫該Future.get()方法將等待結果（因此執行緒完成）。請注意，您想要實作某種嵌套執行緒并行（例如，在并行化 MergeSort 時）。您應該使用ForkJoinPool它是專門為此而制作的。最后，這是一個關于ExecutorService.
如果您需要任何詳細資訊，請隨時在評論中詢問。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/475214.html