Ben sadece bir şey tökezledi. İlk başta in this case ama ben şube misprediction bu fenomen neden neden açıklayamaz gibi şube misprediction bir durum olabileceğini düşündüm. Java Kabarcık Sıralama iki versiyonu hayata ve bazı performans testleri yaptı

import java.util.Random;

public class BubbleSortAnnomaly {

    public static void main(String... args) {
        final int ARRAY_SIZE = Integer.parseInt(args[0]);
        final int LIMIT = Integer.parseInt(args[1]);
        final int RUNS = Integer.parseInt(args[2]);

        int[] a = new int[ARRAY_SIZE];
        int[] b = new int[ARRAY_SIZE];
        Random r = new Random();
        for (int run = 0; RUNS > run;   run) {
            for (int i = 0; i < ARRAY_SIZE; i  ) {
                a[i] = r.nextInt(LIMIT);
                b[i] = a[i];
            }

            System.out.print("Sorting with sortA: ");
            long start = System.nanoTime();
            int swaps = bubbleSortA(a);

            System.out.println(  (System.nanoTime() - start)   " ns. "
                                 "It used "   swaps   " swaps.");

            System.out.print("Sorting with sortB: ");
            start = System.nanoTime();
            swaps = bubbleSortB(b);

            System.out.println(  (System.nanoTime() - start)   " ns. "
                                 "It used "   swaps   " swaps.");
        }
    }

    public static int bubbleSortA(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i;   j) {
                if (a[j] > a[j   1]) {
                    swap(a, j, j   1);
                      counter;
                }
            }
        }
        return (counter);
    }

    public static int bubbleSortB(int[] a) {
        int counter = 0;
        for (int i = a.length - 1; i >= 0; --i) {
            for (int j = 0; j < i;   j) {
                if (a[j] >= a[j   1]) {
                    swap(a, j, j   1);
                      counter;
                }
            }
        }
        return (counter);
    }

    private static void swap(int[] a, int j, int i) {
        int h = a[i];
        a[i] = a[j];
        a[j] = h;
    }
}

Gördüğünüz gibi, bu iki sıralama yöntemleri arasındaki tek fark > vs >=. java BubbleSortAnnomaly 50000 10 10 ile program çalışırken belli ki sortB sortA daha yavaş olduğunu beklenir. Ama aşağıdaki (veya benzer) üç farklı makinelerde çıkış var:

Sorting with sortA: 4.214 seconds. It used  564960211 swaps.
Sorting with sortB: 2.278 seconds. It used 1249750569 swaps.
Sorting with sortA: 4.199 seconds. It used  563355818 swaps.
Sorting with sortB: 2.254 seconds. It used 1249750348 swaps.
Sorting with sortA: 4.189 seconds. It used  560825110 swaps.
Sorting with sortB: 2.264 seconds. It used 1249749572 swaps.
Sorting with sortA: 4.17  seconds. It used  561924561 swaps.
Sorting with sortB: 2.256 seconds. It used 1249749766 swaps.
Sorting with sortA: 4.198 seconds. It used  562613693 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749880 swaps.
Sorting with sortA: 4.19  seconds. It used  561658723 swaps.
Sorting with sortB: 2.281 seconds. It used 1249751070 swaps.
Sorting with sortA: 4.193 seconds. It used  564986461 swaps.
Sorting with sortB: 2.266 seconds. It used 1249749681 swaps.
Sorting with sortA: 4.203 seconds. It used  562526980 swaps.
Sorting with sortB: 2.27  seconds. It used 1249749609 swaps.
Sorting with sortA: 4.176 seconds. It used  561070571 swaps.
Sorting with sortB: 2.241 seconds. It used 1249749831 swaps.
Sorting with sortA: 4.191 seconds. It used  559883210 swaps.
Sorting with sortB: 2.257 seconds. It used 1249749371 swaps.

Örneğin, 12* * LIMIT (java BubbleSortAnnomaly 50000 50000 10)parametre ayarlarken, beklenen sonuçlar:

Sorting with sortA: 3982697438 ns. It used 625941897 swaps.
Sorting with sortB: 4657909823 ns. It used 789391382 swaps.

Bu sorun Java özgü olup olmadığını belirlemek için C program taşıdık. İşte C kodu.

#include <cstdlib>
#include <iostream>

#include <omp.h>

#ifndef ARRAY_SIZE
#define ARRAY_SIZE 50000
#endif

#ifndef LIMIT
#define LIMIT 10
#endif

#ifndef RUNS
#define RUNS 10
#endif

void swap(int * a, int i, int j)
{
    int h = a[i];
    a[i] = a[j];
    a[j] = h;
}

int bubbleSortA(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; i > 0; --i)
    {
        for (int j = 0; j < i;   j)
        {
            int next = j   1;
            if (a[j] > a[next])
            {
                swap(a, j, next);
                  counter;
            }
        }
    }
    return (counter);
}

int bubbleSortB(int * a)
{
    const int LAST = ARRAY_SIZE - 1;
    int counter = 0;
    for (int i = LAST; i > 0; --i)
    {
        for (int j = 0; j < i;   j)
        {
            int next = j   1;
            if (a[j] >= a[next])
            {
                swap(a, j, next);
                  counter;
            }
        }
    }
    return (counter);
}

int main()
{
    int * a = (int *) malloc(ARRAY_SIZE * sizeof(int));
    int * b = (int *) malloc(ARRAY_SIZE * sizeof(int));
    for (int run = 0; RUNS > run;   run)
    {
        for (int idx = 0; idx < ARRAY_SIZE;   idx)
        {
            a[idx] = std::rand() % LIMIT;
            b[idx] = a[idx];
        }

        std::cout << "Sorting with sortA: ";
        double start = omp_get_wtime();
        int swaps = bubbleSortA(a);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;

        std::cout << "Sorting with sortB: ";
        start = omp_get_wtime();
        swaps = bubbleSortB(b);

        std::cout << (omp_get_wtime() - start) << " seconds. It used " << swaps
                  << " swaps." << std::endl;
    }

    free(a);
    free(b);

    return (0);
}

Bu program aynı davranışı gösterir. Biri burada neler olduğunu açıklayabilir mi?

sortB sortA sonra yürütme sonuçlarını değiştirmez.

Gerçekten şube tahmin kaynaklanıyor olabilir bence. Eğer iç tür yineleme sayısına göre swapları sayısını sayarsan bulabilirsin

= 10 sınırı

• = 560 swapları / 1250M döngüler
• B = 1250M swapları / 1250M loops (döngüler daha 0.02% daha az swap)

50000 = Limit

• = 627M swapları / 1250M döngüler
• B = 850 / 1250M döngüler getirir

Yani Limit == 10 Bu durumda takas şube tahmini için açıkçası uygun B sıralama zaman 99.98% gerçekleştirilir. Limit == 50000 bu durumda takas sadece 68% rastgele vurmak şube tahmini daha az faydalıdır.