• Im ersten Teil der heutigen Vorlesung haben Sie Programme gelesen und vorhergesagt, was sie tun. Jetzt geht es darum, wie lange ein Programm für seine Arbeit braucht, und wie man das abschätzt, ohne zu messen. Dazu sehen Sie einen Klassiker der Informatik, die Suche in einem Array, und lernen abzuschätzen, wie die Laufzeit wächst, wenn die Eingabe größer wird. Am Ende bauen Sie Ihren ersten eigenen Datentyp.

• Macht das einen Unterschied? Bei "Hallo" nicht. Bei einem sehr langen String schon: strlen zählt jedes Mal alle Zeichen bis zum \0, und das in jedem Durchlauf. Das folgende Programm baut einen String aus lauter a, so lang, wie Sie es beim Aufruf angeben, und zählt dann die a. Der String liegt in einem globalen Array oben in der Datei, außerhalb von main. Ein globales Array ist mit Nullen vorbelegt: Das \0 hinter dem letzten a steht also schon da, und vier Millionen Zeichen haben sicher Platz. Wie man so viel Speicher besser anfordert, sehen Sie in Vorlesung 4.

  #include <cs50.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  char s[4000001];
  
  int main(int argc, string argv[])
  {
      // Einen String aus lauter 'a' bauen, so lang wie angegeben
      int laenge = atoi(argv[1]);
      for (int i = 0; i < laenge; i++)
      {
          s[i] = 'a';
      }
  
      // Jedes Zeichen einmal ansehen
      int zaehler = 0;
      for (int i = 0; i < strlen(s); i++)
      {
          if (s[i] == 'a')
          {
              zaehler++;
          }
      }
      printf("%i\n", zaehler);
  }

• Mit time vor dem Aufruf misst das Terminal, wie lange ein Programm läuft (Zeile real):

  $ time ./laenge 250000
  250000
  
  real    0m0.595s

• Die Abhilfe stand schon in Notes 2 (Abschnitt Stringlänge), hier noch einmal Schritt für Schritt. Der Kopf einer for-Schleife hat drei Teile, getrennt durch Semikolons. Der erste Teil läuft genau einmal, vor dem ersten Durchlauf. Die Bedingung in der Mitte prüft das Programm vor jedem Durchlauf neu. Steht strlen(s) dort, zählt es also vor jedem Durchlauf wieder alle Zeichen.

• Deshalb kommt der Aufruf in den ersten Teil: Die Länge wird einmal vor der Schleife bestimmt und in n gemerkt.

  for (int i = 0, n = strlen(s); i < n; i++)

  Im ersten Teil dürfen Sie mehrere Variablen desselben Typs anlegen, durch ein Komma getrennt: hier i mit 0 und n mit der Länge. Die Bedingung vergleicht danach nur noch zwei Zahlen. Jetzt ruft das Programm strlen genau einmal auf. Eine Million Zeichen dauern nur noch wenige Tausendstel Sekunden. Die Zeit steigt jetzt nur noch so wie die Länge: Doppelt so viele Zeichen, doppelt so lange, aber auf dem Niveau von Tausendsteln.

• Moderne Compiler können so einen Aufruf oft selbst aus der Schleife ziehen, wenn man sie optimieren lässt (-O2). make übersetzt in unserer Kursumgebung ohne Optimierung, deshalb sehen Sie den Unterschied hier so deutlich. Verlassen sollten Sie sich darauf ohnehin nicht.

• Wie man so etwas abschätzt, ohne zu messen, sehen Sie im Abschnitt Laufzeit. Mit time messen Sie in Übung 4 auch die Sortierprogramme.

• Dasselbe Prinzip funktioniert im Hörsaal. Um herauszufinden, wie viele Personen im Raum sind, gehen alle so vor:

  1. Stehen Sie auf und denken Sie an die Zahl 1.
  2. Bilden Sie ein Paar mit jemandem, der steht, addieren Sie beide Zahlen und merken Sie sich die Summe.
  3. Eine Person des Paares setzt sich hin.
  4. Wenn Sie noch stehen, gehen Sie zurück zu Schritt 2.

