Op deze website gebruiken we cookies om content en advertenties te personaliseren, om functies voor social media te bieden en om ons websiteverkeer te analyseren. Ook delen we informatie over uw gebruik van onze site met onze partners voor social media, adverteren en analyse. Deze partners kunnen deze gegevens combineren met andere informatie die u aan ze heeft verstrekt of die ze hebben verzameld op basis van uw gebruik van hun services. Meer informatie.

Akkoord

Vraag & Antwoord

Programmeren

[Delphi] Boom (tree) probleempje.

Workshop Alex
12 antwoorden
  • 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
  • Wat doe je in VulBoom?

    Debug eens en kijk wat data is.
  • 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 ?
  • 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 ;)
  • 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.
  • [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?
  • [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.
  • [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…
  • [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.
  • [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
  • 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.
  • 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.

Beantwoord deze vraag

Dit is een gearchiveerde pagina. Antwoorden is niet meer mogelijk.