Board logo

標題: [原創] 快速穩定排序法測試 [打印本頁]
作者: linyancheng    時間: 2017-2-12 21:26     標題: 快速穩定排序法測試

快速穩定排序法測試
ˉ
一般的快速排序演算法為不穩定的排序法，
將之改良為穩定的排序法，
命名為「快速穩定排序法」。
（不穩定是指相等元素會被改變順序，反之相等元素會保持相對位置。）
ˉ
測試結果：
一維陣列，10000筆數字，
氣泡排序法為14.299秒
快速穩定排序法為0.082秒
（氣泡排序法為入門的排序法，亦為不穩定的排序法。）
二維陣列，10000x2筆數字
快速穩定排序法為0.198秒（看最右一行資料遞增，表示為穩定排序。）
（不同電腦或Excel版本下，會有不同結果；同電腦或Excel版本下，每次演算也會有些微差距。）
作者: jackyq    時間: 2017-2-12 22:20

本帖最後由 jackyq 於 2017-2-12 22:23 編輯

10000x2  = 0.198秒 算慢了
排序如果用得很兇
應該要用 VC 封裝1下
會是 0.198秒 的 10 倍速
作者: linyancheng    時間: 2017-2-12 22:35

本帖最後由 linyancheng 於 2017-2-12 22:49 編輯

我已經夠用了
而且我沒研究封裝
VBA用那個方便嗎？

而且你有測試過嗎？真有10倍速，懷疑！

測試條件：
陣列用Variant資料型態，因功能需要
二維陣列要能設定排序維度、排序維度的元素起迄範圍、另一維度的元素範圍(1個)，因功能需要
排序後相等元素要保持相對位置，不能被調換。
作者: linyancheng    時間: 2017-2-12 23:19

漏掉了，再加一個條件：
比較模式用option compare text，功能需要
作者: jackyq    時間: 2017-2-12 23:43

夠用就好

每個人 CPU 等級不一樣
只能自己和自己比
計算量 720萬筆
EXCEL + VBA  不穩排 = 15.567 sec
EXCEL + VBA      穩排 = 18.398 sec
EXCEL + VC    不穩排   =   1.547 sec
EXCEL + VC        穩排   =   1.603 sec
作者: linyancheng    時間: 2017-2-13 01:31

本帖最後由 linyancheng 於 2017-2-13 01:39 編輯

回復 5# jackyq


所以封裝的是相同的代碼嗎？
還是有做語言的調整？

真的差那麼多，
難怪Excel本身的排序速度這麼快！

其實我的測試是因為本來用的氣泡排序法太慢，而且是不穩定排序，
所以才寫一個快速穩定排序法來測試看看，
兩者的差距對我已經很夠了！
作者: linyancheng    時間: 2017-2-13 08:30

我的代碼，可幫忙優化嗎？謝謝！

Option Explicit
Option Base 1
Option Compare Text

