[Delphi] Boom (tree) probleempje.

[anoniem]

Ik zit helemaal vast. Het ergste is, ik heb het vaker gedaan. Verleerd denk ik. Het is een klein probleempje ook. Ik heb nu twee classes. Scherm van het typte TForm en Boom van het type TBoom. Ik krijg van Scherm heel veel data binnen. Deze sla ik op in een boom structuur. Dus vanuit Scherm maak ik een Boom aan. Nu weet ik uiteraard hoe ik het aantal takken kan tellen of de hoogste waarde kan uitlezen. Maar hoe lees ik nou die hele boom ook alweer uit ? stuk uit TForm [code:1:ed5e58daf0] .. Zit in een while loop die net zolang doorgaat tot dat de data op is. if Boom = nil then Boom := TBoom.Create(data, nil, nil) else Boom.VulBoom(data); end; end; Resultaat.Lines.Add('============='); Resultaat.Lines.Add(Boom.LeesBoom); [/code:1:ed5e58daf0] En TBoom [code:1:ed5e58daf0] function TBoom.LeesBoom : string; begin if links <> nil then LeesBoom := links.LeesBoom else if rechts <> nil then LeesBoom := rechts.LeesBoom else LeesBoom := self.data; //Hiermoet de data naar TForm gaan en in de Memo-box worden geplaatst. end; [/code:1:ed5e58daf0] Zo stom eigenlijk. Heb het hele prorgamma al een ISA kaart met een IC laten uitlezen. Blijf ik hier op hangen :o

[anoniem]

Wat doe je in VulBoom? Debug eens en kijk wat data is.

[anoniem]

De boom wordt perfect gebouwd. Het zijn uiteraard objecten bestaande uit een string en een integer. Ik kan ook tak 3 van links uitlezen bijvoorbeeld. Het probleem is hem nou dat ik graag een tak / node als object naar TForm wil terug geven. Boom.leesboom is dan een recursieve functie die constant een tak naar TForm geeft. Ik heb een oplossing gemaakt door elke tak een boolean gelezen mee te geven. Dus dan [code:1:2c1a290c72] while not boom.gelezen do memo.lines.add(boom.leesuit) [/code:1:2c1a290c72] Ik zat te denken aan TList die gevuld wordt, maar hoe deel ik een TList tussen twee objecten ?

[anoniem]

En opeens heb ik het. Ik maak een TList in TForm aan. En dan pseudo, ben nu Delphi loos. [code:1:d2bd2d3385] while not Boom.gelezen TList.add(object van TBoom); [/code:1:d2bd2d3385] Dan kan ik in TForm de boel ook netjes uitpakken. Dit zou moeten gaan werken. Weer in TList verdiepen ;)

[anoniem]

Okay... Je maakt een boompje en gebruikt daarbij een treelist? Lijkt mij niet goed. Als je een tree bouwt dan doe je dat met een linked list principe. Iets als: [code:1:45c3b91b4f]type TBoom=class private FLinks: TBoom; FRechts: TBoom; public property Links: TBoom read FLinks write FLinks; property Rechts: TBoom read FRechts write FRechts; end;[/code:1:45c3b91b4f] Maar ja, ik ben maar een Pascal-purist in dir soort dingen... ;) Verder wil ik effe opmerken dat je een recursieve methode gebruikt om door de tree heen te lopen maar in principe kun je dit beter doen met een niet-recursieve methode. Is een beetje lastiger te bedenken, dat geef ik toe. Maar als het je lukt is het een zeer bewonderenswaardige prestatie. Daarnaast, als je Delphi 5 of hoger gebruikt, overweeg dan het gebruik van een dynamische array in plaats van een TList. Iets als: var Bomen: array of TBoom; Daarna kun je eenvoudig via SetLength(Bomen, n) de array op de gewenste grootte brengen. De Length(Bomen) functie geeft daarbij steeds de huidige lengte terug. Functies Low(Bomen) en High(Bomen) geven de ondergrens en bovengrens terug, hoewel Low(Bomen) in het algemeen 0 zal teruggeven bij een dynamische array. Het enige lastige bij arrays is dat je zelf code zult moeten schrijven om een record ergens in het midden toe te voegen of om een record te verwijderen. Maar als je eenmaal de juiste code hiervoor weet, is een array net zo krachtig als een TList.

[anoniem]

[quote:1247a34f3d="Workshop Alex"] Het enige lastige bij arrays is dat je zelf code zult moeten schrijven om een record ergens in het midden toe te voegen of om een record te verwijderen. Maar als je eenmaal de juiste code hiervoor weet, is een array net zo krachtig als een TList.[/quote:1247a34f3d] Waarom dan een array gebruiken?

