1 Attachment(s)
Re: VB6 Dual-Pivot-QuickSort
Quote:
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):
Attachment 150001
@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):
http://vbRichClient.com/Downloads/DualPivotIndirect.png
HTH
Olaf
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.
Re: VB6 Dual-Pivot-QuickSort
Quote:
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):
http://vbRichClient.com/Downloads/Du...tIndirect2.png
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
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
Re: VB6 Dual-Pivot-QuickSort
Quote:
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.
Quote:
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.
Quote:
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...
Quote:
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
Re: VB6 Dual-Pivot-QuickSort
Olaf thank you for your help & guidance.
STeve.
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.