• Stellen Sie sich sieben Kisten nebeneinander vor, in jeder liegt ein Geldschein. Sie wollen wissen: Ist die 50 dabei? Von außen sehen Sie nichts, Sie müssen eine Kiste öffnen, um hineinzuschauen. Genau so geht es einem Computer mit einem Array: Er kann immer nur ein Element ansehen.
• Herauszufinden, ob ein Wert in einem Array vorkommt, ist ein Standardproblem der Informatik: die Suche. Die Eingabe ist das Array und der gesuchte Wert, die Ausgabe ist true oder false.

• Die einfachste Lösung: Kiste für Kiste von links nach rechts öffnen, bis die 50 auftaucht. Das heißt lineare Suche. Als Pseudocode, also als für Menschen lesbare Anleitung, die schon nach Programm aussieht:

  Für jede Kiste von links nach rechts
      Wenn 50 in der Kiste ist
          Gib true zurück
  Gib false zurück

  Mit Array-Schreibweise, wie Sie es gleich in C programmieren:

  Für i von 0 bis n-1
      Wenn 50 in kisten[i] ist
          Gib true zurück
  Gib false zurück

• Als Pseudocode:

  Wenn keine Kisten übrig sind
      Gib false zurück
  Wenn 50 in der mittleren Kiste ist
      Gib true zurück
  Sonst wenn 50 < mittlere Kiste
      Durchsuche die linke Hälfte
  Sonst wenn 50 > mittlere Kiste
      Durchsuche die rechte Hälfte

  Die erste Zeile ist wichtig: Ohne sie würde der Algorithmus nie aufhören, wenn die 50 gar nicht da ist. Mit Array-Schreibweise werden aus den Hälften Bereiche von Indizes. Zwei Grenzen merken sich, welcher Bereich noch übrig ist: Am Anfang ist links 0 und rechts n − 1.

  Solange links <= rechts
      mitte = (links + rechts) / 2
      Wenn 50 in kisten[mitte] ist
          Gib true zurück
      Sonst wenn 50 < kisten[mitte]
          rechts = mitte - 1
      Sonst
          links = mitte + 1
  Gib false zurück

  „Keine Kisten übrig“ heißt jetzt: links ist größer als rechts. Bei einer geraden Zahl von Kisten gibt es zwei mittlere; (links + rechts) / 2 rundet als Ganzzahldivision ab und nimmt die linke.

• Bei jeder geöffneten Kiste fällt die Hälfte der übrigen weg. Die binäre Suche öffnet auch die letzte übrige Kiste noch: Bei n Kisten sind es höchstens k Blicke, wenn 2^k größer als n ist. Bei 7 Kisten also höchstens 3, bei 8 schon 4, bei 15 höchstens 4. Das ist dasselbe Prinzip wie beim Zählen im Hörsaal.

• Dieses Vorgehen heißt Teile und herrsche (Vorlesung 0): Das Problem wird in jedem Schritt kleiner, und auf dem kleineren Stück macht man dasselbe noch einmal. Wie man „mach dasselbe auf der Hälfte noch einmal“ direkt in C schreibt, sehen Sie im zweiten Teil (Rekursion).

Stufe 1. 23, 8, 15. Die Mitte der 7 Zahlen ist die 23; 15 ist kleiner, also bleiben 3 8 15. Deren Mitte ist die 8; 15 ist größer, also bleibt die 15.

Stufe 2. 37, 79, 56, 46, dann ist kein Bereich mehr übrig. Die Mitte der 15 Zahlen ist die 37 (40 ist größer, rechts weiter: 46 … 121). Mitte 79 (kleiner, links: 46 56 67). Mitte 56 (kleiner, links: 46). 46 ist nicht 40, und links von der 46 ist nichts mehr: Die 40 kommt nicht vor.