[anoniem]

[quote:1e38c90863="h4xX0r"][quote:1e38c90863="Workshop Alex"] Het enige lastige bij arrays is dat je zelf code zult moeten schrijven om een record ergens in het midden toe te voegen of om een record te verwijderen. Maar als je eenmaal de juiste code hiervoor weet, is een array net zo krachtig als een TList.[/quote:1e38c90863] Waarom dan een array gebruiken?[/quote:1e38c90863] Oh, simpel. Een array bevat records van een bepaald type terwijl je met een TList steeds met pointertjes moet blijven werken. Wil je dit alles netjes afwerken voor verder gebruik dan is het practisch om gewoon een wrapper om het systeem te maken. Qua performance maakt het ook vrij weinig uit. Maar een belangrijk verschil is dat een dynamische array standaard vanuit het systeem wordt gesteund terwijl je voor de TList de Classes unit moet toevoegen. Ik hou me wel eens bezig om zo klein mogelijke executables te maken en probeer dan gewoon de Classes unit te vermijden om zo beneden de 100 KB te blijven. En als je eenmaal gewend bent aan het werken met dynamische arrays dan werkt het best lekker.

[anoniem]

[quote:53270974e7="Workshop Alex"][quote:53270974e7="h4xX0r"][quote:53270974e7="Workshop Alex"] Het enige lastige bij arrays is dat je zelf code zult moeten schrijven om een record ergens in het midden toe te voegen of om een record te verwijderen. Maar als je eenmaal de juiste code hiervoor weet, is een array net zo krachtig als een TList.[/quote:53270974e7] Waarom dan een array gebruiken?[/quote:53270974e7] Oh, simpel. Een array bevat records van een bepaald type terwijl je met een TList steeds met pointertjes moet blijven werken. Wil je dit alles netjes afwerken voor verder gebruik dan is het practisch om gewoon een wrapper om het systeem te maken. Qua performance maakt het ook vrij weinig uit. [/quote:53270974e7] Bij veelvuldig toevoegen en verwijderen is een dynamische array aanmerkelijk trager. Dit komt, omdat bij een wijziging van het aantal elementen een nieuwe array aangemaakt wordt met de juiste grootte en daar de inhoud van de oude array naar toe wordt gekopieerd. [quote:53270974e7="Workshop Alex"] Maar een belangrijk verschil is dat een dynamische array standaard vanuit het systeem wordt gesteund terwijl je voor de TList de Classes unit moet toevoegen. Ik hou me wel eens bezig om zo klein mogelijke executables te maken en probeer dan gewoon de Classes unit te vermijden om zo beneden de 100 KB te blijven. [/quote:53270974e7] Leuk als hobby...

[anoniem]

[quote:f29885eedd="h4xX0r"]Bij veelvuldig toevoegen en verwijderen is een dynamische array aanmerkelijk trager. Dit komt, omdat bij een wijziging van het aantal elementen een nieuwe array aangemaakt wordt met de juiste grootte en daar de inhoud van de oude array naar toe wordt gekopieerd.[/quote:f29885eedd] Ehm, nee. Da's dus niet waar. In ieder geval niet binnen Delphi. En niet als je het gewoon goed doet. Ik heb de performance van Delphi's dynamische arrays vergeleken met een vergelijkbaar programma dat gebruik maakt van een TList. Het maakte niet echt verschil. Het meest belangrijke verschil tussen een TList en een dynamische array is dat een TList steeds extra blokken geheugen alloceert waarin meerdere extra items kunnen worden opgeslagen, en dus twee counters bijhoudt. Eentje voor het aantal opgeslagen items en eentje voor de totale capaciteit van de list. Verder gebruikt een TList iets snellere routines om een blok items opwaards en neerwaards te kopieren. Maar een dynamische array is heel erg practisch als je relatief weinig wijzigingen maakt. Voor een project moest ik een snelle parser ontwikkelen voor tekst-bestanden van enkele tientallen megabytes. Via een memory-mapped file het bestand gemapped in het geheugen en vervolgens via een dynamische arrays een lijst gemaakt van pointers binnen dit tekstbestand die de positie en lengte van iedere regel teruggeeft. Zo'n lijst hoef je dus maar 1 keer te maken, waarna je de lijst dus veelvuldig kunt doorlopen op zoek naar wat je maar wilt zoeken. Dit doorlopen van zo'n array gaat niet sneller als je daar een TList voor gebruikt dus was voor de ontwikkeling hiervan een array veel practischer. De code werd er immers een stuk leesbaarder op. Daarnaast gebruikte ik natuurlijk ook een truuk om niet te veel de array aan te hoeven passen. Net als de TList reserveerde ik steeds een grote buffer tijdens het aanmaken van de lijst. Mocht de buffer te klein worden dan reserveerde ik gewoon nog meer. Waren uiteindelijk alle regels bepaald dan stelde ik de lengte in van de array op het exacte aantal en het resultaat ervan is bijzonder snel. En geen typecasts nodig in je code. En je mag het wel een hobbie vinden om te proberen om applicaties zo klein mogelijk te houden maar je leert er wel van om zo optimaal mogelijk code te schrijven. Voor veel programmeurs geldt dat als ze niet af en toe dit soort uitdagingen aangaan dat ze gewoon slordiger gaan programmeren. Vaal niet echt een probleem, zeker niet als je met GUI's werkt. Maar mijn specialiteit is het schrijven van achtergrondstaken waarvan een hoge performance wordt geeist.

