/ Forside / Teknologi / Udvikling / Delphi/Pascal / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Delphi/Pascal
#NavnPoint
oldwiking 603
jrossing 525
rpje 520
EXTERMINA.. 500
gandalf 460
gubi 270
DJ_Puden 250
PARKENSS 230
technet 210
10  jdjespers.. 200
Grums i sorting, quicksort sucks?
Fra : Thomas Eg Jørgensen


Dato : 20-03-07 17:18

Hej,

Jeg har to "hovedklasser" som alle mine underklasser arver fra. Den ene
er en dataklasse(arver fra TPersistent), det kunne eksempel være en
vare, en kunde osv. Den anden hovedklasse er en listeklasse(arver fra
TObjectList), denne indeholder så en liste af dataklasser, f.eks. en
varelist, en kundeliste osv.

Da jeg bruger RaveReports til rapportgenerering vil jeg gerne kunne
angive, fra Rave-rapporten, hvilken property i data-klassen som en given
liste skal kunne sorteres efter. Da jeg gerne vil undgå at lave sorting
for alle klasser og alle properties har jeg forsøgt at benytte mig af
RTTI.

Jeg har lavet en metode i min listeklasse(TNPParentList.PrinterSetSort),
denne metode kaldes fra Rave Reports når brugeren har sat en
SortKey-property på et databand som henter data fra listen. Dette
fungere fint, men idag spurgte en test-brugere så om: "Jeg vil gerne
sortere efter FeltA _OG_ FeltB...i den rækkefølge...hvordan gør jeg
det?"....øh...jeg forsøgte så at omskrive sortingsfunktionen til at
understøtte dette, men det vil bare ikke som jeg vil. Nu har jeg så
efterhånden stiret mig blind på det og mistænker nu Quicksort for ikke
at kunne bruges til det jeg forsøger. Er der nogen der kan gennemskue om
det er korrekt eller set hvor jeg har lavet fejlen?

Først en kildekoden:

**********
//Method to enable users to sort lists from a Rave-report
procedure TNPParentList.PrinterSetSort(Connection: TRvCustomConnection);
//Compare-method for the Sort-function
function SortCompare(Item1, Item2: Pointer): Integer;
var
Count, Loop: Integer;
List: PPropList;
objProp: TObject;
SortLoop: integer;
begin
//Make sure we are reset
SortLoop:=0;
Result:=0;

//Allocate space for properties of the data-class
//Note: item1 and item2 will always be of the same class, so just
use item1!
Count := GetPropList(TNPParent(item1).ClassInfo, tkProperties, nil)
;
GetMem(List, Count * SizeOf(PPropInfo)) ;
GetPropList(TNPParent(item1).ClassInfo, tkProperties, List);

try
//Loop as long as we does not have a difference in the sorting
fields (...or aslong as we have fields to sort by!)
while (result=0) and (SortLoop<TNPParent(Item1).SortingList.Count)
do
begin

//Loop through the property-list of the data-class...
for Loop := 0 to Pred(Count) do
begin

//Is this the right property to sort by?
If TNPParent(Item1).SortingList[SortLoop] = List[loop]^.Name
then
begin

