Daten, Datenstrukturen und Algorithmen und warum die Geschwindigkeit von ihnen abhängt

Alles besteht aus Bits

Computer speichern alles als Bits: Binärziffern, die entweder 0 oder 1 sind. Physisch kann ein Bit eine winzige elektrische Ladung sein, ein magnetischer Bereich auf einer Festplatte oder ein Lichtimpuls in einer Glasfaser, aber für Software ist es einfach einer von zwei Werten. Acht Bits ergeben ein Byte, das 2⁸ = 256 verschiedene Muster aufnehmen kann, von 00000000 bis 11111111.

Die Größen bauen darauf auf. Ein Kilobyte sind etwa tausend Bytes, ein Megabyte etwa eine Million, ein Gigabyte etwa eine Milliarde und ein Terabyte etwa eine Billion. (Streng genommen bedeuten die Standardpräfixe Kilo, Mega und Giga Potenzen von 1000; Speicher wird oft in Potenzen von 1024 gemessen, wofür es die Einheiten Kibibyte, Mebibyte und Gibibyte gibt. Der Unterschied spielt für den Entwurf selten eine Rolle, erklärt aber, warum eine „1 TB“-Festplatte in manchen Dateimanagern weniger anzeigt.) Eine Seite reiner Text umfasst ein paar Kilobyte, ein Handyfoto ein paar Megabyte, eine Stunde HD-Video ein paar Gigabyte.

Für sich genommen bedeuten Bits nichts. Das Muster 01000001 könnte die Zahl 65 sein, der Buchstabe A, Teil einer Farbe in einem Foto oder Teil einer Anweisung für die CPU. Bedeutung erhalten Bits erst durch die Vereinbarung, wie sie zu lesen sind, und genau das ist die Idee eines Datentyps.

Datentypen: Zahlen, Text und wahr oder falsch

Ein Datentyp sagt einem Programm, welche Art von Wert ein Datenelement ist und welche Operationen daher sinnvoll sind. Jede Programmiersprache hat einige Grundtypen, und die von Python sind typisch.

Ganzzahlen (Integers) sind ganze Zahlen wie 3, 0 oder -42 und dienen zum Zählen: Artikel in einem Warenkorb, Sitze in einem Flug. Gleitkommazahlen (Floats) wie 12,5 oder 0,2 stellen Dezimalzahlen näherungsweise im Binärsystem dar. Weil viele Dezimalzahlen keine exakte binäre Form haben, ergibt 0.1 + 0.2 in Python 0.30000000000000004. Für Physik und Grafik ist das in Ordnung, für Geld aber falsch, weshalb Finanzsysteme Beträge als ganze Zahlen in Pence oder Cent speichern oder einen Dezimaltyp verwenden (Python hat decimal.Decimal). Boolesche Werte (Booleans) haben nur zwei Werte, True und False, und halten Ja-Nein-Fakten fest wie „Ist diese Bestellung bezahlt?“. Strings sind Text, etwa der Name eines Kunden. Reale Systeme fügen weitere Typen hinzu: Datum und Uhrzeit, Geldbeträge und Binärdaten wie Bilder.

Typen sind über ein einzelnes Programm hinaus wichtig. Wenn zwei Systeme Daten austauschen, müssen sie sich auf Typen ebenso einigen wie auf Werte: Ist eine Postleitzahl eine Zahl oder Text (Text: Manche beginnen mit Buchstaben, und manche numerischen Codes beginnen mit einer Null)? Steht ein Datum in der Reihenfolge Tag-Monat oder Monat-Tag, und in welcher Zeitzone? Viele teure Integrationsfehler sind Unstimmigkeiten bei Typen.

Text und UTF-8

Text wird gespeichert, indem jedes Zeichen eine Nummer erhält und diese Nummern dann als Bytes abgelegt werden. Der internationale Standard Unicode weist weit über hunderttausend Zeichen aus den Schriftsystemen der Welt, dazu Symbolen und Emojis, jeweils eine Nummer zu, einen sogenannten Codepunkt. Eine Codierung legt dann fest, wie diese Nummern zu Bytes werden. Die heute vorherrschende Codierung, im Web und in den meisten neuen Systemen, ist UTF-8.

UTF-8 verwendet eine variable Anzahl von Bytes pro Zeichen: ein Byte für die englischen Grundbuchstaben, Ziffern und Satzzeichen (sodass Text, der nur diese Zeichen verwendet, in UTF-8 Byte für Byte identisch mit der viel älteren ASCII-Codierung ist), zwei Bytes für Zeichen wie é, drei für Zeichen wie € und die meisten chinesischen, japanischen und koreanischen Zeichen und vier für Emojis und einige seltenere Schriften. Das hat eine praktische Folge: Die Anzahl der Zeichen in einem String und die Anzahl der Bytes, die er belegt, können sich unterscheiden. Eine Datenbankspalte, die auf 50 Bytes begrenzt ist, fasst einen 50 Zeichen langen Namen in griechischer Schrift möglicherweise nicht.

