C++ / Rekursion

Re(4): Stacküberlauf ?

gepeinigter_aon_neukunde — Mon, 19 Sep 2005 09:52:22 GMT

Hehe...
Genau das meinte ich mit meinem Schlußabsatz

Re(3): Stacküberlauf ?

ecgnwotan — Fri, 16 Sep 2005 19:55:21 GMT

Hab ich behauptet Rekursion ist schlecht? Sicher nicht. Ich hab nur drauf hingewiesen, dass man eben auf den Stack achten soll/muss, sonst nix.

Un mitm pthread_attr_setstacksize hast schon recht

Re(2): Stacküberlauf ?

gepeinigter_aon_neukunde — Fri, 16 Sep 2005 12:56:08 GMT

Naja...

Erstens: Wenn du pthread_attr_setstacksize net verwendest, bist wissentlich ins Messer gerannt
Zweitens: sehe ich pthreads als ähnlichen "Exoten" wie embedded Devices... Beide gibt's sehr oft, aber beide haben ganz eigene Regeln
Drittens: Als Allgemeinplatz finde ich die Aussage "vermeide Rekursionen" definitiv falsch
Viertens: Sein Buch wirkt wie ein Einsteigerbuch... Da hat sowas überhaupt nichts zu suchen ,-).

Vieles läßt sich elegant und sauber einfach mit Rekursionen lösen. Klar kann man alles ohne Rekursion lösen, nur das Argument "Stacküberlauf" gilt für jede Rekursion gleich wie für jeden "normalen" Funktionsaufruf (eine Rekursion ist ja ein auch in Wirklichkeit ein ganz normaler Aufruf fürs System)...

So oder so, du hast absolut Recht, daß es [manchmal] Gründe gibt, auf Rekursionen zu verzichten - aber eben nur manchmal...
cu
gepeinigter.

Re: Stacküberlauf ?

ecgnwotan — Fri, 16 Sep 2005 09:27:24 GMT

Sorry, aber sobald man multithreading fährst, muss man aufpassen. Desgleichen bei DCE-RPC. Meldung: 'process killed due to trashed stack' auf einer HP-UX midrange Unix Kiste mit 4 CPU's und 4 Gig Ram habe ich schon gesehen.

Das kommt wohl daher, dass der Stack eines neuen pthreads etwas klein ist (64KB), ausser Du setzt ihn beim Erzeugen schon rauf.

Stacküberlauf ?

gepeinigter_aon_neukunde — Fri, 16 Sep 2005 09:11:38 GMT

Wirklich nur in Ausnahmefällen, also
- Embedded Devices mit seeehr wenig RAM
- Strangen Devices ohne MMU und ohne HW-Stack
- Extrem aufwändigen Funktionen

Denn mit der gleichen Argumentation könntest auch sagen "meide Funktionsaufrufe, bau lieber lineare Programme"

Re: C++ / Rekursion

ecgnwotan — Thu, 15 Sep 2005 11:50:39 GMT

Auf den Stacküberlauf muss man aufpassen, ansonsten vernachlässigbar, wenn Du nicht wirklich große Datenstrukturen als lokale Variablen oder im Funktionsaufruf verwendest.

Re(9): Dein Buch ist schrott...

Marax — Thu, 15 Sep 2005 09:33:51 GMT

hmm...tja is leider so...

geh zum orf

hab gestern gelesen das der roman raffreider (oder wie der da genau heißt) gut 15.000€ monatlich verdient als moderator etc

und ATV hat ihm sogar +16.000€ geboten wenn er zu denen wechselt

Re(8): Dein Buch ist schrott...

Fly — Thu, 15 Sep 2005 09:30:27 GMT

Schön wär's ja. Du unterschätzt die Bürokratie eines Konzerns gewaltig. Ich muss mit meiner Arbeitsleistung eine Menge Overhead mitfinanzieren.

Re(7): Dein Buch ist schrott...

Marax — Thu, 15 Sep 2005 09:23:15 GMT

also was du ein unternehmen kostest??

