Re: [fpc-devel] Sorting tests
Indeed. I'm just trying to think if there's a way that that can be implemented in a cross-platform way, or if there's a wa to identify if a generic type is a pointer/managed type. Kit On 25/11/2022 16:00, Stefan Glienke via fpc-devel wrote: >From experience I can tell that IntroSort is fast enough. The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting. On 24/11/2022 19:51 CET J. Gareth Moreton via fpc-devel wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Also, since Olly mentioned that the unit is used in TStringList, it makes me wonder if the RTL has a radix sort algorithm available, since radix sort is on the order of O(n) and is ideal for sorting large arrays of strings (although it can be memory-intensive). Kit ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
From experience I can tell that IntroSort is fast enough. The main performance improvement usually comes from treating anything that is a managed type such as strings as Pointers - instead of three string assignments that cause a bunch of unnecessary atomic operations you then just have 3 pointer assignments. And with anything inside of IntroSort there are just swaps that can go without any reference counting. > On 24/11/2022 19:51 CET J. Gareth Moreton via fpc-devel > wrote: > > > Hi everyone, > > I just need to touch on the knowledge base. What tests exist that test > the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm > looking at creating Introsort for this unit as well, but I need to know > if such a unit already exists or if I need to make my own. > > Also, since Olly mentioned that the unit is used in TStringList, it > makes me wonder if the RTL has a radix sort algorithm available, since > radix sort is on the order of O(n) and is ideal for sorting large arrays > of strings (although it can be memory-intensive). > > Kit > > ___ > fpc-devel maillist - fpc-devel@lists.freepascal.org > https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
These are nice but don't actually use the code in rtl/inc/sortbase.pp - maybe they can be adapted though. Kit On 25/11/2022 10:10, Marco Borsari via fpc-devel wrote: On Thu, 24 Nov 2022 18:51:12 + "J. Gareth Moreton via fpc-devel" wrote: Hi everyone, I just need to touch on the knowledge base. What tests exist that test the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm looking at creating Introsort for this unit as well, but I need to know if such a unit already exists or if I need to make my own. Some times ago I wrote a couple of merge sort routines to use in BWT, the project never goes further so they remain at level of numerical values input only. They should have a good worst case scenario. In the merge.pas the parameter nrm has to be false when the dimension of the array is not a power of two. There also is a check head-tail of the blocks to move in a single pass the smaller one. The natural.pas is recursive in the initial division in blocks and allow for adaptation for inputs already sorted. If you find them useful, you are free to made anything you want. Marco ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel ___ fpc-devel maillist - fpc-devel@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Re: [fpc-devel] Sorting tests
On Thu, 24 Nov 2022 18:51:12 +
"J. Gareth Moreton via fpc-devel" wrote:
> Hi everyone,
>
> I just need to touch on the knowledge base. What tests exist that test
> the functionality of rtl/inc/sortbase.pp? As Olly suggested, I'm
> looking at creating Introsort for this unit as well, but I need to know
> if such a unit already exists or if I need to make my own.
Some times ago I wrote a couple of merge sort routines to use in BWT,
the project never goes further so they remain at level of numerical
values input only.
They should have a good worst case scenario.
In the merge.pas the parameter nrm has to be false when the dimension
of the array is not a power of two.
There also is a check head-tail of the blocks to move in a single pass
the smaller one.
The natural.pas is recursive in the initial division in blocks and allow
for adaptation for inputs already sorted.
If you find them useful, you are free to made anything you want.
Marco
--
Simplex sigillum veri
PROGRAM Sort;
CONST
len=20;
VAR
a:ARRAY[0..2*len-1] OF Byte;
i,j:Word;
src:Boolean;
PROCEDURE MergeSort(VAR src:Boolean;nrm:Boolean);
VAR
dbl,sub,i,j,k,l,m,n,dst,lim:Word;
x,y,z:Integer;
BEGIN
dbl:=len SHL 1;
sub:=1;
WHILE subdbl THEN
l:=dbl;
IF m>dbl THEN
m:=dbl;
IF lim>len THEN
lim:=len;
END
ELSE
BEGIN
IF l>len THEN
l:=len;
IF m>len THEN
m:=len;
IF lim>dbl THEN
lim:=dbl;
END;
x:=l-i;
y:=m-j;
z:=m-i;
END;
IF a[l-1]<=a[j] THEN
BEGIN
IF z>0 THEN
Move(a[i],a[dst],z);
i:=l;
j:=m;
dst:=lim;
END
(* Solo < per avere un metodo stabile *)
ELSE IF a[m-1]0 THEN
Move(a[j],a[dst],y)
ELSE
y:=0;
IF x>0 THEN
Move(a[i],a[dst+y],x);
i:=l;
j:=m;
dst:=lim;
END;
WHILE dst=m) OR ((iPROGRAM Sort;
CONST
len=20;
VAR
a,b:ARRAY[0..len-1] OF Byte;
h,t,idx:Word;
PROCEDURE NaturalSort(i,j,k:Word;run:Byte);
VAR
l,m:Word;
BEGIN
l:=i;
m:=j;
IF run<>2 THEN
BEGIN
t:=a[i];
Inc(i);
h:=a[i];
WHILE (i<=m) AND (h>=t) DO
BEGIN
t:=h;
Inc(i);
h:=a[i];
END;
Dec(i);
END
ELSE
i:=k;
IF i1 THEN
BEGIN
h:=a[j];
Dec(j);
t:=a[j];
WHILE (j>=l) AND (h>=t) DO
BEGIN
h:=t;
Dec(j);
t:=a[j];
END;
Inc(j);
END
ELSE
j:=k;
IF i-l>=m-j THEN
BEGIN
k:=i+1;
NaturalSort(k,m,j,1);
j:=k;
END
ELSE
BEGIN
k:=j-1;
NaturalSort(l,k,i,2);
i:=k;
END;
END
ELSE
k:=len;
IF ki) OR (a[l]<=a[j]) THEN
Inc(l)
ELSE
BEGIN
b[h]:=a[l];
Inc(h);
a[l]:=a[j];
Inc(l);
Inc(j);
END
ELSE
BEGIN
IF l<=i THEN
BEGIN
b[h]:=a[l];
Inc(h);
END;
IF (j>m) OR (b[t]<=a[j]) THEN
BEGIN
a[l]:=b[t];
Inc(l);
Inc(t);
END
ELSE
BEGIN
a[l]:=a[j];
Inc(l);
Inc(j);
END;
END;
END;
END;
BEGIN
Randomize;
FOR idx:=0 TO len-1 DO
BEGIN
a[idx]:=Random(256);
Write(' ',a[idx]);
END;
WriteLn;
NaturalSort(0,len-1,len,0);
FOR idx:=0 TO len-1 DO
Write(' ',a[idx]);
END.
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