Der klassische Textfehler sind verstümmelte Zeichen (zum Beispiel Café statt Café), die entstehen, wenn Bytes, die in einer Codierung geschrieben wurden, in einer anderen gelesen werden. Die Abhilfe ist einfach zu formulieren: Verwenden Sie überall UTF-8 und geben Sie dies ausdrücklich an, wann immer Text eine Grenze überquert, etwa eine Datei, eine Datenbank oder eine Netzwerknachricht.

Datenstrukturen: Arten, Daten anzuordnen

Programme haben selten mit nur einem Wert zu tun. Eine Datenstruktur ist eine Art, viele Werte im Speicher so zu organisieren, dass die benötigten Operationen schnell sind. Die richtige Wahl kann den Unterschied ausmachen zwischen einer Seite, die sofort lädt, und einer, die nie lädt. Für jede gibt es eine Analogie aus dem Alltag.

Eine Liste (in vielen Sprachen Array genannt) hält Elemente in einer Reihenfolge, wie eine nummerierte Einkaufsliste. Das fünfte Element abzurufen geht sofort, weil der Computer berechnen kann, wo es liegt. Ein Element anhand seines Werts zu finden, bedeutet dagegen, die Elemente einzeln zu prüfen. Ein Dictionary (auch Map oder Hashtabelle genannt) speichert Werte unter eindeutigen Schlüsseln, wie eine Garderobe: Geben Sie die Marke C377 ab, und Sie bekommen sofort den richtigen Mantel, ohne dass jemand alle Mäntel durchsehen muss. Ein Set ist eine Sammlung ohne Duplikate, wie eine Gästeliste, und beantwortet die Frage „Steht diese Person darauf?“ schnell.

Eine Queue (Warteschlange) funktioniert wie die Schlange am Postschalter: Wer zuerst kommt, wird zuerst bedient. Systeme nutzen Queues für Arbeit, die darauf wartet, erledigt zu werden, etwa Bestellungen, die auf die Küche warten. Ein Stack (Stapel) funktioniert wie ein Tellerstapel: Was zuletzt kommt, geht zuerst. Die Zurück-Schaltfläche Ihres Browsers verwendet einen: Die zuletzt besuchte Seite ist die erste, zu der Sie zurückkehren. Ein Baum hat eine einzige Wurzel mit Zweigen darunter, wie ein Stammbaum oder die Ordner auf Ihrem Computer; Bäume sind auch das Mittel, mit dem Datenbanken Daten für eine schnelle Suche sortiert halten. Ein Graph besteht aus Elementen (Knoten), die durch Verbindungen (Kanten) in beliebigem Muster verknüpft sind, wie eine Straßenkarte oder ein soziales Netzwerk, und beantwortet Fragen wie „Was ist der kürzeste Weg?“ oder „Wer sind Freunde von Freunden?“.

basket = ["pizza", "cola", "pizza"]            # list: ordered, duplicates allowed
print(basket[0])                                # by position: "pizza"

customers = {"C102": "Ana", "C377": "Chen"}      # dictionary: key to value
print(customers["C377"])                        # by key: "Chen"

voted = {"ana@example.com", "ben@example.com"}   # set: no duplicates
print("ana@example.com" in voted)              # True

from collections import deque
kitchen = deque(["order 1", "order 2"])         # queue
kitchen.append("order 3")                       # joins at the back
print(kitchen.popleft())                        # served first: "order 1"

Algorithmen

Ein Algorithmus ist eine präzise, schrittweise Methode zur Lösung eines Problems, die immer zu einem Ende kommt: wie ein Rezept, aber ohne Interpretationsspielraum. Eine Namensliste sortieren, die kürzeste Route zwischen zwei Adressen finden, prüfen, ob ein Passwort übereinstimmt, und entscheiden, welche Werbung angezeigt wird: All das erledigen Algorithmen.

Für dasselbe Problem gibt es meist mehr als einen Algorithmus, und sie können sich enorm darin unterscheiden, wie viel Arbeit sie leisten. Denken Sie an die Suche nach einem Namen in einem gedruckten Telefonbuch. Sie könnten auf Seite eins beginnen und jeden Eintrag lesen, bis Sie ihn finden: korrekt, aber langsam. Oder Sie schlagen das Buch in der Mitte auf, prüfen, ob der Name vor oder nach dieser Seite kommt, verwerfen die Hälfte, die ihn nicht enthalten kann, und wiederholen das. Weil das Telefonbuch sortiert ist, halbiert jeder Blick die verbleibenden Seiten. Diese zweite Methode heißt binäre Suche, und bei einem Telefonbuch mit einer Million Namen braucht sie etwa 20 Blicke statt bis zu einer Million.