dann wärn es also gut 40€ brutto für dich

Re(6): Dein Buch ist schrott...

Fly — Thu, 15 Sep 2005 09:11:03 GMT

Was meinst jetzt mit Brutto? Gesamtkosten.

Re(5): Dein Buch ist schrott...

Marax — Thu, 15 Sep 2005 09:03:22 GMT

brutto?

Re(4): Dein Buch ist schrott...

Fly — Thu, 15 Sep 2005 08:57:36 GMT

Dann bin ich ja direkt billig! Ich koste knapp 80€ intern.

Hmm... mal über mein Gehalt nachdenken...

Re(3): Dein Buch ist schrott...

gepeinigter_aon_neukunde — Thu, 15 Sep 2005 08:54:29 GMT

Yup - genau das ist der Punkt.

Denn der Programmierer kostet zusätzlich Arbeitgeberabgaben, Anteilig Büroplatz, Storage, Client-PC's, Putzfrau, Verwaltung, ...

Und dem Unternehmen ist ja mal wurscht, wieviel er verdient - dem ist nur wichtig, wieviel es zahlen muß

Die Kosten passen schon mit 120-500 Euro...

Re(2): Dein Buch ist schrott...

Fly — Thu, 15 Sep 2005 07:15:06 GMT

Naja, zwischen kosten und bekommen ist halt ein kleiner Unterschied.

Re: Dein Buch ist schrott...

nergal — Thu, 15 Sep 2005 04:26:24 GMT

Die Stunde eines [guten] Programmierers kostet insgesamt rd. 120-500 Euro.

Kennst Du wirklich Programmierer die einen solchen Stundensatz haben? - ich nicht - die Leute die ich kenne - und das sind sehr gute Leute . bekommen knapp unter 100 Euro per Stunde.

Re: Dein Buch ist schrott...

promillo — Wed, 14 Sep 2005 22:05:40 GMT

das is mal eine antwort wie ich sie mir erwarte.. und leider bleibts hier oft beim warten

ja hast recht.. is ein schrottiges buch.. hab eh noch stroustrub und 2 mal sedgewick da liegen.. hab darüber leider nix auf die schnelle gefunden außer einem hinweise dass " bei sehr großen problemen der stack eine rekursive lösung verhindern kann"... darum meine frage..

welche bücher kannst du sonst noch empfehlen?

Re(4): C++ / Rekursion

promillo — Wed, 14 Sep 2005 22:00:26 GMT

dass es für kleinere aufgaben komplett irrelevant ist ist mir klar... bei welchen fällen könnt sowas zu einem problem werden?

Re: C++ / Rekursion

Robert Craven — Wed, 14 Sep 2005 21:27:45 GMT

Kommt drauf an, was du machst (und wie du es machst). So allgemeine Aussagen sind nie 100% korrekt. Wennst viele grosse lokale Variablen und eine hohe Rekursionstiefe hast, dann stimmt das schon.

Dein Buch ist schrott...

gepeinigter_aon_neukunde — Wed, 14 Sep 2005 21:18:09 GMT

Wahrscheinlich von irgendeinem Jolly, der gerade mal Windows programmiert, geschrieben.

Definitiv stimmt die Aussage, daß es Speicherplatz braucht. Allerdings ist die Frage, wieviel da realistisch zusammenkommt. Intel-CPU's verwenden die ENTER/LEAVE-Kombi auf Assemblerebene - das bedeutet, daß die Stackanforderung selbst mal mit wenigen CPU-Zyklen auskommt - also auf weniger als einer Milliardstel-Sekunden auf aktuellen Rechner... Und Speicher wird genausoviel angefordert wie lokale nicht-statische Variablen in der Funktion.

Wenn du also sagen wir 10 int32-werte in deiner lokalen Funktion hast - dann sind das 40 Bytes. Bei einer Rekursionstiefe von 25000 (was utopisch hoch ist) - hast gerade mal ein einziges Megabyte verschleudert - und auch nur zum "tiefsten" Zeitpunkt der Rekursion.

