在多个线程中对数组进行洗牌

Question

我有一个大小为N的数组。我想要将它的元素在2个或更多线程中进行洗牌。每个线程应该使用自己的数组部分进行操作。

比如说，第一个线程对从0到K的元素进行洗牌，第二个线程对从K到N的元素进行洗牌（其中0 < K < N）。所以，它可以看起来像这样：

//try-catch stuff is ommited
static void shuffle(int[] array) {
   Thread t1 = new ShufflingThread(array, 0, array.length / 2);
   Thread t2 = new ShufflingThread(array, array.length / 2, array.length);
   t1.start();
   t2.start();
   t1.join();
   t2.join();
}

public static void main(String[] args) {
   int array = generateBigSortedArray();
   shuffle(array);
}

JVM能保证在这样的洗牌后，我能从主方法中看到数组array的变化吗？

为了得到这样的保证，我应该如何实现ShufflingThread（或者说，我应该如何运行它，也许是在synchronized块内或其他地方）？

- Roman

---

我猜任何线程级别的缓存在 join() 返回后就会结束，所以最终你必须在没有声称它为 volatile 的情况下在 array 中获取一致的数据。但是在共享数组的情况下，我不是完全确定。也许复制数组的其中一半并将其传递给其中一个线程是个好主意。 - 9000

仅供参考，这个任务非常适合Java 7 Fork/join API，http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/。 - Andrew

你将面临的问题是前半部分的元素永远不会出现在后半部分，反之亦然。因此，您正在洗牌两个独立的数组（恰好出现在同一个对象中），即您并未对整个数组进行洗牌。如果您以这种方式洗牌纸牌，您可能每次都会得到所有黑色纸牌先于所有红色纸牌的情况。 - Peter Lawrey

@Peter Lawrey：谢谢，这是一个有用的观点。 - Roman

Answer 1

join() 方法足以确保内存一致性：当 t1.join() 返回时，主线程会“看到”线程 t1 在数组上执行的任何操作。

此外，Java 保证数组不会出现字撕裂（word-tearing）的情况：不同的线程可以在没有同步的情况下使用同一数组的不同元素。

- Thomas Pornin

Answer 2

我认为这是一个很好的线程控制练习，其中（1）一个作业可以被分成几个部分（2）这些部分可以独立且异步地运行（3）主线程监视各个线程中这些作业的完成情况。你需要的就是让这个主线程等待()并在每个线程完成执行时被notify()-ed jobCount次。以下是一段示例代码，您可以进行编译/运行。取消println（）的注释以查看更多信息。

注意事项：[1]JVM不保证线程执行顺序[2]当主线程访问大数组时，您需要同步以避免数据损坏....

public class ShufflingArray {

private int nPart = 4,      // Count of jobs distributed, resource dependent
        activeThreadCount,  // Currently active, monitored with notify
        iRay[];         // Array the threads will work on

    public ShufflingArray (int[] a) {
    iRay = a;
    printArray (a);
}

private void printArray (int[] ia) {
    for (int i = 0 ; i < ia.length ; i++)
        System.out.print (" " + ((ia[i] < 10) ? " " : "") + ia[i]);
    System.out.println();
    }

public void shuffle () {
    int startNext = 0, pLen = iRay.length / nPart;  // make a bunch of parts
    for (int i = 0 ; i < nPart ; i++, activeThreadCount++) {
        int start = (i == 0) ? 0 : startNext,
            stop = start + pLen;
        startNext = stop;
        if (i == (nPart-1))
            stop = iRay.length;
        new Thread (new ShuffleOnePart (start, stop, (i+1))).start();
    }
    waitOnShufflers (0);        // returns when activeThreadCount == 0
    printArray (iRay);
}

synchronized private void waitOnShufflers (int bump) {
    if (bump == 0) {
        while (activeThreadCount > 0) {
            // System.out.println ("Waiting on " + activeThreadCount + " threads");
            try {
                wait();
            } catch (InterruptedException intex) {
    }}} else {
        activeThreadCount += bump;
        notify();
}}

public class ShuffleOnePart implements Runnable {
    private int startIndex, stopIndex;      // Operate on global array iRay

    public ShuffleOnePart (int i, int j, int k) {
        startIndex = i;
        stopIndex = j;
        // System.out.println ("Shuffler part #" + k);
    }

    // Suppose shuffling means interchanging the first and last pairs
    public void run () {
        int tmp = iRay[startIndex+1];
        iRay[startIndex+1] = iRay[startIndex];  iRay[startIndex] = tmp;
        tmp = iRay[stopIndex-1];
        iRay[stopIndex-1] = iRay[stopIndex-2];  iRay[stopIndex-2] = tmp;
        try {   // Lets imagine it needs to do something else too
            Thread.sleep (157);
        } catch (InterruptedException iex) { }
        waitOnShufflers (-1);
}}

public static void main (String[] args) {
    int n = 25, ia[] = new int[n];
    for (int i = 0 ; i < n ; i++)
        ia[i] = i+1;
    new ShufflingArray(ia).shuffle();

}}

- Manidip Sengupta

Answer 3

使用Thread.start()和Thread.join()足以为您提供数组初始化、其交接给线程，然后在主方法中读取的关系。

导致happens-before的操作在此处有记录。

正如在其他地方提到的那样，ForkJoin非常适合这种分而治之的算法，并使您免于实现许多簿记工作。

- Jed Wesley-Smith

Answer 4

使用java.util.Concurrent包中的ExecutorService和Callable任务，从每个线程运行中返回数组的一部分，一旦两个线程都完成，这是实现一致行为的另一种方法。

- Dead Programmer

Answer 5

嗯，它们不能同时访问同一个数组，如果你使用锁、互斥量或任何其他同步机制，你会失去线程的优势（因为一个线程必须等待另一个线程完成洗牌或完成一部分洗牌）。 为什么不将数组分成两半，给每个线程它的一部分数组，然后合并这两个数组呢？

- Ricardo Ferreira