O-Notation: wie der Aufwand mit den Daten wächst

Fachleute beschreiben, wie die Kosten eines Algorithmus wachsen, mit der O-Notation (Big-O). Sie sieht von der genauen Zeit auf einem bestimmten Rechner ab und stellt nur eine Frage: Wenn die Datenmenge, genannt n, zehn- oder tausendmal größer wird, wie viel mehr Arbeit fällt dann an? Sie beschreibt den ungünstigsten Fall, sofern nichts anderes gesagt wird, und ignoriert konstante Faktoren, was zugleich ihre Stärke ist (sie erfasst die Form des Wachstums) und ihre Schwäche (zwei O(n)-Algorithmen können sich in der Praxis trotzdem um den Faktor zehn unterscheiden).

O(1), konstante Zeit: Der Aufwand hängt nicht von n ab. Einen Schlüssel in einem Dictionary nachzuschlagen ist im Durchschnitt O(1). O(log n), logarithmisch: Der Aufwand wächst um einen Schritt, wann immer sich n verdoppelt, wie bei der binären Suche. O(n), linear: doppelte Daten, doppelter Aufwand, wie beim Durchsuchen einer Liste. O(n log n): etwas schlechter als linear; gute Allzweck-Sortieralgorithmen arbeiten in dieser Größenordnung. O(n²), quadratisch: doppelte Daten, vierfacher Aufwand. Das tritt typischerweise auf, wenn ein Programm für jedes Element über alle anderen Elemente läuft, etwa wenn es jeden Kunden mit jedem anderen Kunden vergleicht, um Duplikate zu finden.

Lesen Sie die letzte Spalte genau. Bei einer Milliarde einfacher Schritte pro Sekunde braucht ein Algorithmus mit einer Million zum Quadrat eine Billion Schritte: etwa eine Viertelstunde reiner Rechenzeit und in der Praxis weit länger. Dieselbe Aufgabe mit einer O(n log n)-Methode dauert einen kleinen Bruchteil einer Sekunde. Code, der im Test mit 1000 Kunden gut aussah, kann bei einer Million zum Stillstand kommen, und keine noch so große Menge zusätzlicher Hardware rettet einen quadratischen Algorithmus auf Dauer.

Platz gegen Zeit

Das Dictionary im ausgearbeiteten Beispiel ist schneller, weil es zusätzlichen Speicher nutzt, um die Daten im Voraus zu organisieren. Das ist eine der häufigsten Abwägungen in der Informatik: Oft lässt sich Geschwindigkeit mit Platz erkaufen oder Platz sparen, indem man Zeit aufwendet.

Ein Index sind zusätzliche Daten neben den Hauptdaten, die eine bestimmte Art von Frage schnell beantworten, wie das Stichwortverzeichnis hinten in einem Buch. Er beschleunigt Lesezugriffe, belegt aber Speicher und muss bei jedem Schreibvorgang aktualisiert werden, sodass das Einfügen in eine Tabelle mit zehn Indizes langsam ist. Ein Cache hält eine Kopie der Antwort auf eine aufwendige Frage an einem schnellen Ort bereit, etwa im Arbeitsspeicher, sodass die nächste Person, die fragt, sie sofort erhält. Caches sind der Grund, warum eine beliebte Produktseite schnell lädt, selbst wenn die Datenbank dahinter ausgelastet ist, aber sie werfen eine schwierige Frage auf: Wenn sich die zugrunde liegenden Daten ändern, wie schnell muss sich die Kopie mitändern? Ein paar Sekunden lang einen veralteten Preis anzuzeigen, mag akzeptabel sein; einen veralteten Kontostand anzuzeigen, möglicherweise nicht.

Kompression ist der umgekehrte Tausch: CPU-Zeit aufwenden, um Daten in weniger Bytes zu pressen, was Speicher und Übertragungszeit im Netzwerk spart.

Warum das für die Architektur wichtig ist

Architekten schreiben selten Sortieralgorithmen, treffen aber ständig Entscheidungen, deren Folgen genau diese sind. Welche Fragen muss das System schnell beantworten, und haben die Daten die Indizes, um sie zu beantworten? Wie groß werden die Daten in drei Jahren sein, und welche Teile des Entwurfs wachsen dabei linear oder schlechter? Wo lohnt sich Caching trotz seiner Komplexität, und wie veraltet dürfen gecachte Daten sein? Welche Komponente bricht zuerst, wenn das Datenvolumen um das Zehnfache wächst?

Das sind Fragen zu Performance und Skalierbarkeit, die Kapitel 2 präzisiert, sowie zu Caching und zur Wahl der Datenbank, die Kapitel 7 ausführlich behandelt. Der nächste Abschnitt wendet sich von den Daten dem Code zu und der Frage, wie Code organisiert wird, damit Menschen ihn verstehen und ändern können.