Java:赛车 Arrays.sort

Question

我对 QuickSort 进行了一些改进，并决定针对 Java Arrays.sort() 对其进行测试。

结果令人着迷:

在 Java 6 上:

• 我的时间/系统时间 = 74/83 = 0.891566265060241
• 我的时间/系统时间 = 75/79 = 0.9493670886075949
• 我的时间/系统时间 = 75/84 = 0.8928571428571429

在 Java 7 上:

• 我的时间/系统时间 = 115/70 = 1.6428571428571428
• 我的时间/系统时间 = 101/76 = 1.3289473684210527
• 我的时间/系统时间 = 102/61 = 1.6721311475409837

如您所见，我的算法在 Java 6 上表现更好，但我不明白它在 Java 7 上的表现如何急剧下降。也许你能找到原因？

编辑:我的算法是如何工作的:

• 第 1 步:取 3 个数字，对它们进行排序，以中间数字为基准
• 第 2 步:将所有大于 pivot 的数字移到右侧，将所有小于 pivot 的数字移到左侧，并将 pivot 放在排序数组中的最终位置。这实际上在 O(N) 中实现。
• 第 3 步:对左侧和右侧递归地重复第 1 步和第 2 步。当您的子数组小于 12 个元素时，使用网络排序对其进行排序。

我的源代码

public class QuickSort {

    public static void sort(int[] source) {
        int buffer[] = new int[source.length];
        concatenate(source, buffer, 0, source.length);
    }

    private static void concatenate(int[] source, int[] buffer, int low, int high) {
        int count = high - low;
        int lowBuffer = low;
        int highBuffer = high;

        if (count < 2) {
            return;
        }

        if (count < 12) {
            networkSort(source, buffer, low, count);
            return;
        }
        int pivotIndex = bestOfThree(source, low);
        int value = source[pivotIndex];

        for (int i = low; i < high; i++) {
            if (i == pivotIndex) {
                continue;
            }
            if (source[i] < value) {
                buffer[lowBuffer] = source[i];
                source[lowBuffer] = buffer[lowBuffer];
                lowBuffer++;
            }
            else {
                highBuffer--;
                buffer[highBuffer] = source[i];
            }
        }

        buffer[lowBuffer] = source[lowBuffer] = value;
        for (int i = lowBuffer; i < high; i++) {
            source[i] = buffer[i];
        }

        concatenate(source, buffer, lowBuffer + 1, high);
        concatenate(source, buffer, low, lowBuffer);
    }

    private static int bestOfThree(int[] source, int low) {
        int a = low;
        int b = a + 1;
        int c = a + 2;
        int median = -1;

        if (source[a] >= source[b] && source[a] >= source[c]) {
            if (source[b] < source[c]) {
                median = c;
            }
            else {
                median = b;
            }
        }
        else if (source[b] >= source[a] && source[b] >= source[c]) {
            if (source[a] < source[c]) {
                median = c;
            }
            else {
                median = a;
            }
        }
        else if (source[c] >= source[a] && source[c] >= source[b]) {
            if (source[a] < source[b]) {
                median = b;
            }
            else {
                median = a;
            }
        }
        return median;
    }

    private static int[][] networkSort = { 
            { 0, 1 }, 
            { 1, 2, 0, 2, 0, 1 },
            { 0, 1, 2, 3, 0, 2, 1, 3, 1, 2 },
            { 0, 1, 3, 4, 2, 4, 2, 3, 1, 4, 0, 3, 0, 2, 1, 3, 1, 2 },
            { 1, 2, 4, 5, 0, 2, 3, 5, 0, 1, 3, 4, 2, 5, 0, 3, 1, 4, 2, 4, 1, 3, 2, 3 },
            { 1, 2, 3, 4, 5, 6, 0, 2, 3, 5, 4, 6, 0, 1, 4, 5, 2, 6, 0, 4, 1, 5, 0, 3, 2, 5, 1, 3, 2, 4, 2, 3 }, 
            { 0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 4, 6, 5, 7, 1, 2, 5, 6, 0, 4, 3, 7, 1, 5, 2, 6, 1, 4, 3, 6, 2, 4, 3, 5, 3, 4 },
            { 0, 1, 3, 4, 6, 7, 1, 2, 4, 5, 7, 8, 0, 1, 3, 4, 6, 7, 2, 5, 0, 3, 1, 4, 5, 8, 3, 6, 4, 7, 2, 5, 0, 3, 1, 4, 5, 7, 2, 6, 1, 3, 4, 6, 2, 4, 5, 6, 2, 3 },
            { 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 1, 4, 6, 9, 0, 3, 5, 8, 0, 2, 3, 6, 7, 9, 0, 1, 2, 4, 5, 7, 8, 9, 1, 2, 4, 6, 7, 8, 3, 5, 2, 5, 6, 8, 1, 3, 4, 7, 2, 3, 6, 7, 3, 4, 5, 6, 4, 5 },
            { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 0, 2, 4, 6, 8, 10, 1, 2, 5, 6, 9, 10, 0, 4, 3, 7, 1, 5, 6, 10, 4, 8, 5, 9, 2, 6, 0, 4, 3, 8, 1, 5, 6, 10, 2, 3, 8, 9, 1, 4, 7, 10, 3, 5, 6, 8, 2, 4, 7, 9, 5, 6, 3, 4, 7, 8 }
        };