Stufe 3. 10 bei 1000 Zahlen und 20 bei einer Million. Jeder Blick halbiert den Rest: Nach 10 Blicken ist von 1000 Zahlen nichts mehr übrig, weil 2¹⁰ = 1024 größer als 1000 ist. Bei einer Million: 2²⁰ = 1 048 576.

• Wie lange ein Programm in Sekunden braucht, hängt vom Rechner ab. In der Informatik interessiert deshalb eine andere Frage: Wie wächst die Zahl der Schritte, wenn die Eingabe größer wird? Man nennt das die Ordnung der Laufzeit und schreibt sie in der O-Notation.
• Dabei zählt nur die Form der Kurve, also der Teil, der am schnellsten wächst (bei n² + n nur n²). Ob ein Verfahren n oder n/2 Schritte braucht: Beides wächst linear, beides ist O(n). Auch die Basis des Logarithmus spielt keine Rolle, man schreibt einfach O(log n).

• Die wichtigsten Klassen, von langsam nach schnell:

  Klasse	Name	Beispiel
  O(n²)	quadratisch	strlen in der Bedingung der Schleife (oben gemessen)
  O(n log n)	n log n	kommt im zweiten Teil (Merge Sort)
  O(n)	linear	lineare Suche; die Schleife mit n = strlen(s)
  O(log n)	logarithmisch	binäre Suche
  O(1)	konstant	ein Element eines Arrays über seinen Index lesen

• Zwei ineinander geschachtelte Schleifen über n Elemente brauchen n · n Schritte, also O(n²). So eine Schleife steckt auch in strlen in der Bedingung: Die äußere ist Ihre for-Schleife, die innere zählt strlen. Beim Sortieren im zweiten Teil sehen Sie weitere.

• O gibt eine Obergrenze an: So lange dauert es höchstens. Wir verwenden sie für den schlechtesten Fall (Worst Case). Die lineare Suche braucht im schlechtesten Fall n Schritte, die binäre Suche etwa log₂ n.

• Genauso wichtig ist der beste Fall (Best Case). Liegt die 50 gleich in der ersten Kiste, ist die lineare Suche nach einem Schritt fertig. Für eine Untergrenze (so schnell geht es mindestens) schreibt man den griechischen Buchstaben Ω (Omega); wir verwenden sie für den besten Fall: Die lineare Suche ist Ω(1), die binäre Suche auch (die 50 liegt genau in der Mitte). Sind Ober- und Untergrenze gleich, schreibt man Θ (Theta). Im schlechtesten Fall ist die binäre Suche viel schneller, deshalb nimmt man sie, wenn die Daten schon sortiert sind. Im zweiten Teil sehen Sie Sortierverfahren, bei denen bester und schlechtester Fall weit auseinanderliegen.

• Jetzt programmieren wir die lineare Suche in C. Die sieben Kisten sind ein Array mit sieben Zahlen, gesucht wird eine Zahl, die der Benutzer eingibt. Ein erster Versuch, mit dem, was Sie aus Vorlesung 1 und 2 kennen (code search.c):

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    int n = get_int("Zahl: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Gefunden\n");
        }
        else
        {
            printf("Nicht gefunden\n");
        }
    }
}

• int numbers[] = {20, 500, 10, 5, 100, 1, 50}; legt das Array an und füllt es gleich; die Länge (7) bestimmt der Compiler aus der Zahl der Werte.
• Das Programm meldet für jede Zahl im Array etwas. Der Fehler ist verwandt mit der falschen Fassung des Pseudocodes von vorhin: Ob eine Zahl fehlt, weiß man erst, wenn man alle angesehen hat. „Nicht gefunden“ gehört also hinter die Schleife.

for (int i = 0; i < 7; i++)
{
    if (numbers[i] == n)
    {
        printf("Gefunden\n");
    }
}
printf("Nicht gefunden\n");

• Bei 7 stimmt die Ausgabe jetzt. Bei 50 gibt das Programm aber Gefunden und Nicht gefunden aus: Die Schleife läuft nach dem Fund weiter bis zum Ende, und danach kommt die Zeile mit Nicht gefunden in jedem Fall.

