Page 2 of 2 FirstFirst 12
Results 41 to 47 of 47

Thread: VB6 Dual-Pivot-QuickSort

  1. #41

    Thread Starter
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: VB6 Dual-Pivot-QuickSort

    Quote Originally Posted by Steve Grant View Post
    Olaf you once showed me how to use StrCmpLogicalW(StrPtr(S1),StrPtr(S2)) with a standard QuickSort.

    I would now like to use the DualPivot-Quicksort and have tried replacing all the comparisons (If M1<M2) etc with the StrCmpLogicalW equivalent but it is VERY slow. Can you show how you would do it please.
    Ok, here's a Variant which is using a CallBack-ClassInstance that implements an IStringCompare-Interface
    (so that you can decide on the outside about the String-Comparisons/Collations, by simply passing an appropriately implemented ClassInstance along):
    DualPivotQuickSortString.zip

    @loquat
    Here's the Result compared to the QSort2 you've posted, when both Algos are using the faster of the currently two ClassCallBack-instances
    (cCompareBinary - for case-sensitive String-Comparisons - the other one, not used in the Test, is cCompareNoCase):


    HTH

    Olaf
    Last edited by Schmidt; Jul 26th, 2017 at 04:47 PM.

  2. #42
    Fanatic Member
    Join Date
    Jul 2007
    Location
    Essex, UK.
    Posts
    578

    Re: VB6 Dual-Pivot-QuickSort

    Hi Olaf, many thanks for your efforts. I believe I have got it working ok.

    Just as a test I put the Quicksort you gave me into the mix but it fails the verify test in the IDE. Could you possibly take a look - Thank you.

    Steve.

  3. #43

    Thread Starter
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: VB6 Dual-Pivot-QuickSort

    Quote Originally Posted by Steve Grant View Post
    Hi Olaf, many thanks for your efforts. I believe I have got it working ok.

    Just as a test I put the Quicksort you gave me into the mix but it fails the verify test in the IDE...
    That's because you treat it (in the Verification-Line) as an indirect sorting Algo: .... Arr(Ind(i))

    If you change that to a normal Arr(i), then the verification should succeed.

    Here's the timings on my machine (all algos using the quite CPU-intensive StrCompLogicalW):


    The normal QuickSort is not bad in this comparison, because it is avoiding the additional
    ComparerClass-MethodCall (jumping directly to StrCompLogicalW).

    The DualPivot still the fastest though, despite having to do the Compares over that ClassMethod-Indirection
    (which allows greater flexibility, in case one wants to switch the Sorting-behaviour in the future).

    Olaf

  4. #44
    Fanatic Member
    Join Date
    Jul 2007
    Location
    Essex, UK.
    Posts
    578

    Re: VB6 Dual-Pivot-QuickSort

    Many thanks for your advice, you were right Arr(i) sorted out the verification.

    I removed the classes and made calls to StrCompLogicalW directly which significantly improved the times of DualPivot.

    However I have run into a problem which has at least made me understand more fully what Indirect means in this context. I have managed to screw up my database (not a real database) files. As these need to be sorted directly.

    It's not a problem as I had backed up, more of a disappointment, as I realise that the speed comes from sorting the longs rather than the strings themselves. I just want to sort string arrays directly as fast as possible using StrCompLogicalW. This may surprise you: When my programme ends, I have a mostly sorted array (99%) that just has to be finally sorted. The fastest sort I have found for this is a Gnome sort which takes 16mS for 50000 entries. Compared to 215mS if I use the quicksort posted above. Yet if I read in all the filenames in my music folder Quicksort sorts them in 187mS whereas GnomeSort chokes completely.

    In case anyone is interested here is the GnomeSort.

    Code:
    Public Sub GnomeSort(ByRef pvarArray() As String)
        'By Ellis Dee
        'StrCmpLogicalW(StrPtr(S1),StrPtr(S2))
        'Returns 0 if S1=S2. 1 if S1>S2. -1 if S1<S2.
        Dim i As Long
        Dim j As Long
        Dim iMin As Long
        Dim iMax As Long
        Dim varSwap As String
        
        iMin = LBound(pvarArray) + 1
        iMax = UBound(pvarArray)
        
        i = iMin
        j = i + 1
        Do While i <= iMax
            If StrCmpLogicalW(StrPtr(pvarArray(i)), StrPtr(pvarArray(i - 1))) = -1 Then
                varSwap = pvarArray(i)
                pvarArray(i) = pvarArray(i - 1)
                pvarArray(i - 1) = varSwap
                If i > iMin Then i = i - 1
            Else
                i = j
                j = j + 1
            End If
        Loop
    End Sub

  5. #45

    Thread Starter
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: VB6 Dual-Pivot-QuickSort

    Quote Originally Posted by Steve Grant View Post
    Many thanks for your advice, you were right Arr(i) sorted out the verification.

    I removed the classes and made calls to StrCompLogicalW directly which significantly improved the times of DualPivot.
    Yep, if you do not need the flexibility - needing more speed instead - direct compare-calls can shape off a bit of overhead.

    Quote Originally Posted by Steve Grant View Post
    However I have run into a problem which has at least made me understand more fully what Indirect means in this context. I have managed to screw up my database (not a real database) files. As these need to be sorted directly.
    Hmm, in that case I'd suggest a real DBEngine (which normally doesn't "screw up" its table-contents that easily)...
    SQLite can insert about 300000-500000 records per second, so it would be a nice target to feed from e.g. FileSystem-Scans.

    Quote Originally Posted by Steve Grant View Post
    I have a mostly sorted array (99%) that just has to be finally sorted. The fastest sort I have found for this is a Gnome sort which takes 16mS for 50000 entries. Compared to 215mS if I use the quicksort posted above.
    Well, in such cases "horses for courses" I guess...

    Quote Originally Posted by Steve Grant View Post
    Yet if I read in all the filenames in my music folder Quicksort sorts them in 187mS whereas GnomeSort chokes completely.
    In case you need to scan a Directory, expecting "logically sorted" results always, the RC5 cDirList-Class has that already built in.
    (you can treat it like a Collection, which you can pass around and access later).
    Code:
    Dim DL As cDirList, i As Long
    Set DL = New_c.FSO.GetDirList(Path, dlSortByNameLogically, "*.mp3;*.wma;*.whatever")
    For i = 0 To DL.FilesCount - 1 'enumeration of the sorted contents
        Debug.Print DL.FileName(i), DL.FileSize(i), DL.FileLastAccessTime(i)
    Next
    HTH

    Olaf

  6. #46
    Fanatic Member
    Join Date
    Jul 2007
    Location
    Essex, UK.
    Posts
    578

    Re: VB6 Dual-Pivot-QuickSort

    Olaf thank you for your help & guidance.

    STeve.

  7. #47
    New Member
    Join Date
    Aug 2015
    Posts
    7

    Re: VB6 Dual-Pivot-QuickSort

    Olaf,

    I noticed this line in your fantastic DualPivotQuicksort:

    Code:
    If (M2 - M1) > (UB - LB - 21) Then  'handle equal elements
    Can you please shine some light on the value of 21 here? What does 21 do? How was 21 chosen?

    I noticed that in Yaroslavskiy's paper he uses the value of 13 instead. But what is the purpose of 21 or 13?

    Thank you.
    Last edited by xyrph; Sep 3rd, 2020 at 12:32 PM.

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width