Dies ist eine alte Version des Dokuments!
Ein häufig auftretendes Problem ist es, die größte Differenz zwischen zwei beliebigen Elementen einer Menge zu finden. Bei großen Datenmengen ist es umso wichtiger, diese Operation so effizient wie möglich zu implementieren. Eine äußerst effiziente Methode bietet die Lösung des Problems über die kumulative Summe.
Als kumulierte Summe einer Zahlenfolge bezeichnet man die einfache Addition der einzelnen Zahlen. Dabei wird jede Zahl zur vorhergehenden Summe addiert.
Wir können die Berechnung allgemein so darstellen: si = si-1 + xi
Um diese Definition zu verdeutlichen, berechnen wir für zufällig gewählte Zahlen die kumulierten Summe:
Zahlen | 3 | 7 | 12 | 4 | -6 | 2 | -4 |
---|---|---|---|---|---|---|---|
Kumulierte Summe | 3 | 10 | 22 | 26 | 20 | 22 | 18 |
Noch einmal der Rechenvorgang aufgelistet:
Index (i) | Zahl (x) | Summe (s) | Berechnung |
---|---|---|---|
1 | 3 | 3 | 0 + 3 |
2 | 7 | 10 | 3 + 7 |
3 | 12 | 22 | 10 + 12 |
4 | 4 | 26 | 22 + 4 |
5 | -6 | 20 | 26 - 6 |
6 | 2 | 22 | 20 + 2 |
7 | -4 | 18 | 22 - 4 |
Jetzt wissen wir was die kumulative Summe ist und wie wir sie berechnen. Sehen wir uns nun ein paar Beispiele an, die wir über diese Berechnung lösen bzw. optimieren können.
Um mit Aktien einen möglichst hohen Gewinn zu erzielen, muss der Verkaufspreis einen möglichst großen Unterschied (der natürlich positiv sein muss) zum Einkaufspreis aufweisen. Diese Aufgabe ist nicht so trivial wie sie anfangs vielleicht aussieht, denn die beste Lösung ist nicht immer der niedrigste (Einkauf) und der höchste Preis (Verkauf) über den gesamten Zeitraum. Es muss dabei auch die Reihenfolge der Kurspositionen berücksichtigt werden.
Wir nehmen an, dass wir Vorhersagen zu künftigen Aktienkursen haben und den optimalen Einkaufs- und Verkaufszeitpunkt, sowie die jeweiligen Preise bestimmen wollen.
Als Eingabe bekommen wir den Kurs einer Aktie in einem Zeitintervall. Dieses Intervall kann beliebig groß sein und wird in diesem Beispiel vernachlässigt.
Wir haben also folgende Eingabegrößen:
Variable | Wert |
---|---|
Anzahl an Kursen (n) | 8 |
Danach folgen n Kurse:
Index (i) | Kurs (k) |
---|---|
1 | 11 |
2 | 13 |
3 | 4 |
4 | 6 |
5 | 10 |
6 | 5 |
7 | 11 |
8 | 9 |
In unseren Test-Programmen werden die Daten über die Standardeingabe nach folgendem Format geliefert:
n k_1 ... k_n
Bzw. in ausgeschriebener Form:
8 11 13 4 6 10 5 11 9
Wie es für Aktienkurse üblich ist, können wir sie auch mit einem Diagramm darstellen:
Eine Möglichkeit die maximale Differenz zu finden, wäre die Berechnung der Differenzen zu allen nachfolgenden Kursen, aus denen man anschließend das Maximum auswählt.
#include <stdio.h> #include <stdlib.h> // Maximum an eingegebenen Kurspositionen const int MAX_POSITIONS = 1000000; // Puffer für Eingaben const int BUFFER_SIZE = 12; int main() { // Puffer für Eingaben char buffer[BUFFER_SIZE]; // Zählvariablen für Schleifen int i, j; // Anzahl der Kurspositionen int n; // Werte der einzelnen Kursposition int v[MAX_POSITIONS]; // Index des minimalen Wertes (optimaler Einkauf) int minIndex = -1; // Index des maximalen Wertes (optimaler Verkauf) int maxIndex = -1; // Anzahl an Kursen einlesen fgets(buffer, BUFFER_SIZE, stdin); n = atoi(buffer); if (n < 1 || n > MAX_POSITIONS) { printf("Anzahl der Kursposition muss zwischen 1 und %d liegen\n", MAX_POSITIONS); return 1; } // Kurse einlesen for( i = 0; i < n; i++ ) { fgets(buffer, BUFFER_SIZE, stdin); v[i] = atoi(buffer); } // Über alle Kurse iterieren for( i = 0; i < n; i++ ) { // Differenz zu allen darauffolgenden Kursen bilden. // Ist das der erste Durchlauf (minIndex == -1) oder // die Differenz größer als das bisherige Maximum, // werden die bisherigen Indizes überschrieben. for( j = i + 1; j < n; j++ ) { if( minIndex == -1 || v[j] - v[i] > v[maxIndex] - v[minIndex] ) { maxIndex = j; minIndex = i; } } } // Ergebnis ausgeben if( minIndex != -1 ) printf( "Minimum bei Zeiteinheit: %d; Minimaler Wert: %d\n" "Maximum bei Zeiteinheit: %d; Maximaler Wert: %d\n" "Gewinn: %d\n", minIndex + 1, v[minIndex], maxIndex + 1, v[maxIndex], v[maxIndex] - v[minIndex] ); return 0; }
Aufruf:
$ ./squared_stock_prices < input.txt
Ausgabe:
Minimum bei Zeiteinheit: 3; Minimaler Wert: 4 Maximum bei Zeiteinheit: 7; Maximaler Wert: 11 Gewinn: 7
Die optimale Strategie im angegebenen Zeitintervall ist also im 3. Zeitintervall zu kaufen und im 7. zu verkaufen. Dabei erhalten wir einen Gewinn von 7 pro Aktie.
Sehen wir uns nun die Anzahl der für die Berechnung notwendigen Schritte an. Folgende beiden Schleifen sind für die Berechnung der kumulativen Summe verantwortlich:
// Über alle Kurse iterieren for( i = 0; i < n; i++ ) { // Differenz zu allen darauffolgenden Kursen bilden. // Ist das der erste Durchlauf (minIndex == -1) oder // die Differenz größer als das bisherige Maximum, // werden die bisherigen Indizes überschrieben. for( j = i + 1; j < n; j++ ) { if( minIndex == -1 || v[j] - v[i] > v[maxIndex] - v[minIndex] ) { maxIndex = j; minIndex = i; } } }
Wir haben zwei Schleifen, die jeweils einen Zähler gegen n
laufen lassen. Die äußere Schleife startet bei 0, hat also genau n
Iterationen.
In der inneren Schleife starten wir bei i + 1
, die Anzahl der Schritte ist somit von der äußeren Schleife abhängig. Der aufwendigste Fall mit den meisten Schritten ist der allererste, bei dem i
den Wert 0 hat und die innere Schleife bei 1 startet. In diesem Fall hat die innere Schleife n - 1
Schritte. Nachdem wir nur eine grobe Schätzung wollen, lassen wir den konstanten Wert weg und runden das Ergebnis einfach auf n
. Nun haben wir für jeden der n
Durchläufe der äußeren Schleife auch n
Durchläufe in der inneren Schleife. Es ergibt sich ein von der Anzahl an Kursen n
abhängiger quadratischer Aufwand. In Kurzschreibweise bedeutet das: O(n2)
Die obrige Lösung funktioniert in unserem Beispiel ganz gut. Aber was ist, wenn wir nicht 8 sondern ein paar Millionen Kurspositionen haben? Versuchen wir eine bessere Lösung mit der kumulativen Summe zu finden.
Gehen wir von der ersten Kursposition aus und addieren alle Kursdifferenzen dazu, erhalten wir immer den aktuellen Kurs. Wenn wir uns jetzt das Minimum merken und immer die Differenz zum aktuellen Kurs bilden, können wir in linearem Aufwand das gesuchte Ergebnis finden.
#include <stdio.h> #include <stdlib.h> #include <limits.h> // Maximum an eingegebenen Kurspositionen const int MAX_POSITIONS = 1000000; // Puffer für Eingaben const int BUFFER_SIZE = 12; int main() { // Puffer für Eingaben char buffer[BUFFER_SIZE]; // Anzahl der Kurspositionen int n; // Index des minimalen Wertes (optimaler Einkauf) int minIndex = 0; // Index des maximalen Wertes (optimaler Verkauf) int maxIndex = -1; // Minimaler Wert (Einkaufspreis) int min; // Maximale Kursdifferenz (Verkaufspreis) int maxDiff = INT_MIN; // Aktuelle Summe aller Kursänderungen. Dadurch enthält // diese Variable auch immer den aktuellen Kurs. long sum; // Aktueller Aktienkurs int currentPrice; // Vorheriger Aktienkurs int oldPrice; // Anzahl an Kursen einlesen fgets(buffer, BUFFER_SIZE, stdin); n = atoi(buffer); if (n < 1 || n > MAX_POSITIONS) { printf("Anzahl der Kursposition muss zwischen 1 und %d liegen\n", MAX_POSITIONS); return 1; } // 1. Kurs einlesen und als bisherige Summe festlegen. fgets(buffer, BUFFER_SIZE, stdin); currentPrice = atoi(buffer); sum = min = oldPrice = currentPrice; // Alle Aktienkurse einlesen und Ergebnis berechnen int i; for( i = 1; i < n; i++ ) { // Aktuellen Kurs einlesen fgets(buffer, BUFFER_SIZE, stdin); currentPrice = atoi(buffer); // Wir summieren die Kursänderungen auf. sum += currentPrice - oldPrice; // Ist der Kurs kleiner als das bisherige Minimum, wird // die aktuelle Kursposition als neues Minimum gespeichert. if( sum < min ) { min = sum; minIndex = i; } // Ist der Kursunterschied zwischen dem bisherigen minimalen und // dem aktuellen Kurs größer als das bisherige Maximum, wird // die aktuelle Kursposition als neues Maximum gespeichert. if( sum - min > maxDiff ) { maxDiff = sum - min; maxIndex = i; } // Wir speichern den aktuellen Kurs für den nächsten Durchlauf als // alten Kurs. oldPrice = currentPrice; } // Ergebnis ausgeben. printf( "Minimum bei Zeiteinheit: %d; Minimaler Wert: %d\n" "Maximum bei Zeiteinheit: %d; Maximaler Wert: %d\n" "Gewinn: %d\n", minIndex + 1, min, maxIndex + 1, maxDiff + min, maxDiff ); return 0; }
Aufruf:
$ ./linear_stock_prices < input.txt
Ausgabe:
Minimum bei Zeiteinheit: 3; Minimaler Wert: 4 Maximum bei Zeiteinheit: 7; Maximaler Wert: 11 Gewinn: 7
In dieser Version haben wir nicht nur den rechnerischen Aufwand von O(n2) auf O(n) verringert, wir ersparen uns sogar ein Array mit den gesamten Daten.
Nachfolgend wollen wir einen einfachen Performance-Vergleich zwischen den beiden Implementierungen durchführen. Es ist zu beachten, dass dies kein vollständiger und statistisch zuverlässiger Benchmark ist. Vielmehr soll der Sinn hinter dieser Art von Optimierung demonstriert werden.
Für einen sinnvollen Vergleich sind große Datenmengen erforderlich. Um die entsprechenden Eingabedaten zu generieren, wird ein Python-Skript verwendet:
#!/usr/bin/env python3 import random import sys n = int(sys.argv[1]) lower_bound = int(sys.argv[2]) upper_bound = int(sys.argv[3]) print(n) for i in range(n): print(random.randint(lower_bound, upper_bound))
Nun erzeugen wir 1 Million Kurspositionen zwischen 0 und 1000. Aufruf:
$ ./generate.py 1000000 0 1000 > large_input.txt
Beide Implementierungen werden auf höchster Optimierungsstufe kompiliert:
$ gcc -O3 squared_stock_prices.c -o squared_stock_prices $ gcc -O3 linear_stock_prices.c -o linear_stock_prices
Starten wir die Berechnung für die quadratische Lösung:
$ time ./squared_stock_prices < large_input.txt Minimum bei Zeiteinheit: 1227; Minimaler Wert: 0 Maximum bei Zeiteinheit: 5013; Maximaler Wert: 1000 Gewinn: 1000 ./squared_stock_prices < large_input.txt 1557.53s user 0.18s system 99% cpu 26:03.02 total
In diesem Fall dauerte der Durchlauf über 26 Minuten. Zum Vergleich die lineare Lösung:
$ time ./linear_stock_prices < large_input.txt Minimum bei Zeiteinheit: 1227; Minimaler Wert: 0 Maximum bei Zeiteinheit: 5013; Maximaler Wert: 1000 Gewinn: 1000 ./linear_stock_prices < large_input.txt 0.06s user 0.00s system 98% cpu 0.061 total
Die optimierte Lösung benötigte für das gleiche Ergebnis 0.06 Sekunden! Natürlich werden bei diesem Vergleich einige wesentliche Dinge vernachlässigt, wie etwa die verwendete Hardware oder Caches. Das Ergebnis ist trotzdem relativ eindeutig.
Wir haben ein quadratisches Grundstück, auf das wir ein Haus bauen möchten. Dieses Grundstück ist jetzt aber keine komplett leere Fläche, sondern beinhaltet auch Hindernisse wie zum Beispiel Bäume. Da wir diese nur ungern fällen möchten, suchen wir eine möglichst große rechteckige Teilfläche, auf der wir unser Haus platzieren können, ohne ein Hindernis zu entfernen.
Zuerst bekommen wir die Seitenlänge der quadratischen Fläche als Eingabe:
Variable | Wert |
---|---|
Seitenlänge (s) | 7 |
Danach folgt die Anzahl der Hindernisse, die sich auf der Fläche befinden:
Variable | Wert |
---|---|
Anzahl der Hindernisse (n) | 5 |
Im Anschluss folgen noch die Koordinaten der Hindernisse (Koordinaten: 1 ⇐ x, y ⇐ s):
x-Koordinate | y-Koordinate |
---|---|
2 | 3 |
4 | 2 |
4 | 6 |
7 | 8 |
7 | 4 |
Zeichnen wir uns diese Matrix auf, erhalten wir folgendes Ergebnis:
In der Grafik steht die Farbe Grün für freie Felder und Schwarz für belegte Felder. Wir suchen nun den größten rechteckigen Block aus grünen Feldern. Dabei interessieren uns natürlich Koordinaten und Breite bzw. Höhe des Rechtecks.
Ein relativ einfaches, aber sehr aufwendiges Verfahren ist es, alle möglichen Felder durchzuprobieren. Dabei geht man alle einzelnen Koordinaten durch und sucht für alle davon ausgehenden Breiten und Höhen das größte freie Feld. Eine Implementierung könnte so aussehen:
#include <stdio.h> char area[1001][1001]; // Test-Daten const char testData[] = { 7, 5, // s, n 3, 2, // y1, x1 2, 4, // y2, x2 6, 4, // y3, x3 4, 6, // y4, x4 7, 6 }; // y5, x5 // Gibt das nächste Element in den Test-Daten zurück int getNext() { static int i = 0; return testData[i++]; } int main( int argc, char *argv[] ) { // Größe des Quadrates abfragen int s = getNext(); // Anzahl an Hindernissen abfragen int n = getNext(); // Noch keine passende Fläche gefunden, deshalb mit -1 vorbelegt int x = -1, y = -1, maxW = -1, maxH = -1; // Schleifenzähler int i, j, k, l, a, b; // Gibt an, ob ein Block frei von Hindernissen ist int isFree; // Hindernisse einlesen und im Array kennzeichnen for( i = 0; i < n; i++ ) area[getNext()][getNext()] = 1; // Durch alle Zeilen iterieren (y-Koordinate) for( j = 1; j <= s; j++ ) { // Durch alle Spalten iterieren (x-Koordinate) for( i = 1; i <= s; i++ ) { // Alle möglichen Breiten versuchen, beginnend bei der größten for( k = s; k >= i; k-- ) { // Alle möglichen Höhen versuchen, beginnend bei der größten for( l = s; l >= j; l-- ) { // Prüfen, ob das Feld leer ist isFree = 1; for( a = i; a <= k && isFree; a++ ) { for( b = j; b <= l && isFree; b++ ) { if( area[b][a] ) isFree = 0; } } // Feld ist leer if( isFree ) { // Prüfen, ob das neue Feld größer ist als das bisher // größte gefundene. Gegebenenfalls Koordinaten und // Größe speichern int newW = k - i + 1; int newH = l - j + 1; if( x == -1 || ( maxW * maxH ) < ( newW * newH ) ) { x = i; y = j; maxW = newW; maxH = newH; } } } } } } // Ergebnis ausgeben printf( "x: %d y: %d w: %d h: %d\n", x, y, maxW, maxH ); return 0; }
Ausgabe:
x: 1 y: 4 w: 3 h: 4
Wir bekommen also folgende gelb markierte Fläche als Ergebnis:
Das Ergebnis sieht schon mal sehr gut aus. Aber am Code fällt sofort die Verschachtelung von 6 Schleifen auf. Wir haben hier also einen Algorithmus der Ordnung O(n6), der sehr schnell anwächst.
Hinweis: In der Implementierung wurde der Index 0 im Array vernachlässigt. Das verschwendet zwar Speicher, hat aber einen Grund, den wir im nächsten Abschnitt näher betrachten werden.
So können wir unser Programm aber nicht einfach stehen lassen. Es liefert zwar die richtige Lösung, die Berechnung ist aber sehr aufwendig.
skizzen, erklärung