我有一个包含一百万个整数的数组，因为我正在试验并行快速排序。 有时我有以下奇怪的行为:

为了检查数组是否排序正确，我在排序后输入了以下代码:

for(int j=0; j < array_parallel.length-1; ++j)
   if(array_parallel[j] > array_parallel[j+1])
    System.out.println("ERROR! NOT SORTED CORRECTLY!");

在某些情况下，我得到错误输出，它没有正确排序，当我调试时，我发现以下内容(示例，总是不同的):

j=1942 array_parallel[1942] = 6000; array_parallel[1943] = 6000;

(尝试忽略数字，它不是任何特定值或范围) 所以它总是在左值等于右值的情况下。 好吧，对于更大的比较，这应该返回 false，但我明确地得到了输出。

这到底是怎么回事!？

我什至交叉检查了数组，它的排序是正确的。如果我绘制一个小数组(大约 100 个)，它也很好。 我是不是漏掉了一些我的想法欺骗了我的东西？

编辑时间 21:32 (UTC+1):

private static int ANZAHL = 1000000;        // Größe des Arrays

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int array_single[] = new int[ANZAHL];
        int array_parallel[] = new int[ANZAHL];

        Speedmeasure sp_single = new Speedmeasure();
        Speedmeasure sp_parallel = new Speedmeasure();
        ArrayReader ar = null;

        try {
            ar = new ArrayReader(array_single, array_parallel);
        } catch (FileNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (IOException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        } catch (ClassNotFoundException e1) {
            // TODO Auto-generated catch block
            e1.printStackTrace();
        }

        if(ar == null) {
            System.err.println("Großes Problem. Lass es sein!");
            System.exit(-1);
        }
        else {

            for(int i=0; i < 5; ++i) {
                Quicksort_Single qs = new Quicksort_Single();
                sp_single.setStart(System.currentTimeMillis());

                qs.quicksort_start(array_single);
                sp_single.setStop(System.currentTimeMillis());

                //printArray(array);
                PrintSpeed(sp_single.getSpeed(), "Single");


                System.out.print("\nUnd jetzt treiben wir es parallel! \n\n");
                Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel));

                sp_parallel.setStart(System.currentTimeMillis());
                t1.start();

                try {
                    t1.join();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }

                sp_parallel.setStop(System.currentTimeMillis());

                //printArray(array_parallel);
                PrintSpeed(sp_parallel.getSpeed(),"Parallel");

                System.out.println("Speed up was: "+sp_parallel.calcSpeedup(sp_single.getSpeed(), sp_parallel.getSpeed()));
                System.out.println("******************************************");

                for(int j=0; j < array_single.length-1; ++j)
                    if(array_single[j] > array_single[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI SINGLE!");

                for(int j=0; j < array_parallel.length-1; ++j)
                    if(array_parallel[j] > array_parallel[j+1])
                        System.out.println("ERROR! NICHT SORTIERT KORREKT BEI PARALLEL!");



                ar.copyArray(array_single, array_parallel);
            }
        }
    }

我在启动并行排序的线程上进行了连接。第一个线程最多同时产生 4 个线程。我不是 100% 确定它可能是什么并发性，正如我在调试器中看到的那样，数组已排序。我将把两个整数的输出相加，再看一眼。

编辑于 23/05/12 16:46 UTC+1

我正在改变整个事情以使用来自 JDK 1.7 的新的、非常简单的 ForkJoinPool。 使用最多 10 个 mio 整数的整数数组进行测试并得到有趣的结果: 我已经在 Core2Duo (2010) MacBook Pro 和 Core-i5 (2011) Windows 7 上对其进行了测试:

core2duo 和 i5 可以进行超线程处理，所以我现在使用 availableProcessors()*2 进行了测试 -> core2duo 的 2 个线程的加速分别提高到了 1.8 和 1.7； i5 目前大约有 3.2 的加速，每个 availableProcessors()*2 有多达 8 个线程

仍在试验我的机器。所有测试均使用相同的数组进行，平均值是根据每个数组大小的 1000 次排序迭代计算得出的。

最佳答案

查看您的代码，您生成了一个线程，但随后立即将其加入主执行线程:

        Thread t1 = new Thread(new Quicksort_Parallel(0, array_parallel.length-1, array_parallel));

        sp_parallel.setStart(System.currentTimeMillis());
        t1.start();

        try {
            t1.join();

问题变成了 - 你在 Quicksort_Parallel 例程中做什么？你在产生额外的线程吗？您是否正在对它们所有 进行连接？否则，您已经创建了一个竞争条件来解释您所看到的结果。

关于Java 整数比较 : greater than，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10708736/