V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yusuzhan
V2EX  ›  程序员

为什么我的选择排序比插入排序快?

  •  1
     
  •   yusuzhan · 2019-07-02 15:24:14 +08:00 · 3386 次点击
    这是一个创建于 1731 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚刚开刷红宝书,好奇测了一下发现 Java 实现的选择排序比插入排序速度快,个人推测是 JVM 上交换位置操作比对比操作消耗大。 当然还是担心是我自己粗心导致的,请大家帮忙看下, tldr 的可以直接看最后面的运行结果。

    选择排序

    public static void sort(Comparable[] a) {
            int min = 0;
            for (int i = 0; i < a.length; i++) {
                min = i;
                for (int j = i + 1; j < a.length; j++) {
                    if (less(a[j], a[min])) {
                        min = j;
                    }                
                }
                exch(a, i, min);
            }
        }
    

    插入排序

    public static void sort(Comparable[] a) {
            for (int i = 0; i < a.length - 1; i++) {
                for (int j = i + 1; j > 0; j--) {                
                    if (less(a[j], a[j-1])) {                    
                        exch(a, j, j - 1);
                    } else {
                        break; 
                    }                                    
                }            
            }
        }
    

    性能对比

    public static void timeTest(int n, int repeat) {
            double selectionSortTime = 0;        
            long compareInSelection = 0;
            long swapInSelection = 0;
    
            double bubbleSortTime = 0;
            
            double insertionSortTime = 0;
            long compareInInsertion = 0;
            long swapInInsertion = 0;
    
            for (int i = 0; i < repeat; i++) {
                Integer[] arr0 = genRandomArray(n);        
                Integer[] arr1 = copyArray(arr0);
                Integer[] arr2 = copyArray(arr0);
    
                Stopwatch stopwatch0 = new Stopwatch();            
                SelectionSort.sort(arr0);
                selectionSortTime += stopwatch0.elapsedTime();
                compareInSelection += SelectionSort.compare;
                swapInSelection += SelectionSort.swap;
    
                Stopwatch stopwatch1 = new Stopwatch();            
                BubbleSort.sort(arr1);
                bubbleSortTime += stopwatch1.elapsedTime();
    
                Stopwatch stopwatch2 = new Stopwatch();            
                InsertionSort.sort(arr2);
                insertionSortTime += stopwatch2.elapsedTime();
                compareInInsertion += InsertionSort.compare;
                swapInInsertion += InsertionSort.swap;
            }
            StdOut.printf("algorithm        avg    compare    swap\n");
            StdOut.printf("SelectionSort    %f  %d  %d\n", selectionSortTime / repeat, compareInSelection / repeat, swapInSelection / repeat);
            StdOut.printf("BubbleSort       %f  \n", bubbleSortTime / repeat);
            StdOut.printf("InsertionSort    %f  %d  %d\n", insertionSortTime / repeat, compareInInsertion / repeat, swapInInsertion / repeat);
        }
    

    打印结果

    algorithm        avg    compare    swap
    SelectionSort    0.001032  499500  1000
    BubbleSort       0.001788  
    InsertionSort    0.001293  250824  249831
    
    20 条回复    2019-12-12 21:10:17 +08:00
    davie
        1
    davie  
       2019-07-02 15:27:43 +08:00 via Android
    数据量多大?
    yusuzhan
        2
    yusuzhan  
    OP
       2019-07-02 15:28:58 +08:00
    @davie 数组长度 1000,repeat 5000 次测平均值
    davie
        3
    davie  
       2019-07-02 15:42:00 +08:00 via Android
    随机性呢?
    yusuzhan
        4
    yusuzhan  
    OP
       2019-07-02 15:50:58 +08:00
    @davie 随机性用的红宝书里提供的库,描述是 uniformly

    ```
    /**
    * Rearranges the elements of the specified array in uniformly random order.
    *
    * @param a the array to shuffle
    * @throws IllegalArgumentException if {@code a} is {@code null}
    */
    public static void shuffle(Object[] a) {
    validateNotNull(a);
    int n = a.length;
    for (int i = 0; i < n; i++) {
    int r = i + uniform(n-i); // between i and n-1
    Object temp = a[i];
    a[i] = a[r];
    a[r] = temp;
    }
    }
    ```
    yusuzhan
        5
    yusuzhan  
    OP
       2019-07-02 15:52:18 +08:00
    @davie 在我的电脑上,临界点是 270,超过这个超度的数组,都是选择快
    AmmeLid
        6
    AmmeLid  
       2019-07-02 15:53:16 +08:00
    用数组来做插入排序,还要考虑插入后数据移动的开销吧。
    wutiantong
        7
    wutiantong  
       2019-07-02 16:00:32 +08:00
    很可能是 exch 引入了额外的开销
    yusuzhan
        8
    yusuzhan  
    OP
       2019-07-02 16:03:55 +08:00
    @wutiantong 真没啥,书里原文

    ```
    private static void exch(Comparable[] a, int i, int j) {
    swap++;
    final Comparable swap = a[i];
    a[i] = a[j];
    a[j] = swap;
    }
    ```
    xuwei0056
        9
    xuwei0056  
       2019-07-02 16:07:19 +08:00
    创建 Comparable 的开销大?
    jmc891205
        10
    jmc891205  
       2019-07-02 16:08:10 +08:00
    你再测一下 less 和 exch 的速度好了
    wutiantong
        11
    wutiantong  
       2019-07-02 16:14:53 +08:00
    @yusuzhan 排序算法的性能评估只看比较操作(less)的次数,交换操作(exch)则应尽量降低影响。

    你的这个 exch 恐怕比 less 还要慢一丢丢。
    lance6716
        12
    lance6716  
       2019-07-02 16:19:54 +08:00 via Android
    我咋记得插入排序不是这么写…一个一个往后移,而不是交换
    yusuzhan
        13
    yusuzhan  
    OP
       2019-07-02 16:30:19 +08:00
    @jmc891205 @wutiantong
    测了一下,exch 速度确实慢很多

    compareTime = 0.006
    exchTime = 1.306
    yusuzhan
        14
    yusuzhan  
    OP
       2019-07-02 16:31:42 +08:00
    @xuwei0056 用的 Integer 数组,创建的开销没算, 只统计的排序的速度。刚才看了一下, 确实是 exch 速度比 less 慢导致的。
    wizardoz
        15
    wizardoz  
       2019-07-02 17:24:27 +08:00
    选择排序移动很少,插入排序有很多移动
    算法书上的时间复杂度是以比较次数来计的。
    littlewing
        16
    littlewing  
       2019-07-03 02:27:39 +08:00 via Android
    复杂度低并不代表任何情况下速度就快,因为复杂度算得是极限
    capljf
        17
    capljf  
       2019-12-12 19:53:46 +08:00
    我的 mac pro 上也是选择排序比插入排序快,100 ~ 10000 个 double 随机数,用 StdRandom.shuffle 打乱了。100 ~ 10000 次都试了,都是选择比插入快。搞得我检查了好几遍代码是不是写反了,但代码确实没问题。还得继续找原因
    capljf
        18
    capljf  
       2019-12-12 19:58:26 +08:00
    我猜是插入排序没有做优化,因为每次比较都做了 exch,exch 比较耗时,我去按书上的优化一下,将较大元素都往右移动而不是总是 exch。访问数组的次数能减少一半
    capljf
        19
    capljf  
       2019-12-12 21:07:28 +08:00
    为啥回复不了了,提示验证手机号
    capljf
        20
    capljf  
       2019-12-12 21:10:17 +08:00
    好像我的回复有些词被 block 了。简单说下,刚刚是我的代码写得有问题,插入是比选择快的,优化后的代码 swap 次数确实比优化前少一半左右
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2997 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 14:42 · PVG 22:42 · LAX 07:42 · JFK 10:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.