[anoniem]

[quote:def0daeddf="Workshop Alex"][quote:def0daeddf="h4xX0r"][b:def0daeddf]Bij veelvuldig toevoegen en verwijderen is een dynamische array aanmerkelijk trager[/b:def0daeddf]. Dit komt, omdat bij een wijziging van het aantal elementen een nieuwe array aangemaakt wordt met de juiste grootte en daar de inhoud van de oude array naar toe wordt gekopieerd.[/quote:def0daeddf] Ehm, nee. Da's dus niet waar. In ieder geval niet binnen Delphi. En niet als je het gewoon goed doet. Ik heb de performance van Delphi's dynamische arrays vergeleken met een vergelijkbaar programma dat gebruik maakt van een TList. Het maakte niet echt verschil. Het meest belangrijke verschil tussen een TList en een dynamische array is dat een TList steeds extra blokken geheugen alloceert waarin meerdere extra items kunnen worden opgeslagen, en dus twee counters bijhoudt. Eentje voor het aantal opgeslagen items en eentje voor de totale capaciteit van de list. Verder gebruikt een TList iets snellere routines om een blok items opwaards en neerwaards te kopieren. [b:def0daeddf]Maar een dynamische array is heel erg practisch als je relatief weinig wijzigingen maakt[/b:def0daeddf]. Voor een project moest ik een snelle parser ontwikkelen voor tekst-bestanden van enkele tientallen megabytes. Via een memory-mapped file het bestand gemapped in het geheugen en vervolgens via een dynamische arrays een lijst gemaakt van pointers binnen dit tekstbestand die de positie en lengte van iedere regel teruggeeft. Zo'n lijst hoef je dus maar 1 keer te maken, waarna je de lijst dus veelvuldig kunt doorlopen op zoek naar wat je maar wilt zoeken. Dit doorlopen van zo'n array gaat niet sneller als je daar een TList voor gebruikt dus was voor de ontwikkeling hiervan een array veel practischer. De code werd er immers een stuk leesbaarder op. Daarnaast gebruikte ik natuurlijk ook een truuk om niet te veel de array aan te hoeven passen. Net als de TList reserveerde ik steeds een grote buffer tijdens het aanmaken van de lijst. Mocht de buffer te klein worden dan reserveerde ik gewoon nog meer. Waren uiteindelijk alle regels bepaald dan stelde ik de lengte in van de array op het exacte aantal en het resultaat ervan is bijzonder snel. En geen typecasts nodig in je code. [/quote:def0daeddf] Je moet het doel niet uit het oog verliezen: 1. Een dynamische array is relatief traag bij het uitbreiden van de array. 2. Je kan items vrij snel opzoeken in een dynamische array. 3. Sorteren gaat ook vrij snel. (achteraf). Linked list: 1. Praktisch als je van te voren het aantal elementen niet weet. 2. Handig als je niet hoeft te sorteren. 3. Snel in het toevoegen en verwijderen. "Dynamische array"-test scenario: [code:1:def0daeddf] procedure TForm1.Button1Click(Sender: TObject); var i: integer; tmp: array of integer; TimeStart, TimeEnd: TDateTime; begin TimeStart := Now; for i:= 1 to 10000000 do begin SetLength(tmp, i); tmp[i-1] := i; end; TimeEnd := Now; Edit1.Text := FloatToStr(SecondSpan(TimeEnd,TimeStart)); end; [/code:1:def0daeddf] "Linked list"-test scenario [code:1:def0daeddf] procedure TForm1.Button2Click(Sender: TObject); var i: integer; tmp: TList; TimeStart, TimeEnd: TDateTime; begin TimeStart := Now; tmp := TList.Create(); try for i:= 1 to 10000000 do begin tmp.Add(Pointer(i)); end; finally tmp.Free; end; TimeEnd := Now; Edit2.Text := FloatToStr(SecondSpan(TimeEnd,TimeStart)); end; [/code:1:def0daeddf] [code:1:def0daeddf] Aantal items Tijd in seconden Tijd in seconden Dynamische array Linked list -------------- ----------------- ------------------------------- 100 0 0 1000 0 0 10000 0 0 100000 0,030999630689621 0,0150000443682075 1000000 0,171999796293676 0,030999630689621 10000000 2,10900020319968 0,438000541180372 100000000 22,8119997074828 4,31299963966012 1000000000 ???? [List capacity out of bounds] 10000000000 ???? 100000000000 ???? [/code:1:def0daeddf] Test machine: Intel P4 HT 2.8Mhz 800 Mhz FSB