• Was wir eigentlich wollen: Sobald die Zahl gefunden ist, ist das ganze Programm fertig. Das erledigt return. In main beendet return 0; das Programm mit dem Exit-Code 0 (Erfolg), wie Sie es aus Vorlesung 2 kennen:

  #include <cs50.h>
  #include <stdio.h>
  
  int main(void)
  {
      int numbers[] = {20, 500, 10, 5, 100, 1, 50};
  
      int n = get_int("Zahl: ");
      for (int i = 0; i < 7; i++)
      {
          if (numbers[i] == n)
          {
              printf("Gefunden\n");
              return 0;
          }
      }
      printf("Nicht gefunden\n");
      return 1;
  }

  $ ./search
  Zahl: 50
  Gefunden
  $ echo $?
  0
  $ ./search
  Zahl: 7
  Nicht gefunden
  $ echo $?
  1

• Die Zeile mit Nicht gefunden erreicht das Programm jetzt nur, wenn die Schleife ganz durchgelaufen ist, ohne die Zahl zu finden. Dann endet es mit return 1. Für den Erfolg nimmt man die 0, weil es meist nur einen Erfolgsfall gibt, aber viele mögliche Fehler; die übrigen Zahlen bleiben für die verschiedenen Fehler.

• Der Unterschied in einem Satz: break verlässt die Schleife, return verlässt die Funktion (in main also das Programm).

• break ist dann richtig, wenn nach der Schleife noch etwas passieren soll. Dann merkt man sich in einer Variablen, ob die Zahl gefunden wurde:

  bool gefunden = false;
  for (int i = 0; i < 7; i++)
  {
      if (numbers[i] == n)
      {
          gefunden = true;
          break;
      }
  }
  
  if (gefunden)
  {
      printf("Gefunden\n");
  }
  else
  {
      printf("Nicht gefunden\n");
  }

• Mit break statt continue käme 530 heraus (20 + 500 + 10): Bei der 5 endet die ganze Schleife.

• Zusammengefasst:

  Anweisung	Was sie beendet
  continue	den aktuellen Durchlauf der Schleife, weiter mit dem nächsten
  break	die ganze Schleife, weiter hinter der Schleife
  return	die ganze Funktion (in main: das Programm)

• continue und break machen eine Schleife oft kürzer, aber nicht immer leichter zu lesen. Häufig lässt sich dasselbe auch mit einem if ausdrücken (hier: if (scheine[i] >= 10)).

• Was, wenn die Kisten Wörter enthalten? Dann ändert sich nur die Bedingung: Statt zwei Zahlen vergleicht das Programm zwei Strings.

• Dafür gibt es die Funktion strcmp (string compare) aus string.h. Sie kam in Notes 2 schon vor (Abschnitt Stringlänge), hier noch einmal: strcmp geht beide Strings Zeichen für Zeichen durch und gibt eine Zahl zurück, kein true oder false.

  strcmp("Hund", "Hund")     // 0: gleich
  strcmp("Hund", "Katze")    // negativ: "Hund" kommt vorher
  strcmp("Katze", "Hund")    // positiv: "Katze" kommt später

  Gleich heißt 0. Vorher und später richten sich nach den ASCII-Werten der Zeichen.

• Welche dieser Bedingungen findet das Wort?

  // A
  if (strings[i] == s)
  
  // B
  if (strcmp(strings[i], s))
  
  // C
  if (strcmp(strings[i], s) == 0)

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string strings[] = {"Schiff", "Auto", "Hund", "Katze", "Hut"};

    string s = get_string("Wort: ");
    for (int i = 0; i < 5; i++)
    {
        if (strcmp(strings[i], s) == 0)
        {
            printf("Gefunden\n");
            return 0;
        }
    }
    printf("Nicht gefunden\n");
    return 1;
}

