C Tutorial - Expertenthemen

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
Xeon
Beiträge: 36
Registriert: So Dez 17, 2017 4:10 pm

C Tutorial - Expertenthemen

Beitrag von Xeon » Do Jan 09, 2020 3:22 pm

Hallo zusammen

Strukturen organisieren:

https://www.proggen.org/doku.php?id=c:tutorial:meta

Bin bei Arrays von Zeigern.

Das Array playField ist hier 24 Byte groß - 3 Adressen zu je 8 Byte (auf einem 64 Bit-System). An den Adressen zeigt sich, dass sich jede Spalte im Spielfeld an unterschiedlichen Stellen im Speicher befinden, zumindest nicht hintereinander. Wenn wir genau hinsehen, stellen wir auch fest, dass die Adressen bei diesem Betriebssystem (Debian Linux 2.6.35.3) hier im Freispeicher befinden (der Speicher wurde mit malloc() angefordert), statt als lokale Variable der Funktion main auf dem Stack zu liegen (die Speicherstelle ist extrem groß: Die Adressen zuvor begannen mit 7fff). Wir erkennen, dass das Betriebssystem statt der 3 Byte, die wir benötigen, gleich 32 Bytes (hexadizimal 20) anfordert.

Dieser Text den ich unterstrichen habe ist mir nicht ganz klar. Warum 32 Bytes?


Danke im voraus
Xeon

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8514
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: C Tutorial - Expertenthemen

Beitrag von Xin » Do Jan 09, 2020 3:53 pm

Es müssen nicht unbedingt 32 Byte sein, das darf das OS nach belieben entscheiden. Die Anforderung ist ja, dass man 3 Byte am Stück braucht und das ist bei 32 Byte am Stück ja auch gegeben.

3 Byte ist ein sehr unpraktischer Wert, die wenn die wieder freigeben werden - wann werden das nächste mal 3 Byte benötigt? Und wie aufwendig wird es, sich solche freien Stellen im Speicher zu merken? Das kostet mehr, als es bringt. Entsprechend kann das OS hingehen und Pakete schnüren. Für kleinste Speicherblöcke kann es beispielsweise 32 Byte rausgeben. Wenn Du die 3 Byte wieder freigibst und dannach 17 Byte anforderst, bekommst Du den gleichen Speicherbereich - passt ja.

Desweiteren ist der Zugriff auf eine 64 Bit Adresse schneller als auf eine Byte-Adresse. Würde ein Pointer genau auf die Speicherzelle zeigen, die nach den 3 Byte kommt, wäre der Zugriff langsamer. Die Geschwindigkeit des Programms würde also von der Anordnung der Daten abhängig sein. Speicher ist heute sehr billig, CPU Leistung ist teuer. Also legt die Speicherverwaltung Wert darauf, dass alle herausgegebenen Speicherblöcke an einer 64-Bit angepassten Adresse liegen. Das ist bei 32-Byte-Häppchen automatisch gegeben.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 36
Registriert: So Dez 17, 2017 4:10 pm

Rekursion

Beitrag von Xeon » Mi Jan 15, 2020 2:36 pm

Hallo zusammen,

Rekursion und Optimierung:

https://www.proggen.org/doku.php?id=c:t ... :recursion

Bin bei Optimierung:

Code: Alles auswählen

unsigned int fibonacci_intern( unsigned int fib )
{
  if( fib <= 2 ) return 1;
 
  return fibonacci_intern( fib-1 ) + fibonacci_intern( fib-2 );
}
 
unsigned int fibonacci( unsigned int fib )
{
  if( fib == 0 ) return 0;
 
  return fibonacci_intern( fib );
}
Sagen wir mal ich übergebe der Funktion den Wert 7. Was passiert bei der Funktion fibonacci_intern in dieser Zeile: return fibonacci_intern( fib-1 ) + fibonacci_intern( fib-2 ); ?
Wird zuerst fibonacci_intern( fib-1 ) und dann fibonacci_intern( fib-2 ) aufgerufen und dann addiert?
Könnte mir das jemand ausführlich erklären was da passiert?


Liebe Grüße
Xeon

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8514
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Rekursion

Beitrag von Xin » Mi Jan 15, 2020 2:49 pm

Xeon hat geschrieben:
Mi Jan 15, 2020 2:36 pm
Bin bei Optimierung:

Code: Alles auswählen