[anoniem]

Okay, probeer het nou nog eens maar dan als volgt: [code:1:cf7e0939a8]procedure TForm1.Button1Click(Sender: TObject); var i: integer; tmp: array of integer; TimeStart, TimeEnd: TDateTime; begin TimeStart := Now; SetLength(tmp, 0); I := 0; while (I < 10000000) do begin if (I > High(tmp)) then SetLength(tmp, length(tmp) + 1024); tmp[i] := i+1; inc(I); end; SetLength(tmp, i); TimeEnd := Now; Edit1.Text := FloatToStr(SecondSpan(TimeEnd,TimeStart)); end; [/code:1:cf7e0939a8] Dit keer reserveer ik dus steeds een buffer die ik vervolgens kan opvullen. Doordat de for-lus in een while-lus is veranderd is i achteraf nog steeds een geldige waarde. (Maar vertraagt het wel iets.) Aan het eind bevat i dus het aantal elementen in de dynamische array. De waarde 1024 is overigens willekeurig gekozen zodat de array niet netjes op een rond getal uitkomt. Door geheugen in blokken te reserveren versnel ik de dynamische array dus, volgens mij. Maar voor een eerlijke test zul jij het moeten testen. :) Als je dus veel gegevens wilt toevoegen dan kun je dat beter in grote blokken reserveren. De TList doet precies hetzelfde, capaciteit reserveren voor nieuwe toevoegingen. Voor het verwijderen van gegevens is het alleen belangrijk dat je gegevens in je array opschuift. In principe kan dot ook via hetzelfde move() statement als wat de TList gebruikt, alleen is het even iets meer rekenwerk om de pointer naar de juiste plekken te vinden.

[anoniem]

Iedergeval de software hoefde ik niet verder af te maken, ik had hem eventjes gemaakt om data te analyseren. Maar dat bleek bij de eerste proefdraai (met de extra foute variabele) al onmogelijk werk te zijn. Ben nog niet aan TList oplossing toegekomen. Wel met de foute oplossing om een extra variabele gelezen te gebruiken. Ik heb zitten nadenken over een oplossing om je hele boom op het scherm te krijgen. Nou is mijn nieuwe vraag bestaat er in Delphi een variabele die bij alle objecten uit een klasse gelijk is ? Wat Java ook heeft Stel dat ik een TList maak, dat toch voor het snellere werk handiger is voor mij, en deze definieer in de klasse TBoom. Dat elk object uit TBoom deze TList langer kan maken ? Dus TList een soort klassen variabele wordt. Zoiets als static int TotaalAantalObjecten in Java en dat bij elke object dat gemaakt wordt laat ik deze integer een verhogen. Ik ben geen expert in Delphi, daarom ben ik wel nieuwsgierig wat property voor commando is.

[anoniem]

[quote:573ea17592]Nou is mijn nieuwe vraag bestaat er in Delphi een variabele die bij alle objecten uit een klasse gelijk is ?[/quote:573ea17592] Ik snap even niet wat je hier bedoelt... Wel heb ik het idee dat je beter eerst meer van Delphi (classes) kunt gaan studeren voordat je aan de complexere zaken begint. Het is alsof je tijdens je eerste rijles van je leven jezelf al helemaal naar huis rijdt. (Heb ik overigens gedaan tijdens mijn eerste les! Van het oefenterrein zo'n 10 km naar huis...) Sommige mensen kunnen dit maar er valt nog heel wat bij te leren. (Uiteindelijk had ik 70 lessen nodig.) Als je de handleiding hebt, lees deze dan eens goed door. Anders een ander goed boek over Delphi. Wat belangrijk is is dat je eerste de basis-beginselen over classes leert!