//Make sure we sort the right way...only Integers, Strings
and Floats at the moment!
case List[Loop]^.PropType^.Kind of
tkInteger:
Result:=CompareValue(GetOrdProp(TNPParent(Item1),List[loop]^.Name),GetOrdProp(TNPParent(Item2),List[loop]^.Name));
tkString,
tkLString,
tkWString:
Result:=CompareText(GetStrProp(TNPParent(Item1),List[loop]^.Name),GetStrProp(TNPParent(Item2),List[loop]^.Name));
tkFloat:
Result:=CompareValue(GetFloatProp(TNPParent(Item1),List[loop]^.Name),GetFloatProp(TNPParent(Item2),List[loop]^.Name));
else raise exception.create(Format(_('Cannot sort on field
"%s", the format of the field is not supported! Please redefine
sortfield!'),[TNPParent(Item1).SortingList[SortLoop]]));
end;

//No need to search any further! We found the right
property!
break;
end;

//showmessage(List[loop]^.Name+chr(13)+inttostr(loop)+chr(13)+inttostr(Pred(Count)));
//Did we not find the property? If we are sorting on a
sub-class we wont find it! e.g. "dataclass.dataclass.property"
if loop=Pred(Count) then
begin
raise exception.create(Format(_('Cannot sort on field "%s",
maybe a sub-field? Please redefine
sortfield!'),[TNPParent(Item1).SortingList[SortLoop]]));
end;
end;

//Goto the next sort-field...
Inc(SortLoop);
end;
finally
FreeMem(List, Count * SizeOf(PPropInfo))
end;
end;
var
a: integer;
TheSortList: TStrings;
SortByFieldName: string;
begin
//Get the name of the field which the list should be sorted...
SortByFieldName:=Connection.ReadStr;

//Create a list of strings(Since the "SortByFieldName" can be of the
format "Field1 & Field2 & Field3..."
TheSortList:=TStringlist.create;
try

//Loop through the string and find each field-name
while pos('&',SortByFieldName)> 0 do
begin
TheSortList.Add(Trim(copy(SortByFieldName,1,pos('&',SortByFieldName)-2)));
System.Delete(SortByFieldName,1,pos('&',SortByFieldName));
end;

//...remember to add the last field in the list(...and potential the
only one!)
TheSortList.Add(Trim(SortByFieldName));

//Assign all the searchfields to each item (to be used in the
SortCompare-method)
for a:=0 to Self.Count-1 do
begin
Items[a].SortingList.Text:=TheSortList.Text;
end;
finally
TheSortList.free;
end;

//Use the TList.Sort function to sort the list...
Sort(@SortCompare);
end;

**********

Så problemet:
Say jeg søger på FeltA(en streng-type) og FeltB(en float-type), f.eks.:

1: "A" og 5,5
2: "B" og 1,0
3: "A" og 4,5

Så ville jeg forvente at den sorterede listen som 3-1-2:
3: "A" og 4,5
1: "A" og 5,5
2: "B" og 1,0

MEN dette er ikke tilfælde, den sortere ikke efter felter ud over den
første:
1: "A" og 5,5
3: "A" og 4,5
2: "B" og 1,0

....min tanke er så: Jeg har mistænkt min do-while løkke for at være
årsagen til problemet: altså det med at jeg kun kigger på de
efterfølgende felter hvis det aktuelle felt er ens for item1 og item2.
Men jeg kan ikke rigtigt gennemskue hvorfor det IKKE skulle virke. Jeg
håbede derfor at der var nogle "søgehajer" herinde som kunne sige: "hør
lige her unge mand, linje 7 er der helt i skoven!"...eller noget i den
stil

PS: Jeg har brugt samme princip til at fortælle Rave hvilke felter der
findes i data-klasserne og til at hente data ind i Rave fra
listerne...Jeg synes selv det er suuuuper smart, men jeg kunne godt
tænke mig at høre hvordan andre gør? Om jeg bare har opfundet den dybe
tallerken igen....igen....?

MVH
Thomas


 
 
Uffe Kousgaard (20-03-2007)
Kommentar
Fra : Uffe Kousgaard


Dato : 20-03-07 18:41

"Thomas Eg Jørgensen" <thomas@hest.notaplan.com> wrote in message
news:46000924$0$90266$14726298@news.sunsite.dk...

Noget må jo gå galt her. Med debugging skulle det vel være til at finde ud
af?

hilsen
Uffe

> //Compare-method for the Sort-function
> function SortCompare(Item1, Item2: Pointer): Integer;
> var
> Count, Loop: Integer;
> List: PPropList;
> objProp: TObject;
> SortLoop: integer;
> begin
> //Make sure we are reset
> SortLoop:=0;
> Result:=0;
>
> //Allocate space for properties of the data-class
> //Note: item1 and item2 will always be of the same class, so just use
> item1!
> Count := GetPropList(TNPParent(item1).ClassInfo, tkProperties, nil) ;
> GetMem(List, Count * SizeOf(PPropInfo)) ;
> GetPropList(TNPParent(item1).ClassInfo, tkProperties, List);
>
> try
> //Loop as long as we does not have a difference in the sorting fields
> (...or aslong as we have fields to sort by!)
> while (result=0) and (SortLoop<TNPParent(Item1).SortingList.Count) do
> begin
>
> //Loop through the property-list of the data-class...
> for Loop := 0 to Pred(Count) do
> begin
>
> //Is this the right property to sort by?
> If TNPParent(Item1).SortingList[SortLoop] = List[loop]^.Name then
> begin
>
> //Make sure we sort the right way...only Integers, Strings and
> Floats at the moment!
> case List[Loop]^.PropType^.Kind of
> tkInteger:
> Result:=CompareValue(GetOrdProp(TNPParent(Item1),List[loop]^.Name),GetOrdProp(TNPParent(Item2),List[loop]^.Name));
> tkString,
> tkLString,
> tkWString:
> Result:=CompareText(GetStrProp(TNPParent(Item1),List[loop]^.Name),GetStrProp(TNPParent(Item2),List[loop]^.Name));
> tkFloat:
> Result:=CompareValue(GetFloatProp(TNPParent(Item1),List[loop]^.Name),GetFloatProp(TNPParent(Item2),List[loop]^.Name));
> else raise exception.create(Format(_('Cannot sort on field
> "%s", the format of the field is not supported! Please redefine
> sortfield!'),[TNPParent(Item1).SortingList[SortLoop]]));
> end;
>
> //No need to search any further! We found the right property!
> break;
> end;
>
>
> //showmessage(List[loop]^.Name+chr(13)+inttostr(loop)+chr(13)+inttostr(Pred(Count)));
> //Did we not find the property? If we are sorting on a sub-class
> we wont find it! e.g. "dataclass.dataclass.property"
> if loop=Pred(Count) then
> begin
> raise exception.create(Format(_('Cannot sort on field "%s",
> maybe a sub-field? Please redefine
> sortfield!'),[TNPParent(Item1).SortingList[SortLoop]]));
> end;
> end;
>
> //Goto the next sort-field...
> Inc(SortLoop);
> end;
> finally
> FreeMem(List, Count * SizeOf(PPropInfo))
> end;
> end;



Thomas Eg Jørgensen (21-03-2007)
Kommentar
Fra : Thomas Eg Jørgensen


Dato : 21-03-07 12:39


"Uffe Kousgaard" <oh@no.no> skrev i en meddelelse
news:46001ca7$0$2093$edfadb0f@dtext02.news.tele.dk...
> "Thomas Eg Jørgensen" <thomas@hest.notaplan.com> wrote in message
> news:46000924$0$90266$14726298@news.sunsite.dk...
>
> Noget må jo gå galt her. Med debugging skulle det vel være til at
> finde ud af?
>
> [SNIP - kildeteksten]

Nej, det er netop det der er problemet. Jeg har debugget den bette stump
kode i mange timer. Uanset hvad jeg "angriber" så ser alt ud som det bør
gøre. Derfor er jeg begyndt at tvivle på om min fremgangsmåde
overhovedet er mulig med en quicksort? Jeg er ikke helt inde i
"faldgrupper" i de forskellige sort-metoder, men jeg gik ud fra at
TList.Sort's quicksort var ok når det nu var den der var implementeret
fra Borlands side af...men jo flere timer jeg bruger på at steppe
igennem den stump kode, desto mere i tvivl bliver jeg....a' fatter'et
æ

Egentlig var mit spørgsmål mere af principel art, blot med den konkrete
kildekode vedhæftet Håbede på at andre havde prøvet at sortere en
TList eller lignende i forhold til flere nøgler...

Pseudoudgaven i simpel form:
Function CompareListItems(Item1,Item2):TCompareValue;
begin
//så sorter efter by...
Result:=CompareText(Item1.City , Item2.City );

//Så sorter efter gade hvis by'en er ens...
If Result=0 Then Result:=CompareText(Item1.Street, Item2.Street);

//Først sorter efter navn hvis by'en og gaden er ens...
If Result=0 Then Result:=CompareText(Item1.Name, Item2.Name);
end;

Den kaldes så med:

var
MyList: TList;
begin
MyList.Sort(@CompareListItems);

Den skulle efter mit hoved give en liste hvor alle items er sorteret
efter By, Gade og derefter navn...

Samme resultat som følgende pseudo-SQL-udtryk:
SELECT * FROM MyTable
ORDER BY City, Street, Name

Ehm...Ja...er det ikke rigtigt? Eller har jeg misforstået det
grundlæggende i den måde hvorpå sorteringen foregår?

MVH
Thomas


Uffe Kousgaard (21-03-2007)
Kommentar
Fra : Uffe Kousgaard


Dato : 21-03-07 12:58

"Thomas Eg Jørgensen" <thomas@hest.notaplan.com> wrote in message
news:46011966$0$90264$14726298@news.sunsite.dk...
>
> Ehm...Ja...er det ikke rigtigt? Eller har jeg misforstået det
> grundlæggende i den måde hvorpå sorteringen foregår?

Hvis din sammenligningsfunktion virker som specificeret, så virker quicksort
også. Din pseudokode ser umiddelbart OK ud, så du må desværre nok igang med
en gang debugging med små eksempler.

Hilsen
Uffe



Thomas Eg Jørgensen (21-03-2007)
Kommentar
Fra : Thomas Eg Jørgensen


Dato : 21-03-07 13:02

"Uffe Kousgaard" <oh@no.no> skrev i en meddelelse
news:46011dd5$0$2085$edfadb0f@dtext02.news.tele.dk...
>>
>> Ehm...Ja...er det ikke rigtigt? Eller har jeg misforstået det
>> grundlæggende i den måde hvorpå sorteringen foregår?
>
> Hvis din sammenligningsfunktion virker som specificeret, så virker
> quicksort også. Din pseudokode ser umiddelbart OK ud, så du må
> desværre nok igang med en gang debugging med små eksempler.
>

Ok, tak...

....op på hesten igen så....

MVH
Thomas


Thomas Eg Jørgensen (21-03-2007)
Kommentar
Fra : Thomas Eg Jørgensen


Dato : 21-03-07 15:30


"Uffe Kousgaard" <oh@no.no> skrev i en meddelelse
news:46011dd5$0$2085$edfadb0f@dtext02.news.tele.dk...
>>
>> Ehm...Ja...er det ikke rigtigt? Eller har jeg misforstået det
>> grundlæggende i den måde hvorpå sorteringen foregår?
>
> Hvis din sammenligningsfunktion virker som specificeret, så virker
> quicksort også. Din pseudokode ser umiddelbart OK ud, så du må
> desværre nok igang med en gang debugging med små eksempler.
>

Hmmm....Fandt fejlen, som desværre er af den type der normalt vil udløse
en form for kvajebajer. En slåfejl i en af rapporterne(som jeg brugte
til at teste med) viste sig at være problemet. Så nu fungerer
sorteringen helt som den skal.

Computerens største problem(eller fordel?): "Garbage in, garbage out"


Beklager ulejligheden

MVH
Thomas


Stig Johansen (21-03-2007)
Kommentar
Fra : Stig Johansen


Dato : 21-03-07 02:57

Thomas Eg Jørgensen wrote:

> Hej,
>
> Jeg har to "hovedklasser" som alle mine underklasser arver fra. Den ene
> er en dataklasse(arver fra TPersistent), det kunne eksempel være en
> vare, en kunde osv. Den anden hovedklasse er en listeklasse(arver fra
> TObjectList), denne indeholder så en liste af dataklasser, f.eks. en
> varelist, en kundeliste osv.
>
> Da jeg bruger RaveReports til rapportgenerering vil jeg gerne kunne
> angive, fra Rave-rapporten, hvilken property i data-klassen som en given
> liste skal kunne sorteres efter. Da jeg gerne vil undgå at lave sorting
> for alle klasser og alle properties har jeg forsøgt at benytte mig af
> RTTI.
>
> Jeg har lavet en metode i min listeklasse(TNPParentList.PrinterSetSort),
> denne metode kaldes fra Rave Reports når brugeren har sat en
> SortKey-property på et databand som henter data fra listen. Dette
> fungere fint, men idag spurgte en test-brugere så om: "Jeg vil gerne
> sortere efter FeltA _OG_ FeltB...i den rækkefølge...hvordan gør jeg
> det?"....øh...jeg forsøgte så at omskrive sortingsfunktionen til at
> understøtte dette, men det vil bare ikke som jeg vil. Nu har jeg så
> efterhånden stiret mig blind på det og mistænker nu Quicksort for ikke
> at kunne bruges til det jeg forsøger. Er der nogen der kan gennemskue om
> det er korrekt eller set hvor jeg har lavet fejlen?

Se længere nede.

>
> Først en kildekoden:
>
> **********
> //Method to enable users to sort lists from a Rave-report
> procedure TNPParentList.PrinterSetSort(Connection: TRvCustomConnection);
> //Compare-method for the Sort-function
> function SortCompare(Item1, Item2: Pointer): Integer;
> var
> Count, Loop: Integer;
> List: PPropList;
> objProp: TObject;
> SortLoop: integer;
> begin
> //Make sure we are reset
> SortLoop:=0;
> Result:=0;
>
> //Allocate space for properties of the data-class
> //Note: item1 and item2 will always be of the same class, so just
> use item1!
> Count := GetPropList(TNPParent(item1).ClassInfo, tkProperties, nil)
> ;
> GetMem(List, Count * SizeOf(PPropInfo)) ;
> GetPropList(TNPParent(item1).ClassInfo, tkProperties, List);
>
> try
> //Loop as long as we does not have a difference in the sorting
> fields (...or aslong as we have fields to sort by!)
> while (result=0) and (SortLoop<TNPParent(Item1).SortingList.Count)
> do
> begin
>
> //Loop through the property-list of the data-class...
> for Loop := 0 to Pred(Count) do
> begin
>
> //Is this the right property to sort by?
> If TNPParent(Item1).SortingList[SortLoop] = List[loop]^.Name
> then

Her finder du det første felt.

> begin
>
> //Make sure we sort the right way...only Integers, Strings
> and Floats at the moment!
> case List[Loop]^.PropType^.Kind of
> tkInteger:
>
Result:=CompareValue(GetOrdProp(TNPParent(Item1),List[loop]^.Name),GetOrdProp(TNPParent(Item2),List[loop]^.Name));
> tkString,
> tkLString,
> tkWString:
>
Result:=CompareText(GetStrProp(TNPParent(Item1),List[loop]^.Name),GetStrProp(TNPParent(Item2),List[loop]^.Name));
> tkFloat:
>
Result:=CompareValue(GetFloatProp(TNPParent(Item1),List[loop]^.Name),GetFloatProp(TNPParent(Item2),List[loop]^.Name));
> else raise exception.create(Format(_('Cannot sort on field
> "%s", the format of the field is not supported! Please redefine
> sortfield!'),[TNPParent(Item1).SortingList[SortLoop]]));
> end;
>
> //No need to search any further! We found the right
> property!
> break;

Her stopper du efter det første felt, uanset result.

--
Med venlig hilsen
Stig Johansen

Thomas Eg Jørgensen (21-03-2007)
Kommentar
Fra : Thomas Eg Jørgensen


Dato : 21-03-07 12:23

"Stig Johansen" <stig_johansen_it_at_=(@)hotmail.com> skrev i en
meddelelse news:4600917f$0$90264$14726298@news.sunsite.dk...

Jeg har klippet lidt i kildekoden da det bliver umuligt at qoute pænt
ellers...

>> while (result=0) and
>> (SortLoop<TNPParent(Item1).SortingList.Count) do
>> begin
>>
>> //Loop through the property-list of the data-class...
>> for Loop := 0 to Pred(Count) do
>> begin
>>
>> //Is this the right property to sort by?
>> If TNPParent(Item1).SortingList[SortLoop] =
>> List[loop]^.Name then
>
> Her finder du det første felt.
>
>> begin
>>
>> case List[Loop]^.PropType^.Kind of
>> tkInteger: result:=[some compare]
>> tkString,
>> tkLString,
>> tkWString: result:=[some compare]
>> tkFloat: result:=[some compare]
>> else raise exception.create('ERROR');
>> end;
>>
>> //No need to search any further! We found the right property!
>> break;
>
> Her stopper du efter det første felt, uanset result.
>

Njea, den breaker vel kun ud af property-løkke: "for look:=0 to
Pred(Count)" og ikke ud af While-løkken som løber igennem de nøgler jeg
ønsker at sortere efter...

Break er naturligvis ikke nødvendig, men der er ingen grund til at løbe
igennem de sidste properties i klassen da jeg jo har fundet den
rigtige...

MVH
Thomas


Søg
Reklame
Statistik
Spørgsmål : 177414
Tips : 31962
Nyheder : 719565
Indlæg : 6407849
Brugere : 218876

Månedens bedste
Årets bedste
Sidste års bedste