unsigned int fibonacci_intern( unsigned int fib )
{
  if( fib <= 2 ) return 1;
 
  return fibonacci_intern( fib-1 ) + fibonacci_intern( fib-2 );
}
Sagen wir mal ich übergebe der Funktion den Wert 7. Was passiert bei der Funktion fibonacci_intern in dieser Zeile: return fibonacci_intern( fib-1 ) + fibonacci_intern( fib-2 ); ?
Wird zuerst fibonacci_intern( fib-1 ) und dann fibonacci_intern( fib-2 ) aufgerufen und dann addiert?
Könnte mir das jemand ausführlich erklären was da passiert?
Sehr schöne Frage!

Das spielt in diesem Fall eigentlich keine Rolle, da die fibonacci_intern Funktion über keine Seiteneffekte verfügt. Würde sie Variablen außerhalb der Funktion ändern, könnte die Reihenfolge der Aufrufe wichtig sein. Hier wird aber wird nur der Rückgabewert berechnet und kein Einfluss von außen ändert etwas daran.

Die Reihenfolge hängt vom Operator ab.

Grundsätzlich ist das aber geregelt, siehe hier: Operatorprioritäten. Die Assoziativität gibt an, ob erst der linke Ausdruck (L-R) oder der rechte Ausdruck (R-L) ausgewertet wird. + als Infix-Operator (inmitten zweier Operanden) ist L-R, also erst das Linke-Argument, dann das rechte.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 36
Registriert: So Dez 17, 2017 4:10 pm

Re: Rekursion

Beitrag von Xeon » Mi Jan 22, 2020 2:33 pm

Hallo Xin,

ich habe an der Funktion fibonacci_intern ein bisschen experimentiert, bin aber zu keinem logischen Ergebnis gekommen.

Code: Alles auswählen

unsigned int fibonacci_intern( unsigned int fib )
{
  printf("- %d - ", fib); //Codeverlauf verfolgen

  if( fib <= 2 ) return 1;

  return fibonacci_intern( fib-2 ) + fibonacci_intern( fib-1 );
}
Beendet die zweite return Anweisung im Code die Funktion oder?


Grüße
von Xeon

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8514
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Rekursion

Beitrag von Xin » Mi Jan 22, 2020 3:54 pm

Xeon hat geschrieben:
Mi Jan 22, 2020 2:33 pm
ich habe an der Funktion fibonacci_intern ein bisschen experimentiert, bin aber zu keinem logischen Ergebnis gekommen.

Code: Alles auswählen

unsigned int fibonacci_intern( unsigned int fib )
{
  printf("- %d - ", fib); //Codeverlauf verfolgen

  if( fib <= 2 ) return 1;

  return fibonacci_intern( fib-2 ) + fibonacci_intern( fib-1 );
}
Beendet die zweite return Anweisung im Code die Funktion oder?
Jede Return-Anweisung beendet die Funktion. Wird eine Return-Anweisung erreicht, werden nachfolgende Anweisungen nicht mehr ausgeführt. Das return 1 sorgt also dafür, dass das nachfolgende return nicht mehr erreicht.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 36
Registriert: So Dez 17, 2017 4:10 pm

Re: Rekursion

Beitrag von Xeon » Mi Jan 22, 2020 4:42 pm

Ah, jetzt habe ich verstanden für was die zweite Return-Anweisung gut ist: Wenn die Rekursion zu Ende ist wird der Rückgabe Wert von fibonacci_intern( fib-2 ) + fibonacci_intern( fib-1 ) zusammen addiert und dann wird das Ergebnis an die zweite Return-Anweisung übergeben. Richtig?



Liebe Grüße
Xeon

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8514
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Rekursion

Beitrag von Xin » Mi Jan 22, 2020 5:53 pm

Xeon hat geschrieben:
Mi Jan 22, 2020 4:42 pm
Ah, jetzt habe ich verstanden für was die zweite Return-Anweisung gut ist: Wenn die Rekursion zu Ende ist wird der Rückgabe Wert von fibonacci_intern( fib-2 ) + fibonacci_intern( fib-1 ) zusammen addiert und dann wird das Ergebnis an die zweite Return-Anweisung übergeben. Richtig?
Genau. Und die Summe der beiden rekursiben Aufrufe wird dann als Ergebnis an Funktion übergeben, die "mich" gerufen hat.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten