logo标签列表

Java整数比较：大于

javacomparisoninteger
6

我正在尝试并行快速排序，因此有一个包含一百万个整数的数组。 有时候会出现以下奇怪的行为：

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

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），也没问题。 我错过了什么吗？
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);
            }
        }
    }

我在启动并行排序的线程上执行了一个join。 第一个线程最多同时生成4个线程。 我不确定它可能是什么并发性，因为我可以在调试器中看到数组已排序。 我将输出两个整数的总和并再次查看。
编辑23/05/12 16:46 UTC+1
我正在更改整个内容以使用JDK 1.7新而真正简单的ForkJoinPool。 对10百万个整数的整数数组进行了测试，并得到了有趣的结果：
我已在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个排序迭代中计算平均值。
3
为什么不发布生成输出的确切代码。 这肯定不是关于>操作符错误的问题。 发布一个完整的SSCCE以重现您的问题。 - Marko Topolnik
1
很难在没有看到代码的情况下确定，但可能是由于并发问题导致的，在排序算法期间进行的某些更改对检查结果的线程不可见。 - assylias
3
没有适当的同步，仅仅完成了工作的线程并不能保证任何事情。这些线程可能仍然存在，并且可能有一些线程本地存储尚未提交到主内存中。 - Marko Topolnik
2
是的，在线程t1的代码中，你是否对它启动的所有4个线程进行了join？这非常重要。 - Marko Topolnik
1
你其实不需要那个线程t1。你只需要在Quicksort_Parallel中生成的线程，并确保你加入了每一个生成的线程。这样你的问题就解决了。 - Marko Topolnik
显示剩余14条评论
3个回答
3

看着你的代码，你创建了一个线程，但是立即将它加入到主执行线程中:

        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 程序中做了什么？你是否正在生成其他线程？你是否对所有线程进行了加入？如果没有，那么你已经创建了竞争条件，这可能解释了你所看到的结果。
正如我在上面的评论中提到的，我的quicksort_parallel可能会产生多达3个其他线程。我没有在那里进行join - 所以正如我们所说，这是一种竞争条件。如果我在quicksort_parallel中进行join，我的排序速度比“正常”的quicksort要慢得多。 - Stefan
创建线程会带来额外的开销。所要执行的工作是否足够大，以从并行性中受益呢？ - Mike
我测试了高达1000万个整数。 - Stefan
1
你可能成为竞争条件的受害者，这意味着你的输出结果取决于其他事件的顺序。如果某个线程工作得更快，就会发生竞争条件。防止这种情况的方法是使用信号量或将循环划分到不同的线程中。你正在进行怎样的排序？你正在使用还原吗？
1
谢谢你的提示 - 我今天在另一个版本中实现了ForkJoinPool，平均加速比约为1.5，用于1百万个整数。将生成一个包含多达1亿个整数的大型测试，并进行尝试。但是1.5仍然不多，也不是我期望和希望的结果。 - Stefan
它是Intel Core2Duo处理器（2010年款）。我会在家里与晚期2011的Core-i5进行交叉检查。 - Stefan
如果线程数超过核心数，性能可能会下降，因为核心必须在线程之间切换。 - Puce
这是一个逻辑链接，但也涉及到CPU的知识。Core2Duo和i5可以进行超线程，所以我现在使用availableProcessors（）* 2进行测试-> Core2Duo在1000万个整数时得到了一点提升，为1.8; 2个线程为1.7; i5目前在每个availableProcessors（）* 2的8个线程下速度提高了3.2倍。我想我证明了我想要的东西，感谢这里一些非常好的提示和问题解决者！ - Stefan
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接