Fast Sorting algo help

[qWord]

That was also my idea, but Michael (#6) says no ::)

You need a stable algorithm if you sort something that has already been sorted.

What do you think of Jim Dempsey's idea to make qsort stable?

I can't see how that should work - an element might be swapped several times and each time the address change.

[guga]

I`m trying to use qsort, but it is crashing, because the internal pointers of the comparefunction are not being correctly achieved.

Code: [Select]

; equates usedof the structure DFMScript
[DFMScript.pLabelNameDis 0
 DFMScript.pSigLabelDis 4
 DFMScript.pExtentionDis 8
 DFMScript.pSignatureDataLenDis 12
 DFMScript.pSignatureDataDis 16
 DFMScript.pSigSizeDis 20]

[Size_of_DFMScript 24]
[ScriptData2: D$ 0] ; <----- This is a pointer to the actual file data. It is zero only before precomputing the scrypt...but, below, the pointer is already retrieved.

    c_call 'msvcrt.qsort' D$ScriptData2, 9, Size_of_DFMScript, CompareFunc


Code: [Select]


Proc CompareFunc:
    Arguments @Arg1, @Arg2
    Uses esi, edi, edx, esi

    mov ecx D@Arg1
    mov edx D@Arg2

    mov esi ecx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | move edi D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, edi, DecodedData1
    mov esi edx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov ecx D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, ecx, DecodedData2
    If ecx > edi;D@DataLen2
        mov ecx edi;D@DataLen2
    End_If

    c_call 'msvcrt._mbsnbcmp' DecodedData1, DecodedData2, ecx

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
   neg     eax

L0:

EndSTD


Code: [Select]


Proc BinaryDecode:
    Arguments @Input, @InputSize, @Output
    Uses esi, edi, ecx, ebx, edx

    ; EncodeSignature
    mov esi D@Input
    mov edi D@Output
    mov ebx D@InputSize

    ;..While B$esi <> 0
    ..While ebx <> 0

        .If B$esi = SIG_TYPE_BYTE
            inc esi
            movsb
            dec ebx
        .Else_If B$esi = SIG_TYPE_WORD
            inc esi
            movsw
            sub ebx 2
        .Else_If B$esi = SIG_TYPE_DWORD
            inc esi
            movsd
            sub ebx 4
        .Else_If B$esi = SIG_TYPE_REPEAT_BYTES
            ;mov eax eax
            inc esi
            movzx ecx B$esi | inc esi | mov edx ecx
            movzx eax B$esi | inc esi
            rep stosb
            sub ebx edx

        .Else_If B$esi = SIG_TYPE_BYPASS_BYTES
            inc esi
            movzx ecx B$esi | inc esi | mov edx ecx
            mov al 0FF
            rep stosb
            sub ebx edx
        .Else
            ; error when decoding
            mov eax eax
        .End_If

    ..End_While

EndP

I have no idea why it is crashing.
The structure is 24 bytes long, and the file contains 9 structures. So it should suppose to work, but....it isn´t :(


I have no idea what is happenning. The debugger shows me that on the 1st loop of the call back CompareFunc, Arg1 and Arg2 points inside the strcture array....but, on the 2nd loop Arg1 points outside the structure array :(:(:(


Btw: ENDSTD macro is a simple ret instruction. It is to simulate a stdcall function return

[KeepingRealBusy]

That was also my idea, but Michael (#6) says no ::)

You need a stable algorithm if you sort something that has already been sorted.

What do you think of Jim Dempsey's idea to make qsort stable?

I can't see how that should work - an element might be swapped several times and each time the address change.

That is why you need an indirect Qsort - where there are pointers to each of the structures, the structures remain static in memory (same address always), and the indirect pointers are swapped.

Dave.

[qWord]

That is why you need an indirect Qsort - where there are pointers to each of the structures, the structures remain static in memory (same address always), and the indirect pointers are swapped.

yes. (but this wouldn't be in-place of course)

However, guga doesn't need a stable sorting algorithm at all, because it can be done in one pass (AFAICS).

[guga]

OK, i guess i fixed it. It was crashing due to a mistake on the push/pop register ("Uses macro)). Vortex´s example that JJ gave works like a gem  :t

Now it sorts properly on descending order.

Code: [Select]

[Trilobyte's JPEG graphics Library:||jpg|84 10 FF FF FF FF 1E 00 01 10 08 00 00 00 00 00
[Trilobyte's JPEG graphics Library:||jpg|84 10 F1 F2 F3 F4 1E 00 01 10 08 09 07 06 05 04
[Wavelet compressed bitmap:||wvl|057 049
[Bitmap(PBM):||pbm|050 036 0A
[Delphi ImageList:||iml|049 04C
[TImageList:|TImageList|iml|049 04C
[TBitmap:|TBitmap|bmp|042 04D ???? ?? ?? ???? 028
[Cursor:||cur|00 00 00 02 00
[Icon:||ico|00 00 00 01 00

The corrected code is as folows:

Code: [Select]

Proc CompareFunc:
    Arguments @Arg1, @Arg2
    Uses esi, edi, edx, ecx, ebx

    mov ecx D@Arg1
    mov edx D@Arg2

    mov esi ecx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov edi D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, edi, DecodedData1
    mov esi edx | mov ebx D$esi+DFMScript.pSignatureDataDis | add ebx D$ScriptData2 | mov ecx D$esi+DFMScript.pSigSizeDis
    call BinaryDecode ebx, ecx, DecodedData2
    If ecx > edi;D@DataLen2
        mov ecx edi;D@DataLen2
    End_If

    c_call 'msvcrt._mbsnbcmp' DecodedData1, DecodedData2, ecx

; To sort an array in decreasing order, reverse the sense of
; greater than and less than in the comparison function :
;
   neg     eax

L0:
EndSTD

Code: [Select]

c_call 'msvcrt.qsort' D$ScriptData2, 9, Size_of_DFMScript, CompareFunc

Since it seems to be working, then the qsort algorithm seems to be the proper choice.

The question now is....How fast is crt qsort ? Does we have an algo that have the exact same functionality but, faster ?

Also.....what about strncmp does we have an faster algo with the same functionality ?


The better would be have faster algos for qsort and strncmp since, i´ll deal with a large database

[guga]

JJ, does your Algo works for the structure i´m making ?

[jj2007]

The better would be have faster algos for qsort and strncmp since, i´ll deal with a large database

Your BinaryDecode needs to be fast. Maybe inlined instead of called.

QuickSort can be beaten only in rare circumstances. ArraySort is faster but not applicable here, as it does not use a callback.

JJ, does your Algo works for the structure i´m making ?

QSort() could be used only if you translated your strucs into strings, i.e. criteria 1+2 would be expressed as something sortable, the other members added behind. E.g. if crit 1=123, 99 and crit 2=777, 444:
00000123#777#other members#
00000099#444#more data....#

Feasible and probably fast but would require quite a bit of RAM.

[Gunther]

QuickSort can be beaten only in rare circumstances.

Yes, QuickSort is mostly the way to go. I think that's true in Gustavo's special case, too.

Gunther

[jj2007]

QuickSort can be beaten only in rare circumstances.

Yes, QuickSort is mostly the way to go. I think that's true in Gustavo's special case, too.

Why that, in this "special case"?

[Gunther]

Jochen,

Why that, in this "special case"?

I had better written: in his case (nothing is special). No offense.

Gunther

[FORTRANS]

Not sure if I interpret that correct, but I guess you can just use qsort whereby comparing the secondary keys only if the primary keys are equal.

That was also my idea, but Michael (#6) says no ::)

What do you think of Jim Dempsey's idea to make qsort stable?

Hi,

   Basically there are two (simple) ways to do a sort on two (or
more) keys.

   What Jim, qWord, and you are doing, is sort on the primary key,
and if two entries are equal, sort on the secondary key.  This will
work until you have more than one equal key value.  Then things
can rapidly go down the tubes if not well thought out.  (Yes, it
does work, but it can be more complicated because you are doing
two sets of comparisons at once, rather than one at a time.)

   What Michael is saying, I think, is that the standard way to do it
is to use a stable sort, sort on the secondary key, and then sort
on the primary key.  At least that is what I remember from most
discussions.  It can be simpler to do it that way, at least in theory.
Particularly when sorting on many keys.  You just sort the data
from least significant key to most significant key, one at a time.

YMMV,

Steve N.

[jj2007]

What Jim, qWord, and you are doing, is sort on the primary key, and if two entries are equal, sort on the secondary key.

Steve,

I have a suspicion that there is a misunderstanding:

- option 1 is to do TWO sorts, first on crit 1, then on crit 2; this is what I use e.g. in the Excel-stylespreadsheet viewer, and it requires a stable sort.

- option 2 is to do ONE sort, where both criteria are checked in the comparison function; this is what (I assume) qWord and myself suggested in Gustavo's case.

The latter should work fine with an unstable sort.

[guga]

Ok, the crt qsort works fine, but it is slow.

I´m analyzing the msvcrt function, and found out that it is, in fact, a arraysort as described here:

http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html

The source code of qsort accordying to the windows sources i have is extremely old. Last revision is from 11/19/1991 by GJF - Do the swap one character at a time to avoid alignment woes.

It seems similar to one in posix and gnu lib
https://github.com/luciang/haiku/blob/master/src/system/libroot/posix/stdlib/qsort.c

But..i´m starting to get confused here. In my case, i presume the qsort algorithm does not need to be stable, since, i´m basicaly sorting the array biased in 1 of it´s elements, right ?

just to try to understand...is the lik below that is trying to make qsort stable really worthfull in terms of speed (for my case)?
http://nullprogram.com/blog/2014/08/29/


JJ.

- option 2 is to do ONE sort, where both criteria are checked in the comparison function; this is what (I assume) qWord and myself suggested in Gustavo's case.

The changes i made in the code are correct ?

[FORTRANS]

Steve,

I have a suspicion that there is a misunderstanding:

Hi,

   Not really.  As per usual, I was perhaps unclear.  What I was
trying to say is what you then said.  Use a stable sort with
multiple passes.  Or compare everything, either all at once, or
test the first key and then test the second if the first tests equal.
With any sort.  Sorry about that.  The "textbook" way is to use
multiple passes in my experience.

Regards,

Steve

[guga]

One of the things that makes qsort a bit slow is a byte by byte scan on a routine i isolated and named as:

Code: [Select]

Proc Swap:
    Arguments @Struct1, @Struct2, @Width, @compare
    Local @Distance
    Uses ebx, ecx, edx

    mov ebx D@Struct1 | sub ebx D@Struct2 | jz L1> | mov D@Distance ebx ;< distance may not be necessary, as long the user preserved ebx in his comparefunction
    call D@compare D@Struct1, D@Struct2
    .If eax >s 0
        mov ebx D@Distance
        mov eax D@Struct2
        mov ecx D@width ; <--- size of the structure (3rd parameter of qsort function)
        L1:
            mov dh B$eax+ebx
            mov dl B$eax | mov B$eax+ebx dl
            mov B$eax dh
            inc eax
        dec ecx | jne L1<
    .End_If
L1:

EndP



If someone can help building a variation of this function that makes it a bit faster, i´ll appreciate it. Then, once it is done, i´ll reinsert it on the main function to try to optimize the crt qsort a bit more. (Decoding it is a pan, but it is possible to do)