-
Jul 26th, 2017, 04:29 PM
#41
Re: VB6 Dual-Pivot-QuickSort
Originally Posted by Steve Grant
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.
-
Jul 27th, 2017, 02:36 AM
#42
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.
-
Jul 27th, 2017, 05:29 AM
#43
Re: VB6 Dual-Pivot-QuickSort
Originally Posted by Steve Grant
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
-
Jul 28th, 2017, 03:44 AM
#44
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
-
Jul 28th, 2017, 02:53 PM
#45
Re: VB6 Dual-Pivot-QuickSort
Originally Posted by Steve Grant
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.
Originally Posted by Steve Grant
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.
Originally Posted by Steve Grant
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...
Originally Posted by Steve Grant
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
-
Jul 28th, 2017, 04:38 PM
#46
Re: VB6 Dual-Pivot-QuickSort
Olaf thank you for your help & guidance.
STeve.
-
Sep 2nd, 2020, 11:29 PM
#47
New Member
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|