Als [seit >10 Jahren beruflicher] Programmierer sage ich Dir:
Meine Zeit, auch nur einen Gedanken an 1MB Storage [das eh nur millisekunden alloziert wird] zu verschwenden, ist weit teurer als der Speicher selbst .

Wenn du nicht von gaaaanz extremen Rekursiven Funktionen sprichst - vergiß das Statement des Buchs.

Die Stunde eines [guten] Programmierers kostet insgesamt rd. 120-500 Euro. Selbst wenn er nur den Richtsatz der WKO kostet (und da geht's um durchschnittliche Programmierer) - und er sich beinhart einen Algo überlegt, wo er nur 512K Speicher braucht - und er dafür mit Doku, Test, ... 8 Stunden investierte - so kosteten im Endeffekt 512KB Ram mehr als 800 Euro... Wieviel RAM hättest dafür einkaufen können ?

Abschlußaussage:
Meide Bücher, wo endgültige, uneingeschränkte Statements auftreten

Re(3): C++ / Rekursion

Fly — Wed, 14 Sep 2005 20:56:01 GMT

Du hast natürlich den Overhead, der dadurch entsteht daß hier der Aufruf auf'm Stack rumkugelt. Ob's jetzt allerdings sinnvoller ist, es iterativ zu lösen oder rekursiv hängt von einigen Faktoren ab. Von der Architektur die Du verwendest, vom System und nicht zuletzt von der Aufgabenstellung.

Re(2): C++ / Rekursion

promillo — Wed, 14 Sep 2005 20:40:08 GMT

also wenn ich die funktion rekursiv aufrufe ohne eine neue variable anzulegen braucht er kan neuen speicher anfordern? aber irgendwo muss er sich doch den zwischenschritt merken oder?

STL gut und schön.. hilft mir aber weder beim verständnis meines problems noch bei der aufgabenstellung..

Re: C++ / Rekursion

Fly — Wed, 14 Sep 2005 20:18:56 GMT

Kommt drauf an wie man's implementiert. Es stimmt wohl, daß lokale Variablen für jede Rekursion angelegt werden, man kann allerdings durchaus auch ohne auskommen, bzw. die Notwendigkeit derselben auf die "Ausnahmefälle" (sprich Abbruchbedingung oder "Gefunden" usw) beschränken. Oft genug, vor allem wenn man's mit Klassen realisiert, kommt man überhaupt ohne aus.

Lies Dich in die STL ein, damit sind viele der Probleme mit linked lists usw. leicht zu vermeiden.

Re(5): C++ / Rekursion

mko — Wed, 14 Sep 2005 19:26:39 GMT

So schnell lauft der scho net über

Re(4): C++ / Rekursion

promillo — Wed, 14 Sep 2005 19:26:21 GMT

stacküberlauf?

keine ahnung, drum frag ich ja

Re(3): C++ / Rekursion

mko — Wed, 14 Sep 2005 19:23:05 GMT

Hmm.
Jetzt weiß ichs auch nimmer
Aber wenn scho, was würds machen?

Re(2): C++ / Rekursion

promillo — Wed, 14 Sep 2005 19:21:51 GMT

aber wird dann nicht jedes mal eine neue variable angelegt mit der adresse des nächsten elements?

Re: C++ / Rekursion

mko — Wed, 14 Sep 2005 19:15:03 GMT

kann ich dieses problem (zb bei verketteten listen) irgendwie mit zeigern
umgehen?

Würd ich schon sagen...dazu sind Pointer ja da.

C++ / Rekursion

promillo — Wed, 14 Sep 2005 18:40:19 GMT

bin grad in einem buch über folgenden text gestolpert:

verzichten sie auf rekursive funktionen ... rekursionen sind teuer - bei jedem aufruf wird für jede verwendete variable in dieser funktion ein eigener speicherplatz angelegt... stacküberlauf..

wie weit stimmt das? kann ich dieses problem (zb bei verketteten listen) irgendwie mit zeigern umgehen?

bin grad a bissl verwirrt