    private static int tmp;

    private static void networkSort(int[] source, int[] buffer, int low, int count) {
        int[] networkData = networkSort[count - 2];

        for (int i = 0; i < networkData.length; i += 2) {
            int index1 = low + networkData[i];
            int index2 = low + networkData[i + 1];

            if (source[index1] > source[index2]) {
                tmp = source[index1];
                buffer[index1] = source[index1] = source[index2];
                buffer[index2] = source[index2] = tmp;
            }
        }
    }   
}

基础测试类

public abstract class Test {
    protected int[][] buffer;
    private final Random random = new Random();

    public int numberOfTests = 100;
    public int maxValue = 1000;
    public int numberOfItems = 100;

    protected void createBuffer() {
        buffer = new int[numberOfTests][];
        for (int i = 0; i < numberOfTests; i++) {
            int[] list = new int[numberOfItems];
            addRandomNumbers(list);
            buffer[i] = list;
        }
    }

    protected void createBuffer(int...parametes) {
        buffer = new int[1][];
        buffer[0] = parametes;
    }

    protected void addRandomNumbers(int[] list) {
        for (int i = 0; i < numberOfItems; i++) {
            int value = random.nextInt(maxValue);
            list[i] = value;
        }
    }

    protected int[][] cloneBuffer() {
        int[][] clonedBuffer =  new int[numberOfTests][];
        for(int i = 0; i < buffer.length; i++){
            int[] clonedList = new int[buffer[i].length];
            int[] list = buffer[i];
            for (int j = 0; j < list.length; j++) {
                int element = list[j];
                clonedList[j] = element;
            }
            clonedBuffer[i] = clonedList;
        }
        return clonedBuffer;
    }

    public abstract void test();
}

性能测试

public class PerformanceTest extends Test {

    private final Timer timer = new Timer();

    public void test() {
        createBuffer();

        timer.reset();
        testSystem();
        timeResoult("System");

        timer.reset();
        testMy();
        timeResoult("My List");
    }

    public void test(int numberOfTests) {
        long myTotalTime = 0;
        long systemTotalTime = 0;

        for (int i = 0; i < numberOfTests; i++) {
            createBuffer();

            timer.reset();
            testSystem();
            long systemTime = timeResoult();
            systemTotalTime += systemTime;

            timer.reset();
            testMy();
            long myTime = timeResoult();
            myTotalTime += myTime;

            System.out.println("My Time / System Time = " + myTime + " / " + systemTime + " = \t"
                    + ((double) myTime / systemTime));
        }
        System.out.println("My Time / System Time = " + ((double) myTotalTime / systemTotalTime));

    }

    private long timeResoult() {
        return timeResoult(null);
    }

    private long timeResoult(String source) {
        long time = timer.check();
        if (source != null) {
            System.out.println(source + ">\tTime: " + time);
        }
        return time;
    }

    private void testMy() {
        int[][] buffer = cloneBuffer();
        for (int i = 0; i < numberOfTests; i++) {
            int[] list = buffer[i];
            QuickSort.sort(list);
        }
    }

    private void testSystem() {
        int[][] buffer = cloneBuffer();
        for (int i = 0; i < numberOfTests; i++) {
            int[] list = buffer[i];
            Arrays.sort(list);
        }
    }
}

主要内容

public static void main(String[] args) {
        PerformanceTest testBasics = new PerformanceTest();
        testBasics.numberOfTests = 1000;
        testBasics.numberOfItems = 1000;
        testBasics.maxValue = 1000000;
        testBasics.test(100);
    }

Answer 1

他们更改了 Java 7 的 Arrays.sort 排序算法。对于排序对象，Arrays.sort 现在使用称为 Timsort 的算法。和原语的双枢轴快速排序。更多信息在此 answer .

如果你真的想使用旧的，显然你可以设置一个系统属性 java.util.Arrays.useLegacyMergeSort。

参见 Java 7 compatibility documentation .