使用多线程

Question

我是这个小组的新手，所以我相信可以在这里获得帮助，因为我在Google上找不到有关我问题的任何信息。

我正在尝试实现java factodd换位排序。因此，当我算法时，我认为分为分区是一个好主意：

1. 如何知道我应该将数组列表划分多少部分？例如，我现在使用17个元素使其更容易理解。
2. 另外，我不知道我是否应该使用所谓的执行人员服务或正常创建线程。

我在此处添加我当前的逻辑：从奇数阶段开始，然后分为两个部分，然后分配两个线程以进行这些比较，此后创建了等待线程的障碍，因此启动其他线程以类似地与偶数索引一起使用。感谢您可以给我的任何帮助。目前，我不知道如何实现此算法，因此任何单词都可能会有所帮助。 ：//i.sstatic.net/osvjl.png“ alt =”在此处输入图像描述”>

Answer 1

如何知道我应该将几个部分划分我的数组列表？例如，我现在使用17个元素使其更容易理解。

您将数组分为子阵列的直觉是正确的，因为它通常是并发排序算法的基础。如您所知，我们只需要讨论实现：

1. 直观的解决方案就是为每个奇数索引创建thread比较swap和join（）它们到主线程等待结果。 rince并重复此n次。但是，这是非常低效的，因为创建和启动所有o（n^2）线程的开销对于快速比较和换档而言，这远远大。
2. 我们还可以为每个奇数索引创建线程，并使其在左右之间反复比较和交换。这是有问题的，因为我们必须反复左右锁定（以防止数据竞赛），这将导致调度程序的许多无用的开销，我们不知道何时完成。
3. 最后，我们可以为每个奇数索引创建线程，还可以使它们在左右之间反复交替，并且每次都使它们在障碍物上等待。对于我来说，这似乎是正确的选择，因为它可以最大程度地减少线程管理开销，还限制了无用的比较和数据竞赛。

这使我们获得了以下代码：

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），这不是对这种并行算法的最佳选择。您可以尝试在Parrallel中实现的另一种算法是 noreflow noreferrer“ >算法。您可以与此相关的很多东西，但是最重要的是合并，因为它是顺序算法中的瓶颈。您可以查看 nofollow noreferrer“> strong>或查看其他并行合并。

另外，我不知道我是否应该使用“执行人员服务”或正常创建线程。

Java为并行性提供了许多不同的工具，这些工具在不同级别的抽象级别运行。可以说 比基本线程更“高级”，因为它简化了线程管理。它还将优化任务的调度，以使执行更好。

这是我们的实现，使用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();}
        }
    }   
}

如您所见，我们使用的是线程 factory newfixedthreadpool静态方法生成和刻有所有胎面。然后，我们将任务添加到线程池中，将返回a 未来 变量。 Future将在线程完成时（在我们的情况为null）时保持值。呼叫 .get（） 方法将等待结果（因此要完成的线程）。请注意，您想实现某种嵌套的线程偏中性主义（例如，在平行Mergesort时）。您应该使用 > 专门为此而制作。最后，在这里是一个关于executorService 。