Public Sub S_二維陣列快速穩定遞增排序_01(ByRef 原始二維陣列 As Variant, ByVal 排序維度 As Long, ByVal 排序元素序 As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

    On Error Resume Next
   
    Dim N As Long
    Dim H As Long
    Dim K As Long
    Dim X As Long
    Dim Y As Long
   
    Dim 陣列限數 As Long
    Dim 基準 As Variant
    Dim 原始二維陣列數 As Long
    Dim 陣列累計數 As Long
   
    Dim 起陣列() As Variant
    Dim 迄陣列() As Variant
    Dim 基陣列() As Variant
   
    陣列限數 = 迄限 - 起限 + 1
   
    If 陣列限數 < 2 Then
        Exit Sub
    End If
   
    If 排序維度 = 1 Then
        基準 = 原始二維陣列((起限 + 迄限) \ 2, 排序元素序)
        原始二維陣列數 = UBound(原始二維陣列, 2) - LBound(原始二維陣列, 2) + 1
        
        ReDim 起陣列(陣列限數 - 1, 原始二維陣列數) As Variant
        ReDim 迄陣列(陣列限數 - 1, 原始二維陣列數) As Variant
        ReDim 基陣列(陣列限數, 原始二維陣列數) As Variant
        
        N = 0
        H = 0
        K = 0
        For X = 起限 To 迄限
            If 原始二維陣列(X, 排序元素序) < 基準 Then
                N = N + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    起陣列(N, Y) = 原始二維陣列(X, Y)
                Next Y
            ElseIf 原始二維陣列(X, 排序元素序) = 基準 Then
                H = H + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    基陣列(H, Y) = 原始二維陣列(X, Y)
                Next Y
            Else
                K = K + 1
               
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    迄陣列(K, Y) = 原始二維陣列(X, Y)
                Next Y
            End If
        Next X
        
        If N > 1 Then
            S_二維陣列快速穩定遞增排序_01 起陣列, 1, 排序元素序, 1, N
        End If
        
        If K > 1 Then
            S_二維陣列快速穩定遞增排序_01 迄陣列, 1, 排序元素序, 1, K
        End If
        
        陣列累計數 = 0
        For X = 起限 To 迄限
            陣列累計數 = 陣列累計數 + 1
            
            If 陣列累計數 <= N Then
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 起陣列(陣列累計數, Y)
                Next Y
            ElseIf 陣列累計數 <= (N + H) Then
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 基陣列(陣列累計數 - N, Y)
                Next Y
            Else
                For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
                    原始二維陣列(X, Y) = 迄陣列(陣列累計數 - N - H, Y)
                Next Y
            End If
        Next X
    Else
        基準 = 原始二維陣列(排序元素序, (起限 + 迄限) \ 2)
        原始二維陣列數 = UBound(原始二維陣列, 1) - LBound(原始二維陣列, 1) + 1
        
        ReDim 起陣列(原始二維陣列數, 陣列限數 - 1) As Variant
        ReDim 迄陣列(原始二維陣列數, 陣列限數 - 1) As Variant
        ReDim 基陣列(原始二維陣列數, 陣列限數) As Variant
        
        N = 0
        H = 0
        K = 0
        For Y = 起限 To 迄限
            If 原始二維陣列(排序元素序, Y) < 基準 Then
                N = N + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    起陣列(X, N) = 原始二維陣列(X, Y)
                Next X
            ElseIf 原始二維陣列(排序元素序, Y) = 基準 Then
                H = H + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    基陣列(X, H) = 原始二維陣列(X, Y)
                Next X
            Else
                K = K + 1
               
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    迄陣列(X, K) = 原始二維陣列(X, Y)
                Next X
            End If
        Next Y
        
        If N > 1 Then
            S_二維陣列快速穩定遞增排序_01 起陣列, 2, 排序元素序, 1, N
        End If
        
        If K > 1 Then
            S_二維陣列快速穩定遞增排序_01 迄陣列, 2, 排序元素序, 1, K
        End If
        
        陣列累計數 = 0
        For Y = 起限 To 迄限
            陣列累計數 = 陣列累計數 + 1
            
            If 陣列累計數 <= N Then
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 起陣列(X, 陣列累計數)
                Next X
            ElseIf 陣列累計數 <= (N + H) Then
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 基陣列(X, 陣列累計數 - N)
                Next X
            Else
                For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
                    原始二維陣列(X, Y) = 迄陣列(X, 陣列累計數 - N - H)
                Next X
            End If
        Next Y
    End If

End Sub
作者: jackyq    時間: 2017-2-14 14:40

http://jackyq.pixnet.net/blog/post/103456672-2017_02_14
作者: linyancheng    時間: 2017-2-14 23:09

回復 8# jackyq


    感謝，真的太強了，先生是讀資訊科系的嗎？

我看出主要利用Index，只要排序一維，再利用Index作多維移動，有效減少排序過程中不必要的反覆移動，維度元素愈多，提速愈明顯，聰明！

另外幾個問題請教：

像：
      Dim value
      For X = 起限 To 迄限
             value = 原始1維陣列(X)
          If value < 基準 Then
             N = N + 1: 起陣列(N) = value: 起陣列_ID(N) = IndexAR(X)
使用 value 一定比較快嗎？雖然不用反覆進行提取「原始1維陣列(X)」，但多一個「value = 原始1維陣列(X)」的動作，以前也想過這個問題。

像：
ReDim Preserve 起陣列(0 To N), 起陣列_ID(0 To N)  'reduce ram consumption
根據我的經驗，ReDim Preserve很耗時，此例可以不用嗎？當然次數或許不多，但也不少。
作者: linyancheng    時間: 2017-2-14 23:26

回復 8# jackyq


    像 UBound(原始二維陣列, 2) 也先代入變數，之後多次則以變數引用，如此是否也會提速？
作者: jackyq    時間: 2017-2-15 17:01

(1) 用 value 會比較快
(2) 當初是因為在你的2維Sub測 AR2D( 1萬 , 300 ) ,看一下 Ram 最高峰可以爆到 600 MB, 才加上去
  現在 Sub 已經改成1維, 遞迴所需量大概會降為 600 MB / 300 = 2 MB , 可以拿掉 ReDim Preserve 會比較快  
(3)  UBound(原始二維陣列, 2) 也先代入變數會比較快, 但通常無感
作者: linyancheng    時間: 2017-2-15 18:02

回復 11# jackyq


    感謝指教，看來你蠻專業的！
作者: linyancheng    時間: 2017-2-17 00:44

最後優化，從原本的0.198秒→0.089秒
  1. Option Explicit
  2. Option Base 1
  3. Option Compare Text

  5. Public Sub S_二維陣列快速插入穩定遞增排序_01(ByRef 原始二維陣列 As Variant, ByVal 排序維度 As Long, ByVal 排序鍵值 As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

  7.     On Error Resume Next
  8.    
  9.     If 起限 >= 迄限 Then
  10.         Exit Sub
  11.     End If
  12.    
  13.     '------------------------------------------------------
  14.    
  15.     Dim X As Long
  16.     Dim Y As Long
  17.    
  18.     Dim 擷取成一維陣列 As Variant
  19.     Dim 索引陣列() As Long
  20.    
  21.     '------------------------------------------------------
  22.    
  23.     ReDim 擷取成一維陣列(起限 To 迄限) As Variant
  24.     ReDim 索引陣列(起限 To 迄限) As Long
  25.    
  26.     If 排序維度 = 1 Then
  27.         For X = 起限 To 迄限
  28.             擷取成一維陣列(X) = 原始二維陣列(X, 排序鍵值)
  29.             索引陣列(X) = X
  30.         Next X
  31.     Else
  32.         For Y = 起限 To 迄限
  33.             擷取成一維陣列(Y) = 原始二維陣列(排序鍵值, Y)
  34.             索引陣列(Y) = Y
  35.         Next Y
  36.     End If
  37.    
  38.     '------------------------------------------------------
  39.    
  40.     二維陣列快速插入穩定遞增排序 擷取成一維陣列, 索引陣列, 起限, 迄限
  41.    
  42.     '------------------------------------------------------
  43.    
  44.     Dim 複製原始二維陣列 As Variant
  45.    
  46.     複製原始二維陣列 = 原始二維陣列
  47.    
  48.     If 排序維度 = 1 Then
  49.         For X = 起限 To 迄限
  50.             For Y = LBound(原始二維陣列, 2) To UBound(原始二維陣列, 2)
  51.                 原始二維陣列(X, Y) = 複製原始二維陣列(索引陣列(X), Y)
  52.             Next Y
  53.         Next X
  54.     Else
  55.         For Y = 起限 To 迄限
  56.             For X = LBound(原始二維陣列, 1) To UBound(原始二維陣列, 1)
  57.                 原始二維陣列(X, Y) = 複製原始二維陣列(X, 索引陣列(Y))
  58.             Next X
  59.         Next Y
  60.     End If

  62. End Sub

  64. Public Sub 二維陣列快速插入穩定遞增排序(ByRef 原始一維陣列 As Variant, ByRef 索引陣列() As Long, ByVal 起限 As Long, ByVal 迄限 As Long)

  66.     On Error Resume Next
  67.    
  68.     If 起限 >= 迄限 Then
  69.         Exit Sub
  70.     End If
  71.    
  72.     '------------------------------------------------------
  73.    
  74.     Dim X As Long
  75.     Dim Y As Long
  76.     Dim S As Long
  77.     Dim M As Long
  78.     Dim E As Long
  79.     Dim N As Long
  80.    
  81.     Dim 暫存 As Variant
  82.     Dim 索引暫存 As Long
  83.     Dim 基準 As Variant
  84.    
  85.     '------------------------------------------------------
  86.    
  87.     If 迄限 - 起限 < 16 Then
  88.         For X = 起限 + 1 To 迄限
  89.             暫存 = 原始一維陣列(X)
  90.             索引暫存 = 索引陣列(X)
  91.             
  92.             For Y = X - 1 To 起限 Step -1
  93.                 If 暫存 >= 原始一維陣列(Y) Then
  94.                     Exit For
  95.                 End If
  96.                
  97.                 原始一維陣列(Y + 1) = 原始一維陣列(Y)
  98.                 索引陣列(Y + 1) = 索引陣列(Y)
  99.             Next Y
  100.             
  101.             原始一維陣列(Y + 1) = 暫存
  102.             索引陣列(Y + 1) = 索引暫存
  103.         Next X
  104.     Else
  105.         Dim 基準陣列(3) As Variant
  106.         
  107.         基準陣列(1) = 原始一維陣列(起限)
  108.         基準陣列(2) = 原始一維陣列((起限 + 迄限) \ 2)
  109.         基準陣列(3) = 原始一維陣列(迄限)
  110.         
  111.         For X = 2 To 3
  112.             暫存 = 基準陣列(X)
  113.             
  114.             For Y = X - 1 To 1 Step -1
  115.                 If 暫存 >= 基準陣列(Y) Then
  116.                     Exit For
  117.                 End If
  118.                
  119.                 基準陣列(Y + 1) = 基準陣列(Y)
  120.             Next Y
  121.             
  122.             基準陣列(Y + 1) = 暫存
  123.         Next X
  124.         
  125.         基準 = 基準陣列(2)
  126.         
  127.         '------------------------------------------------------
  128.         
  129.         Dim 起陣列 As Variant
  130.         Dim 基陣列 As Variant
  131.         Dim 迄陣列 As Variant
  132.         Dim 索引起陣列() As Long
  133.         Dim 索引基陣列() As Long
  134.         Dim 索引迄陣列() As Long
  135.         
  136.         ReDim 起陣列(迄限 - 起限) As Variant
  137.         ReDim 基陣列(迄限 - 起限 + 1) As Variant
  138.         ReDim 迄陣列(迄限 - 起限) As Variant
  139.         ReDim 索引起陣列(迄限 - 起限) As Long
  140.         ReDim 索引基陣列(迄限 - 起限 + 1) As Long
  141.         ReDim 索引迄陣列(迄限 - 起限) As Long
  142.         
  143.         S = 0
  144.         M = 0
  145.         E = 0
  146.         For X = 起限 To 迄限
  147.             暫存 = 原始一維陣列(X)
  148.             索引暫存 = 索引陣列(X)
  149.             
  150.             If 暫存 < 基準 Then
  151.                 S = S + 1
  152.                 起陣列(S) = 暫存
  153.                 索引起陣列(S) = 索引暫存
  154.             ElseIf 暫存 = 基準 Then
  155.                 M = M + 1
  156.                 基陣列(M) = 暫存
  157.                 索引基陣列(M) = 索引暫存
  158.             Else
  159.                 E = E + 1
  160.                 迄陣列(E) = 暫存
  161.                 索引迄陣列(E) = 索引暫存
  162.             End If
  163.         Next X
  164.         
  165.         '------------------------------------------------------
  166.         
  167.         If S > 1 Then
  168.             二維陣列快速插入穩定遞增排序 起陣列, 索引起陣列, 1, S
  169.         End If
  170.         
  171.         If E > 1 Then
  172.             二維陣列快速插入穩定遞增排序 迄陣列, 索引迄陣列, 1, E
  173.         End If
  174.         
  175.         '------------------------------------------------------
  176.         
  177.         N = 起限 - 1
  178.         For X = 1 To S
  179.             N = N + 1
  180.             原始一維陣列(N) = 起陣列(X)
  181.             索引陣列(N) = 索引起陣列(X)
  182.         Next X
  183.         
  184.         For X = 1 To M
  185.             N = N + 1
  186.             原始一維陣列(N) = 基陣列(X)
  187.             索引陣列(N) = 索引基陣列(X)
  188.         Next X
  189.         
  190.         For X = 1 To E
  191.             N = N + 1
  192.             原始一維陣列(N) = 迄陣列(X)
  193.             索引陣列(N) = 索引迄陣列(X)
  194.         Next X
  195.     End If

  197. End Sub
複製代碼




歡迎光臨 麻辣家族討論版版 (http://forum.twbts.com/)