• Nur C ist richtig. strcmp gibt 0 zurück, wenn beide Strings gleich sind.
• A findet nie etwas: == vergleicht bei Strings, wo sie im Speicher stehen, nicht welche Zeichen darin stehen.
• B findet alles, auch Maus: Ohne == 0 ist die Bedingung wahr, sobald strcmp nicht 0 zurückgibt, also sobald die Wörter verschieden sind. Schon beim ersten Wort im Array, das nicht passt, meldet das Programm Gefunden. Der Compiler warnt bei A und B nicht.
• Warum gibt strcmp bei Gleichheit 0 zurück und nicht true? Weil es mehr kann: Das Vorzeichen sagt, welcher String zuerst kommt. Das ist nützlich zum Sortieren. Weil Großbuchstaben in ASCII vor den Kleinbuchstaben kommen, steht "Zebra" dabei vor "apfel".

• Oft sucht man etwas, um an das zu kommen, was dazugehört: In einem Telefonbuch sucht man einen Namen und will die Nummer. Mit dem, was Sie bisher kennen, braucht das zwei Arrays, eines für die Namen und eines für die Nummern. Was zusammengehört, steht an derselben Stelle.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"Office", "Dominik", "Bittle"};
    string numbers[] = {"+49-951-863-2795", "+49-951-863-2661", "+49-951-863-2661"};

    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(names[i], name) == 0)
        {
            printf("Gefunden: %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Nicht gefunden\n");
    return 1;
}

• Die Telefonnummern sind Strings und keine Zahlen: Sie enthalten + und -, eine führende 0 ginge bei einem int verloren, und rechnen will mit ihnen niemand.

• In C können Sie eigene Datentypen anlegen, die mehrere Werte zusammenfassen. Für das Telefonbuch ist das eine person mit einem Namen und einer Nummer:

  typedef struct
  {
      string name;
      string number;
  }
  person;

  struct heißt: ein Datentyp, der aus mehreren Feldern (englisch members) besteht, hier name und number. typedef gibt ihm einen Namen, person. Diese Zeilen stehen oben in der Datei, vor main. Danach ist person ein Typ wie int oder string: Sie können Variablen und Arrays davon anlegen.

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[3];

    people[0].name = "Office";
    people[0].number = "+49-951-863-2795";

    people[1].name = "Dominik";
    people[1].number = "+49-951-863-2661";

    people[2].name = "Bittle";
    people[2].number = "+49-951-863-2661";

    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(people[i].name, name) == 0)
        {
            printf("Gefunden: %s\n", people[i].number);
            return 0;
        }
    }
    printf("Nicht gefunden\n");
    return 1;
}

• person people[3]; legt ein Array aus drei Personen an. Auf die Felder greifen Sie mit der Punktschreibweise zu: people[0].name ist der Name der Person an Stelle 0, people[0].number ihre Nummer.
• Jetzt gehören Name und Nummer zusammen. Wer people sortiert, verschiebt immer ganze Personen, und die Nummer wandert mit.
• Ein struct lässt sich leicht erweitern: Ein weiteres Feld (etwa eine E-Mail-Adresse) kommt in die Definition, der Rest des Programms bleibt, wie er ist.

#include <cs50.h>
#include <stdio.h>

typedef struct
{
    string titel;
    string kuenstler;
    int jahr;
}
song;

int main(void)
{
    song playlist[3];

    playlist[0].titel = "Bohemian Rhapsody";
    playlist[0].kuenstler = "Queen";
    playlist[0].jahr = 1975;

    playlist[1].titel = "Flowers";
    playlist[1].kuenstler = "Miley Cyrus";
    playlist[1].jahr = 2023;

    playlist[2].titel = "Blinding Lights";
    playlist[2].kuenstler = "The Weeknd";
    playlist[2].jahr = 2019;

    for (int i = 0; i < 3; i++)
    {
        if (playlist[i].jahr > 2020)
        {
            printf("%s\n", playlist[i].titel);
        }
    }
}

• Das Programm gibt nur eine Zeile aus, Flowers: Nur dieser Song ist nach 2020 erschienen.