Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > ger.ct > #287753 > unrolled thread

[Programmierung] Darstellung einer Baumstruktur

Back to article view | Back to ger.ct

Contents

  [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-12 17:47 +0000
    Re: [Programmierung] Darstellung einer Baumstruktur Frank Möller <butterspiegeleiauftoast42@spl.at> - 2016-12-12 19:19 +0100
      Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-12 19:33 +0000
        Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-12 21:19 +0100
    Re: [Programmierung] Darstellung einer Baumstruktur Dennis Preiser <d__p@d--p.de> - 2016-12-12 18:32 +0000
      Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-12 19:33 +0000
        Re: [Programmierung] Darstellung einer Baumstruktur Herwig AQSR <herwig.huener@t-online.de> - 2016-12-12 16:41 -0800
          Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-13 05:28 +0000
            Re: [Programmierung] Darstellung einer Baumstruktur Stefan+Usenet@Froehlich.Priv.at (Stefan Froehlich) - 2016-12-13 07:26 +0000
            Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-13 08:31 +0000
            Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-13 10:18 +0100
            Re: [Programmierung] Darstellung einer Baumstruktur Herwig AQSR <herwig.huener@t-online.de> - 2016-12-13 03:57 -0800
              Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-14 10:06 +0100
                Re: [Programmierung] Darstellung einer Baumstruktur Wolfgang Kynast <wky@gmx.de> - 2016-12-14 10:17 +0100
                  Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-14 16:22 +0100
                    Re: [Programmierung] Darstellung einer Baumstruktur Herwig AQSR <herwig.huener@t-online.de> - 2016-12-14 10:45 -0800
                      Re: [Programmierung] Darstellung einer Baumstruktur Dietz Proepper <dietz-news@rotfl.franken.de> - 2016-12-14 21:00 +0100
                        Re: [Programmierung] Darstellung einer Baumstruktur Wolfgang Enzinger <we_usenet@nurfuerspam.de> - 2016-12-14 21:37 +0100
                          Re: [Programmierung] Darstellung einer Baumstruktur Gerrit Heitsch <gerrit@laosinh.s.bawue.de> - 2016-12-14 21:49 +0100
                            Re: [Programmierung] Darstellung einer Baumstruktur Wolfgang Kynast <wky@gmx.de> - 2016-12-14 23:17 +0100
                          Re: [Programmierung] Darstellung einer Baumstruktur Dietz Proepper <dietz-news@rotfl.franken.de> - 2016-12-14 23:25 +0100
                            Re: [Programmierung] Darstellung einer Baumstruktur Herwig AQSR <herwig.huener@t-online.de> - 2016-12-14 14:43 -0800
                        Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-15 10:14 +0100
                      Re: [Programmierung] Darstellung einer Baumstruktur Hermann Riemann <nospan.gerct08@hermann-riemann.de> - 2016-12-15 10:02 +0100
                Re: [Programmierung] Darstellung einer Baumstruktur Stefan+Usenet@Froehlich.Priv.at (Stefan Froehlich) - 2016-12-14 10:59 +0000
                  Re: [Programmierung] Darstellung einer Baumstruktur Matthias Eißing <meissing@gmx.de> - 2016-12-14 15:55 +0100
    Re: [Programmierung] Darstellung einer Baumstruktur Wolfgang Enzinger <we_usenet@nurfuerspam.de> - 2016-12-12 23:15 +0100
    Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-13 05:17 +0000
      Re: [Programmierung] Darstellung einer Baumstruktur Ricardo Szabo <usenet13@rickszabo.de> - 2016-12-13 19:55 +0000
    Re: [Programmierung] Darstellung einer Baumstruktur Thomas Heuving <heuving@gmx.de> - 2016-12-13 09:54 +0100

Page 1 of 2  [1] 2  Next page →

#287753 — [Programmierung] Darstellung einer Baumstruktur

Wahrscheinlich ist es eine triviale Frage, aber ich habe schon einen Knoten
im Kopf und komme einfach nicht drauf:

Gegeben ist eine Datenbank mit eMails. Die eMails haben eine
funktionierende Bezugsverkettung, für jede eMail ist also bekannt, ob sie 0
oder 1 Parent und wieviel Childs (0 - n) sie hat. Nun möchte ich ausgehend
von jeder beliebigen eMail die komplette Baumstruktur anzeigen, also im
Prinzip nix anderes als es jeder Usenet-Client auch macht.

Mir fehlt aber tatsächlich der komplette Ansatz, wie ich denn alle eMails
rekursiv durchlaufen kann?!
Mag mich mal jemand erleuchten?

Danke & Gruß
Rick


-- 
Bevor i mi afreg, is ma liaba wurscht...

[toc] | [next] | [standalone]

#287762

Ricardo Szabo schrieb:

> Wahrscheinlich ist es eine triviale Frage, aber ich habe schon einen Knoten
> im Kopf und komme einfach nicht drauf:

> Gegeben ist eine Datenbank mit eMails. Die eMails haben eine
> funktionierende Bezugsverkettung, für jede eMail ist also bekannt, ob sie 0
> oder 1 Parent und wieviel Childs (0 - n) sie hat. Nun möchte ich ausgehend
> von jeder beliebigen eMail die komplette Baumstruktur anzeigen, also im
> Prinzip nix anderes als es jeder Usenet-Client auch macht.

> Mir fehlt aber tatsächlich der komplette Ansatz, wie ich denn alle eMails
> rekursiv durchlaufen kann?!
> Mag mich mal jemand erleuchten?

Jede Mail hat einen References-Header. Nur die Ursprungs-Mail hat ihn
nicht. AFAIK stellen NUAs anhand dieses Headers die Baumstruktur eines
Threads dar.

Zusätzlich haben Mails noch den Header "In-Reply-To", der sich auf die
direkte Eltern-Mail bezieht. (Manche Usenet-Postings haben diesen Header
auch, aber dort gehört er AFAIK nicht hin.)

Ist es das, was Du suchst?

-- 
 

[toc] | [prev] | [next] | [standalone]

#287775

Frank Möller <butterspiegeleiauftoast42@spl.at> wrote:

> Ist es das, was Du suchst?

Leider nicht. Wie gesagt, die Bezugsverkettung besteht ja schon. Mein
Problem ist die Darstellung als Baum. 
Wo muss ich ansetzen, wie muss die Schleifenkonstruktion (?) aussehen, dass
ich alle Knoten und Childs erwische. 

Bye 
Rick 


-- 
Bevor i mi afreg, is ma liaba wurscht ...

[toc] | [prev] | [next] | [standalone]

#287783

Am 12.12.2016 um 20:33 schrieb Ricardo Szabo:

> Leider nicht. Wie gesagt, die Bezugsverkettung besteht ja schon. Mein
> Problem ist die Darstellung als Baum.
> Wo muss ich ansetzen, wie muss die Schleifenkonstruktion (?) aussehen, dass
> ich alle Knoten und Childs erwische.

Mir ist nicht klar was Du suchst.

Im Moment denke ich wie beim Dateisystem an Ordner und Dateien.

So was stelle ich intern als Listen dar,
wobei jedes Element auch wieder eine Liste sein kann.
Listen kann sich sequentiell (gleiche Stufe; z.B. Schleife)
  und rekursiv (Schachtelung z.B. Unterprogramm) durchlaufen.
Die Ordner wären die Struktur wie bei Antworten,
die Dateien (oder deren Dateiname) die mails selber.

Hermann
    der hier ein Programmierproblem vermutete
    allerdings nicht die zu erwartete Programmiersprache kennt.

-- 
www.Hermann-Riemann.de

[toc] | [prev] | [next] | [standalone]

#287765

Ricardo Szabo <usenet13@rickszabo.de> wrote:
> Wahrscheinlich ist es eine triviale Frage, aber ich habe schon einen Knoten
> im Kopf und komme einfach nicht drauf:
> 
> Gegeben ist eine Datenbank mit eMails. Die eMails haben eine
> funktionierende Bezugsverkettung, für jede eMail ist also bekannt, ob sie 0
> oder 1 Parent und wieviel Childs (0 - n) sie hat. Nun möchte ich ausgehend
> von jeder beliebigen eMail die komplette Baumstruktur anzeigen, also im
> Prinzip nix anderes als es jeder Usenet-Client auch macht.
> 
> Mir fehlt aber tatsächlich der komplette Ansatz, wie ich denn alle eMails
> rekursiv durchlaufen kann?!
> Mag mich mal jemand erleuchten?

Ein Ansatz:

Zu jeder Message-ID werden drei Zeiger gespeichert. Einer auf die ID des
parent, einer auf die ID des child und einer auf die ID eines sibling.

Ist der parent-Zeiger NULL, dann handelt es sich um den Anfang eines
thread. Den Anfang eines thread findet man, indem man den parent-Zeigern
nachgeht, bis einer NULL ist.

Siblings sind prinzipiell gleichberechtigt. Wenn zu einer Message-ID
mehrere Childs gehören, dann wird das "älteste" als child-Zeiger
vermerkt und zu diesem das "zweitälteste" als sibling und zu diesem
wiederum das "drittälteste" usw. Möchte man alle siblings ermitteln,
muss man von einer Message-ID zum parent gehen und dann
->child->sibling->sibling... abklappern.

Dennis

[toc] | [prev] | [next] | [standalone]

#287776

Dennis Preiser <d__p@d--p.de> wrote:

> Ein Ansatz:
> Zu jeder Message-ID werden drei Zeiger gespeichert. Einer auf die ID des
> parent, einer auf die ID des child und einer auf die ID eines sibling.

Ok, Sibling war mir bislang noch gar nicht geläufig, eventuell bringt mich
das ein wenig weiter.

> Ist der parent-Zeiger NULL, dann handelt es sich um den Anfang eines
> thread. Den Anfang eines thread findet man, indem man den parent-Zeigern
> nachgeht, bis einer NULL ist.

Soweit war/ist es mir klar.

> Siblings sind prinzipiell gleichberechtigt. Wenn zu einer Message-ID
> mehrere Childs gehören, dann wird das "älteste" als child-Zeiger
> vermerkt und zu diesem das "zweitälteste" als sibling und zu diesem
> wiederum das "drittälteste" usw. Möchte man alle siblings ermitteln,
> muss man von einer Message-ID zum parent gehen und dann
> ->child->sibling->sibling... abklappern.

Das ist eventuell hilfreich, wenn mir auch auf Anhieb immer noch nicht klar
ist, wie ich die Schleife(n) bauen/verschachteln muss. Ich glaube, ich
schlafe da mal eine Nacht drüber, vielleicht stehe ich mir dann nicht mehr
selbst im Weg.

Bye 
Rick 



-- 
Bevor i mi afreg, is ma liaba wurscht ...

[toc] | [prev] | [next] | [standalone]

#287801

2016-12-13 01:42:00 +0100

> ...

> Das ist eventuell hilfreich, wenn mir auch auf Anhieb immer noch nicht klar
> ist, wie ich die Schleife(n) bauen/verschachteln muss. Ich glaube, ich
> schlafe da mal eine Nacht drüber, vielleicht stehe ich mir dann nicht mehr
> selbst im Weg.

Ich sehe das Problem nicht - um einen Baum zu durchforsten braucht man
doch nur einen klassischen BaumDurchLauf? Also im Prinzip folgende funktion:

function besuche_knoten {

mache_knoten_spezifisches
wenn erster Sohn vorhanden dann besuche_knoten (erster Sohn)
wenn bruder vorhanden dann besuce_knoten (bruder)
}

Das war es schon - damit kommt jeder Knoten der DatenStruktur vollständig
dran.

Dazu anekdotisches: Anfang der Neunziger Jahre hatte ich genau dieses
Problem - es war eine Funktion zu programmieren, die eine Anzahl von Knoten
in einem Baum durchläuft - aber mit einem beliebigen vorgegebenen Knoten
damit anfängt.

Nun ist ein BaumDurchlauf, wie oben angedeutet, ziemlich trivial, wenn
man den *ganzen* Baum durchlaufen möchte - aber einen TeilBaum an beliebiger
Stelle anzufangen zu durchlaufen, eventuell noch mit einer vorgegebenen Anzahl
von Knoten, so dass man eventuell mit dem BaumDurchLauf sogar noch weiter rauf
(*) kommt wie man angefangen hat, das ist eine ziemliche Fummellei, und die
hängt in Einzelheiten davon ab, wie die BaumElemente miteinander verpointert
sind.

Ich habe mir damals einen abgebrochen und es auch geschafft. Dann erfuhr ich,
dass das Design, nach dem ich vorging, nur vorsah, dass eventuelle Brüder im
Baum besucht werden sollen - und sonst nichts.

Das trug zu meiner Erheiterung nicht unwesentlich bei.

Der Code, der zum grössten Teil also gar nicht gebraucht wird, ist immer noch
im ESQL-Precompiler im BS2000 drin - ich habe es mir nicht getraut, ihn wieder
herauszupräparieren - er war ja nicht falsch - und sonst wird es auch niemand
getan haben.

Fazit von der Geschichte: Wenn Du einen Baum nur teilweise durchlaufen willst,
guck Dir die Requirements noch einmal ganz genau an.

Heute würde ich so vorgehen: Beim BaumAufbau eine VerlinkungsKette mit
aufzubauen, die jederzeit einen kanonischen BaumDurchLauf erlaubt. Dann sind
TeilBaumDurchläufe ganz einfach. Der Code muss *bloss* fehlerfrei sein.

Ich würde übrigens eine ProgrammierSprache nehmen, die Rekursion unterstützt.
Ohne Rekursion zu programmieren ist wie erektionsfrei bumsen.

(*) In der Informatik hängen Bäume immer über Kopf. Das ist beim Gebrauch
von Begriffen wie "weiter oben" zu beachten.

HTH

Herwig

[toc] | [prev] | [next] | [standalone]

#287805

Herwig AQSR <herwig.huener@t-online.de> wrote:

>> Das ist eventuell hilfreich, wenn mir auch auf Anhieb immer noch nicht klar
>> ist, wie ich die Schleife(n) bauen/verschachteln muss. Ich glaube, ich
>> schlafe da mal eine Nacht drüber, vielleicht stehe ich mir dann nicht mehr
>> selbst im Weg.
> 
> Ich sehe das Problem nicht - um einen Baum zu durchforsten braucht man
> doch nur einen klassischen BaumDurchLauf? Also im Prinzip folgende funktion:

Wahrscheinlich stelle ich mich gerade wirklich zu dämlich. Ich versuche
mein Problem mal zu beschreiben:

Gegeben sei Nachricht 1, zwei Söhne 1.1 und 1.2, Sohn 1.1 hat wiederum zwei
Söhne 1.1.1 und 1.1.2, Sohn 1.2 hat nur einen Sohn 1.2.1. Die gesamte
Anzahl der Nachrichten ist aber vorher nicht bekannt.

Ich starte bei 1 in der Datenbank und sehe, es sind zwei Söhne vorhanden.
Eine FOR-NEXT-Schleife hätte also jetzt zwei Zähler:

FOR ( i = 1; i < 2; ++i )

Beim ersten Sohn gibt es wieder zwei Söhne, also hätte die nächste Schleife
wieder zwei Zähler, verschachtelt wäre das also

FOR ( i = 1; i < 2; ++i )
  FOR (j = 1; j < 2; ++j )

Da ich aber weder weiß, wieviel Nachrichten ich insgesamt habe, noch auf
wieviel Ebenen die Verschachtelung stattfindet, kann ich es auf diese Weise
nicht machen. Ich muss also den Baum "linksseitig" nach unten durchlaufen
und immer, wenn es nach unten nicht mehr weitergeht, muss ich wieder eine
Verzweigung nach oben und dann den nächsten Sohn durchlaufen. Und hier ist
mein Denkproblem: Wenn ich wieder eine Verzweigung nach oben gehe, woher
"weiss" ich dann, dass ich den ersten (zweiten, dritten) Sohn schon
durchlaufen habe?

Man sieht, ich habe ein grundsätzliches Verständnisproblem... :-(

Bye
 Rick


-- 
Bevor i mi afreg, is ma liaba wurscht...

[toc] | [prev] | [next] | [standalone]

#287809

On Tue, 13 Dec 2016 06:28:55 Ricardo Szabo wrote:
> Wahrscheinlich stelle ich mich gerade wirklich zu dämlich.

Hast Du schon jemals eine Rekursion programmiert? Wenn nein, wäre das
eine mehr als günstige Gelegenheit, Dich damit zu beschäftigen.

> Gegeben sei Nachricht 1, zwei Söhne 1.1 und 1.2, Sohn 1.1 hat wiederum
> zwei Söhne 1.1.1 und 1.1.2, Sohn 1.2 hat nur einen Sohn 1.2.1. Die
> gesamte Anzahl der Nachrichten ist aber vorher nicht bekannt.

Klar.
 
> [...], verschachtelt wäre das also

> FOR ( i = 1; i < 2; ++i )
>   FOR (j = 1; j < 2; ++j )
 
> Da ich aber weder weiß, wieviel Nachrichten ich insgesamt habe,
> noch auf wieviel Ebenen die Verschachtelung stattfindet, kann ich
> es auf diese Weise nicht machen.

Wenigstens nicht *ganz* so trivial. Jede Rekursion lässt sich
iterativ auflösen, der Code wird dadurch allerdings nicht unbedingt
hübscher lesbar.

> Ich muss also den Baum "linksseitig" nach unten durchlaufen und
> immer, wenn es nach unten nicht mehr weitergeht, muss ich wieder
> eine Verzweigung nach oben und dann den nächsten Sohn durchlaufen.

> Und hier ist mein Denkproblem: Wenn ich wieder eine Verzweigung
> nach oben gehe, woher "weiss" ich dann, dass ich den ersten
> (zweiten, dritten) Sohn schon durchlaufen habe?

Du lässt immer die gleiche Funktion für Dich arbeiten, die sich
um genau *einen* Sohn kümmert, das ausgibt, was auszugeben ist und
danach (durch Aufruf *derselben* Funktion) dessen Kinder
verarbeitet. Strukturell hat Dir das eh schon jemand hier im Thread
aufgeschrieben, irgendetwas in der Art von:

process_child(parent) {
	print parent.name;
	foreach (parent.children as child) {
		process_child(child);
	}
}

Servus,
   Stefan

-- 
http://kontaktinser.at/ - die kostenlose Kontaktboerse fuer Oesterreich
Offizieller Erstbesucher(TM) von mmeike

Die Lust zu lieben! Stefan, gegen den Streß am Morgen!
(Sloganizer)

[toc] | [prev] | [next] | [standalone]

#287815

Ricardo Szabo <usenet13@rickszabo.de> wrote:

> Wahrscheinlich stelle ich mich gerade wirklich zu dämlich. 

So war es auch. :-)
Danke an alle für das mitdenken, zwei Kaffee später sind meine Synapsen
dann doch wieder aufgewacht und das Problem ist gelöst.

Bye 
Rick 

-- 
Bevor i mi afreg, is ma liaba wurscht ...

[toc] | [prev] | [next] | [standalone]

#287820

Am 13.12.2016 um 06:28 schrieb Ricardo Szabo:

> Gegeben sei Nachricht 1, zwei Söhne 1.1 und 1.2, Sohn 1.1 hat wiederum zwei
> Söhne 1.1.1 und 1.1.2, Sohn 1.2 hat nur einen Sohn 1.2.1. Die gesamte
> Anzahl der Nachrichten ist aber vorher nicht bekannt.

> Ich starte bei 1 in der Datenbank und sehe, es sind zwei Söhne vorhanden.
> Eine FOR-NEXT-Schleife hätte also jetzt zwei Zähler:

> FOR ( i = 1; i < 2; ++i )

> Beim ersten Sohn gibt es wieder zwei Söhne, also hätte die nächste Schleife
> wieder zwei Zähler, verschachtelt wäre das also

> FOR ( i = 1; i < 2; ++i )
>   FOR (j = 1; j < 2; ++j )

Wenn die Sprache Feld (array) kennt,
in der man mail-Hinweise (z.B. Dateinamen) speichern kann:
würde es mit einem Stapel (stack) gehen

index=0
mail=Nachricht_1
mail_anzahl=1
while (true){
    if mail_has_töchter
      # Gleichberechtigung: Kollegin würde child schreiben )

      #push
      feld[index]=mail
      index=index+1

      continue
    mail_anzahl = mail_anzahl+1

    wenn keine_Töchter_folgen:

       #pop
       index=index-1
       if index<0: break #ende
       mail=feld[index]
       continue

    mail=nächste_tochter

> Da ich aber weder weiß, wieviel Nachrichten ich insgesamt habe, noch auf
> wieviel Ebenen die Verschachtelung stattfindet, kann ich es auf diese Weise
> nicht machen.

Also ein Feld mir dynamischer Obergrenze.
Wenn das die Sprache nicht hergibt
kann man Dateien verwenden, in der man Feldbereiche auslagert.

> Ich muss also den Baum "linksseitig" nach unten durchlaufen
> und immer, wenn es nach unten nicht mehr weitergeht, muss ich wieder eine
> Verzweigung nach oben und dann den nächsten Sohn durchlaufen. Und hier ist
> mein Denkproblem: Wenn ich wieder eine Verzweigung nach oben gehe, woher
> "weiss" ich dann, dass ich den ersten (zweiten, dritten) Sohn schon
> durchlaufen habe?

Da gibt es noch die Möglicheiten
durchlaufene mails (in)direkt zu markieren.

Direkt wäre eine Markierung in den mails selber
z.B. Durch Anhängen von Sonderzeichen wie "---§§§"
Wobei die Löschung der Sonderzeichen einen erneuten Durchlauf erfordert.

Indirekt wäre z.B. eine Kopie des headers (oder md5sum) in ein
Feld oder Datei und das Absuchen (evlt. mit hash)
ob die mail schon dran war.

Hermann
    der Datenbanken nicht verwendet,
    und daher auch auch die mail-Darstellung nicht kennt.

-- 
www.Hermann-Riemann.de

[toc] | [prev] | [next] | [standalone]

#287842

2016-12-13 12:58:00 +0100

> ...

> Man sieht, ich habe ein grundsätzliches Verständnisproblem... :-(

Fachlich weiter unten ...

> ...

Da bist Du in bester Gesellschaft. Anekdotisch: Als wir nach der
JahrTausendWende anfingen, den neuen COBOL-Standard zu implementieren,
war es fällig, sich mit Rekursion zu beschäftigen. Das hatte es in
COBOL bis dahin nicht gegeben, und so standen die MitArbeiter - immerhin
auch Informatiker - die bis dahin sich jahrzehntelang mit dem
COBOL-Compiler beschäftigt hatten, dem Prinzip der Rekursion eher
ablehnend gegenüber ("Sowas braucht man nicht."). Dabei waren diese MA
unsere besten - ohne sie hätte es den COBOL-Compiler im BS2000 nicht
gegeben.

Der langjährige ChefProgrammierer war ein paar Tage jünger als ich und
hatte 2009 eine Abfindung genommen. Zwei Jahre später war er tot. Die
Vision, ihn bei WaldLäufen oder SpazierGängen zufällig zu treffen und
dann über alte Zeiten zu sprechen, hat sich nicht erfüllt.

Sonst hätte ich jetzt viel Zeit, ihn über die Meriten der Rekursion
zu informieren!

Es ist tatsächlich ein GewöhnungsProblem, sich mit Rekursion zu
beschäftigen. Wenn man es geschafft hat: Viele Probleme sind mit
Rekursion mit weniger Intelligenz zu lösen als ohne Rekursion!

Und man wird natürlich das Gefühl nicht los, dass Rekursion bedeutet,
ständig Probleme an sich selbst zu delegieren - und genau das ist es!

Spass beiseite - das fachliche:
===============================

Zwei Dinge haben erst einmal nichts miteinander zu tun: Zum einen,
wie die DatenStruktur "Baum" aufgebaut ist - also die Verlinkung.
Da gibt es durchaus mehrere möglichkeiten - und zum anderen die
notwendigen ZugriffsFunktionen. Diese zum Beispiel:

(1)

Einen Knoten einfügen.

Es ist schon ein Baum da, und ein neuer Knoten soll eingefügt werden.
Üblicherweise geht man dann zur Wurzel des Baumes (also das Ding da ganz
oben!) und hangelt sich dann bis zur Stelle des Einsetzens vor. Bei der
Gelegenheit merkt man auch gleich, ob der Knoten schon drin ist, und man
muss sich entscheiden, ob man jetzt eine FehlerMeldung machen sollte
oder einfach Nichtstun.

Mit dieser Funktion ist es bereits möglich, einen vollständigen Baum
von Scratch auf aufzubauen - und die BegriffsBildung "fertiger Baum"
- "unfertiger Baum" ist überflüssig.

(2)

Einen Knoten entfernen.

Das ist schon schwieriger - und oftmals gar nicht nötig. Eine einfache
Möglichkeit: Jeder Knoten kriegt ein Attribut (existiert - ja oder nein)
und verbleibt im Baum, als NavigationsHilfe für neue Einsetzvorgänge.

Für dieses Verfahren hat man eine SpeicherPlatzStrafe und eine
ZeitStrafe zu zahlen, aber sie ist völlig legitim. Wenn man den
Knoten aber richtig entfernen möchte, dann braucht man auch eine

(3)

Baum-Reorganisation

Bei Wirth ist das sehr schön dargestellt, wie man sowas etwa bei
binären Bäumen machen kann. Aber schon diese Aufgabe habe ich in meinem
ganzen BerufsLeben weder dienstlich noch privat programmieren müssen
- es kommt also nicht so häufig vor.

(4)

Knoten-Attribute setzen oder lesen.

Diese Funktion muss die Eigenschaft haben, sich bis zum
richtigen Knoten hinzunavigieren, dort zu machen, was sie machen
soll oder bei nichtexistierendem Knoten eine FehlerMeldung zu
machen.

Das ist jetzt alles. Die Trennung von Benutzung eines Baumes (diese
bis zu vier Funktionen) und der Implementierung eines Baumes (die
Verpointerung) ermöglicht, dass Du das eine ändern kannst, und das
andere bleibt unangerührt - und es bleibt fehlerfrei, falls es das
schon war.

***

Ein historisches Beispiel für das letztere: im Ada-Compiler im BS2000,
den wir zwischen Ende der 70-ger Jahre und Anfang der 90-ger Jahre
gemacht hatten, gab  es, wie in jedem Compiler, riesige Tabellen -
und die Zugriffe auf diese Tabellen wurden über Bäume realisiert. Die
Tabellen passten damals jedoch nicht in den Speicher - also wurden
sie auf dem PlattenSpeicher realisiert. Das hat den Compiler ein
bischchen runtergebremst - aber irgendwann in der mittleren Zukunft
hätten die Tabellen vollständig in den Speicher gepasst - und nach
dem Umprogrammieren der ZugriffsFunktionen wäre der Compiler von
einer Sekunde auf die andere flink geworden!

Das Management hat sich aber entschieden, den Compiler einzustampfen:
Mit fachlichen Argumenten kann man halt nicht ausrichten.

Herwig

[toc] | [prev] | [next] | [standalone]

#287967

Am 13.12.2016 um 12:57 schrieb Herwig AQSR:
> 2016-12-13 12:58:00 +0100
>
>> ...
>
>> Man sieht, ich habe ein grundsätzliches Verständnisproblem... :-(
>
> Fachlich weiter unten ...
>
>> ...
>
> Da bist Du in bester Gesellschaft. Anekdotisch: Als wir nach der
> JahrTausendWende anfingen, den neuen COBOL-Standard zu implementieren,
> war es fällig, sich mit Rekursion zu beschäftigen. Das hatte es in
> COBOL bis dahin nicht gegeben,

Bei den Uraltsprachen konnte Lisp Rekursion, FORTRAN nicht.

Hinzu kam, das Hauptspeicher knapp war.
( Und ohne Rekursion gehen viele Unterprogrammaufrufe schneller,
   da man etliche Argumentlisten teilweise statisch aufbauen konnte.)

Heutzutage sind bei Rechner wie Arduino noch Hauptspeicher knapp.


> Der langjährige ChefProgrammierer war ein paar Tage jünger als ich und
> hatte 2009 eine Abfindung genommen. Zwei Jahre später war er tot.

Könnte eher an Tschernobyl als an COBOL oder .. gelegen haben.

> Es ist tatsächlich ein GewöhnungsProblem, sich mit Rekursion zu
> beschäftigen. Wenn man es geschafft hat: Viele Probleme sind mit
> Rekursion mit weniger Intelligenz zu lösen als ohne Rekursion!

unterprogram sub(integer i)
    call sub(i+1)


> Spass beiseite - das fachliche:
> ===============================
>
> Zwei Dinge haben erst einmal nichts miteinander zu tun: Zum einen,
> wie die DatenStruktur "Baum" aufgebaut ist - also die Verlinkung.
> Da gibt es durchaus mehrere möglichkeiten - und zum anderen die
> notwendigen ZugriffsFunktionen. Diese zum Beispiel:
>
> (1)
>
> Einen Knoten einfügen.
>
> Es ist schon ein Baum da, und ein neuer Knoten soll eingefügt werden.
> Üblicherweise geht man dann zur Wurzel des Baumes (also das Ding da ganz
> oben!)

Das hängt von der Verkettung ab.
Eine saubere Verkettung macht nach oben gehen teilweise
Überflüssig.
Wenn Du eine Datei oder Ordner anlegst ( auch Baumstruktur)
gehst du ja auch nicht bis Wurzel  ( / ( oder C:) ) zurück.


> Einen Knoten entfernen.

Ausketten ( bei Felder eventuell Elemente verschieben)

> Bei Wirth ist das sehr schön dargestellt, wie man sowas etwa bei
> binären Bäumen machen kann. Aber schon diese Aufgabe habe ich in meinem
> ganzen BerufsLeben weder dienstlich noch privat programmieren müssen
> - es kommt also nicht so häufig vor.

Wohl nie mit Formeln auf computer hantiert?
Das lässt sich ganz gut in Baumdarstellung machen.
(Z.B. mit lisp (oder Python))
So wie bei einem Syntaxbaum bei compiler.
Ob physikalische Formeln oder Optimierung von Programmlogik
betrieben wird, ist beides ähnlich.

> Knoten-Attribute setzen oder lesen.

Knoten können Strukturen oder Klassen enthalten.

> Diese Funktion muss die Eigenschaft haben, sich bis zum
> richtigen Knoten hinzunavigieren,

Eine Sache von geschickter Verkettung.
Bei C++ fehlt IMHO oft in der Verkettung die Verweise noch "oben".
So das man von einem Element ausgehend bei root anfangen mus.
Informatiker denken an Iterator.
Und wenn man da ein Element einfügen löschen will ..

> dort zu machen, was sie machen soll oder
> bei nichtexistierendem Knoten eine FehlerMeldung zu machen.

Oder erst versuchen, den Knoten selber zu erstellen.
(automatisch zusammensuchen testen etc.)

> Ein historisches Beispiel für das letztere: im Ada-Compiler im BS2000,
> den wir zwischen Ende der 70-ger Jahre und Anfang der 90-ger Jahre
> gemacht hatten, gab  es, wie in jedem Compiler, riesige Tabellen -
> und die Zugriffe auf diese Tabellen wurden über Bäume realisiert.

Autotechnik des 19. Jahrhunderts?

> Das Management hat sich aber entschieden, den Compiler einzustampfen:
> Mit fachlichen Argumenten kann man halt nicht ausrichten.

Die schauen auch auf die Kosten.
Handarbeit ist in D nicht billig.
Und etwas automatisieren ist bei der Nachmach Mentalität
ungewohnt.

Hermann
    fragend wann computer Manager etc. "einstampfen"
    ( nach den gleichen Verfahren wie sie ihre
      Untergeben "einstampfen.")

-- 
www.Hermann-Riemann.de

[toc] | [prev] | [next] | [standalone]

#287969

On Wed, 14 Dec 2016 10:06:55 +0100, "Hermann Riemann" posted:

>Am 13.12.2016 um 12:57 schrieb Herwig AQSR:
>> 2016-12-13 12:58:00 +0100
>>
>>> ...
>>
>>> Man sieht, ich habe ein grundsätzliches Verständnisproblem... :-(
>>
>> Fachlich weiter unten ...
>>
>>> ...
>>
>> Da bist Du in bester Gesellschaft. Anekdotisch: Als wir nach der
>> JahrTausendWende anfingen, den neuen COBOL-Standard zu implementieren,
>> war es fällig, sich mit Rekursion zu beschäftigen. Das hatte es in
>> COBOL bis dahin nicht gegeben,
>
>Bei den Uraltsprachen konnte Lisp Rekursion, FORTRAN nicht.

Trotzdem konnte man in Fortran selbstverständlich rekursiv
programmieren, war halt etwas Arbeit.


-- 
Schöne Grüße,
Wolfgang

[toc] | [prev] | [next] | [standalone]

#288028

Am 14.12.2016 um 10:17 schrieb Wolfgang Kynast:

> Trotzdem konnte man in Fortran selbstverständlich rekursiv
> programmieren, war halt etwas Arbeit.

Und in Pascal ST konnte ich auch anders programmieren,
wenn ich mit Hilfe von GST Assembler
den stack pointer ausgetauscht hatte.

Hermann
    der nicht sicher ist,
    ob das jemand außer ihm auch so gemacht hat.

-- 
www.Hermann-Riemann.de

[toc] | [prev] | [next] | [standalone]

#288057

2016-12-14 19:46:00 +0100

> ...

> Und in Pascal ST konnte ich auch anders programmieren,
> wenn ich mit Hilfe von GST Assembler
> den stack pointer ausgetauscht hatte.

Das hört sich nach quick-and-dirty an.

So. Etwas. Macht. Man. Nicht.

Was mich an eine Stelle im BS2000-Ada-Compiler erinnert,
wo vorsätzlich auf gerade abgeräumte Elemente des
Attribut-Stacks zugegriffen wurde. Kommentar war
"-- I know it's dirty but it is so simple."
Hat auch die ganze Zeit fehlerfrei funktioniert.

Macht man trotzdem nicht.

Herwig

[toc] | [prev] | [next] | [standalone]

#288073

Am 14.12.2016 um 19:45 schrieb Herwig AQSR:
> 2016-12-14 19:46:00 +0100
>
>> ...
>
>> Und in Pascal ST konnte ich auch anders programmieren,
>> wenn ich mit Hilfe von GST Assembler
>> den stack pointer ausgetauscht hatte.
>
> Das hört sich nach quick-and-dirty an.

Works (tm).

> So. Etwas. Macht. Man. Nicht.

Nur. Wenn. Man. Unbedingt. Muss.

> Was mich an eine Stelle im BS2000-Ada-Compiler erinnert,
> wo vorsätzlich auf gerade abgeräumte Elemente des
> Attribut-Stacks zugegriffen wurde. Kommentar war
> "-- I know it's dirty but it is so simple."
> Hat auch die ganze Zeit fehlerfrei funktioniert.

Nun, der Unterschied zwischen einem guten und einem schlechten Hack - 
der gute funktioniert die ganze Zeit fehlerfrei.

> Macht man trotzdem nicht.

Wenn der hack eine Zeile statt 50 umfasst und 1/10 der CPU-Zeit benötigt 
dann darf man zumindest darüber nachdenken.

[toc] | [prev] | [next] | [standalone]

#288077

Am Wed, 14 Dec 2016 21:00:13 +0100 schrieb Dietz Proepper:

>> Macht man trotzdem nicht.
> 
> Wenn der hack eine Zeile statt 50 umfasst und 1/10 der CPU-Zeit benötigt 
> dann darf man zumindest darüber nachdenken.

Eventuell meinst du das Gleiche wie ich, aber ich würde anders formulieren:
wenn man den Hack und was man damit bewirken wollte nach drei Jahren noch
auf Anhieb versteht, dann darf man.

Wobei man das vorher oft dummerweise nicht sicher abschätzen kann.

[toc] | [prev] | [next] | [standalone]

#288078

On 12/14/2016 09:37 PM, Wolfgang Enzinger wrote:
> Am Wed, 14 Dec 2016 21:00:13 +0100 schrieb Dietz Proepper:
>
>>> Macht man trotzdem nicht.
>>
>> Wenn der hack eine Zeile statt 50 umfasst und 1/10 der CPU-Zeit benötigt
>> dann darf man zumindest darüber nachdenken.
>
> Eventuell meinst du das Gleiche wie ich, aber ich würde anders formulieren:
> wenn man den Hack und was man damit bewirken wollte nach drei Jahren noch
> auf Anhieb versteht, dann darf man.

Man kann die Chancen erhöhen indem man den Hack sauber kommentiert.

  Gerrit

[toc] | [prev] | [next] | [standalone]

#288098

On Wed, 14 Dec 2016 21:49:31 +0100, "Gerrit Heitsch" posted:

>On 12/14/2016 09:37 PM, Wolfgang Enzinger wrote:
>> Am Wed, 14 Dec 2016 21:00:13 +0100 schrieb Dietz Proepper:
>>
>>>> Macht man trotzdem nicht.
>>>
>>> Wenn der hack eine Zeile statt 50 umfasst und 1/10 der CPU-Zeit benötigt
>>> dann darf man zumindest darüber nachdenken.
>>
>> Eventuell meinst du das Gleiche wie ich, aber ich würde anders formulieren:
>> wenn man den Hack und was man damit bewirken wollte nach drei Jahren noch
>> auf Anhieb versteht, dann darf man.
>
>Man kann die Chancen erhöhen indem man den Hack sauber kommentiert.

das ist das Stichwort für die schöne Geschichte von 
"!!! only valid in the eighties !!!" :-)

-- 
Schöne Grüße,
Wolfgang

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | ger.ct

csiph-web