====== Summierung von Aktienpositionen ======
===== Problemstellung =====
In unserem Beispiel verwalten wir eine größere Menge an Aktienpositionen. Diese Positionen haben jeweils einen Wert zugewiesen. Nun wollen wir für eine aufeinanderfolgende Gruppe an Aktienpositionen den Gesamtwert abfragen.

===== Eingabe =====
Als Eingabe bekommen wir die Anzahl an Aktien, deren Werte, die Anzahl an Abfragen sowie die Abfragen selbst.

Sehen wir uns ein Beispiel an:

^ Variable                   ^ Wert  ^
| Anzahl an Aktienpositionen | 5     |
| Anzahl an Abfragen         | 3     |

Danach folgen die entsprechenden Werte:
^ Index ^ Wert ^
| 0     | 8    |
| 1     | 13   |
| 2     | 4    |
| 3     | 6    |
| 4     | 10   |

Und schlussendlich die Abfragen:
^ Index ^ Start-Index ^ End-Index ^
| 0     | 1           | 2         |
| 1     | 0           | 4         |
| 2     | 4           | 4         |

In unseren Test-Programmen werden die Daten über die Standardeingabe eingelesen.

Bzw. in ausgeschriebener Form:
<code text stocks_example_input.txt>
5
8
13
4
6
10
3
1 2
0 4
4 4
</code>

===== Quadratische Lösung =====
Eine Möglichkeit eine Abfrage zu beantworten ist, jedes Mal über die entsprechenden Aktienwerte zu iterieren und diese zu addieren.

<code c squared_stock_prices.c>
#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Anzahl an Aktien einlesen
    int num_stocks;
    scanf("%d", &num_stocks);

    if (num_stocks < 1)
    {
        printf("Anzahl der Aktienpositionen muss mindestens 1 sein.\n");
        return 1;
    }

    // Werte einlesen
    int *prices = (int *)malloc(num_stocks * sizeof(int));
    for (int i = 0; i < num_stocks; i++)
        scanf("%d", &(prices[i]));

    // Anzahl an Abfragen einlesen
    int num_queries;
    scanf("%d", &num_queries);

    if (num_queries < 1)
    {
        printf("Anzahl der Abfragen muss mindestens 1 sein.\n");
        return 1;
    }

    // Abfragen einlesen
    int *queries = (int *)malloc(num_queries * 2 * sizeof(int));
    for (int i = 0; i < num_queries; i++)
    {
        scanf("%d %d", &(queries[i * 2]), &(queries[i * 2 + 1]));
        if (queries[i * 2] > queries[i * 2 + 1])
        {
            printf("Ungültige Abfrage\n");
            return 1;
        }
    }

    // Alle Abfragen berechnen
    long total_sum = 0;
    for (int i = 0; i < num_queries; i++)
    {
        long query_sum = 0;
        for (int price_index = queries[i * 2]; price_index <= queries[i * 2 + 1]; price_index++)
            query_sum += prices[price_index];
        total_sum += query_sum;
    }

    // Ergebnis ausgeben
    printf("Gesamtsumme: %ld\n", total_sum);

    free(queries);
    free(prices);
    return 0;
}
</code>

Aufruf:
  $ ./squared_stock_prices < stocks_example_input.txt
Ausgabe:
  Gesamtsumme: 68

Sehen wir uns nun die Anzahl der für die Berechnung notwendigen Schritte an. Folgende beiden Schleifen sind für die Berechnung der Summe verantwortlich:
<code c>
    for (int i = 0; i < num_queries; i++)
    {
        long query_sum = 0;
        for (int price_index = queries[i * 2]; price_index <= queries[i * 2 + 1]; price_index++)
            query_sum += prices[price_index];
        total_sum += query_sum;
    }
</code>

Die äußere Schleife startet bei 0 und läuft gegen ''num_queries'', hat also genau ''num_queries'' Iterationen.

In der inneren Schleife iterieren wir über den abgefragten Bereich. Der aufwendigste Fall mit den meisten Schritten ist also jener, bei dem wir alle vorhandenen Werte aufsummieren. In diesem Fall hat die innere Schleife ''num_stocks'' Schritte. Nun haben wir für jeden der ''num_queries'' Durchläufe der äußeren Schleife im schlimmsten Fall ''num_stocks'' Durchläufe in der inneren Schleife. In Kurzschreibweise bedeutet das: **''O(num_stocks * num_queries)''**

Gehen wir davon aus, dass sich ''num_stocks'' und ''num_queries'' in der gleichen Größenordnung befinden, können wir diese Implementierung überschlagsmäßig als quadratisch bezeichnen.

===== Lineare Lösung =====
Die obenstehende Lösung funktioniert in unserem Beispiel ganz gut. Aber was ist, wenn wir nicht fünf sondern ein paar Millionen Kurspositionen haben? Oder auch eine wesentlich größere Anzahl an Abfragen? Versuchen wir eine bessere Lösung mit der Präfixsumme zu finden.

Für jede Abfrage werden alle Werte im angegebenen Bereich aufsummiert. Selbst wenn die selbe Abfrage doppelt auftritt, wiederholen wir die Berechnung. Betrachten wir nun Bereichsabfragen als Teilproblem der vollständigen Summe aller Werte. Um das Ergebnis einer Bereichsabfrage zu erhalten, müssen die Summanden vor und nach dem Bereich weggelassen werden.

Folgende Tabelle enthält neben der Eingabe auch die dazugehörige Präfixsumme.

^ Index ^ Wert ^ Präfixsumme       ^
| 0     | 8    | 8                |
| 1     | 13   | 21               |
| 2     | 4    | 25               |
| 3     | 6    | 31               |
| 4     | 10   | 41               |

Als Beispiel nehmen wir die Abfrage der Indizes von 1 bis inklusive 2 an. Die Präfixsumme hat beim End-Index laut Tabelle den Wert 25. Um nachfolgende Elemente müssen wir uns an dieser Stelle nicht kümmern, diese sind in diesem Wert nicht enthalten. Vorhergehend Werte können wir über die Präfixsumme beim Index direkt vor dem abgefragten Teilbereich abziehen, in unserem Fall also bei Index 0. Wir berechnen also ''25 - 8 = 17'', die manuelle Überprüfung ''13 + 4 = 17'' bestätigt das Ergebnis.

Mit dieser Optimierung können wir die Summen für Abfragen in konstanter Zeit nutzen.

<code c linear_stock_prices.c>
#include <stdio.h>
#include <stdlib.h>

int main()
{
    // Anzahl an Aktien einlesen
    int num_stocks;
    scanf("%d", &num_stocks);

    if (num_stocks < 1)
    {
        printf("Anzahl der Aktienpositionen muss mindestens 1 sein.\n");
        return 1;
    }

    // Werte einlesen
    long *price_sums = (long *)malloc((num_stocks + 1) * sizeof(long));
    // Erstes Element überspringen, damit wir beim Aufsummieren darauf
    // zugreifen können
    price_sums[0] = 0;
    price_sums++;
    for (int i = 0; i < num_stocks; i++)
    {
        scanf("%ld", &(price_sums[i]));
        price_sums[i] += price_sums[i - 1];
    }

    // Anzahl an Abfragen einlesen
    int num_queries;
    scanf("%d", &num_queries);

    if (num_queries < 1)
    {
        printf("Anzahl der Abfragen muss mindestens 1 sein.\n");
        return 1;
    }

    // Abfragen einlesen
    int *queries = (int *)malloc(num_queries * 2 * sizeof(int));
    for (int i = 0; i < num_queries; i++)
    {
        scanf("%d %d", &(queries[i * 2]), &(queries[i * 2 + 1]));
        if (queries[i * 2] > queries[i * 2 + 1])
        {
            printf("Ungueltige Abfrage\n");
            return 1;
        }
    }

    // Alle Abfragen berechnen
    long total_sum = 0;
    for (int i = 0; i < num_queries; i++)
    {
        long query_sum = price_sums[queries[i * 2 + 1]] - price_sums[queries[i * 2] - 1];
        total_sum += query_sum;
    }

    // Ergebnis ausgeben
    printf("Gesamtsumme: %ld\n", total_sum);

    free(queries);
    free(price_sums - 1);
    return 0;
}
</code>
Aufruf:
  $ ./linear_stock_prices < stocks_example_input.txt
Ausgabe:
  Gesamtsumme: 68

Die initiale Berechnung der Präfixsumme kostet uns ''num_stocks'' Schritte. Danach berechnen wir ''num_queries'' Abfragen in konstanter Zeit. In dieser Version haben wir den rechnerischen Aufwand also von ''O(num_stocks * num_queries)'' auf **''O(num_stocks + num_queries)''** verringert.

===== Performance-Vergleich =====
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 separates Programm verwendet:
<code c stocks_cumulative_sum_generator.c>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char *argv[])
{
    if (argc != 4)
    {
        printf("Usage: %s num_stocks num_queries max_value\n", argv[0]);
        return 1;
    }

    // Der Zufallsgenerator wird mit der aktuellen Zeit initialisiert.
    srand(time(NULL));

    // Anzahl der zu generierenden Werte und Abfragen werden als
    // Kommandozeilenparameter übergeben.
    const int num_stocks = atoi(argv[1]),
              num_queries = atoi(argv[2]),
              max_value = atoi(argv[3]);

    // Anzahl der Werte sowie Werte selbst ausgeben
    printf("%d\n", num_stocks);
    // In der Schleife folgt die zufällige Generirung
    // und Ausgabe der Werte.
    for (int i = 0; i < num_stocks; i++)
        printf("%d\n", rand() % (max_value + 1));

    // Anzahl der Abfragen sowie Abfragen selbst ausgeben
    printf("%d\n", num_queries);
    // In der Schleife folgt die zufällige Generirung
    // und Ausgabe der Abfragen.
    for (int i = 0; i < num_queries; i++)
    {
        const int query_start = rand() % num_stocks;
        const int query_end = query_start + (rand() % (num_stocks - query_start));
        printf("%d %d\n", query_start, query_end);
    }

    return 0;
}
</code>

Nun erzeugen wir uns in 500.000er Schritten sechs Testfälle.
Aufruf:
  $ for s in `seq 500000 500000 3000000`; do ./stocks_cumulative_sum_generator "$s" "$s" 10 > "stocks_${s}x${s}.txt"; done

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

^ Datei                                       ^ Dauer quadratische Ausführung      ^ Dauer lineare Ausführung ^
| stocks_500000<nowiki>x</nowiki>500000.txt   |                             18,666 |                    0,114 |
| stocks_1000000<nowiki>x</nowiki>1000000.txt |                            1:16,45 |                    0,213 |
| stocks_1500000<nowiki>x</nowiki>1500000.txt |                            3:06,29 |                    0,333 |
| stocks_2000000<nowiki>x</nowiki>2000000.txt |                            6:25,36 |                    0,436 |
| stocks_2500000<nowiki>x</nowiki>2500000.txt |                           11:10,95 |                    0,552 |
| stocks_3000000<nowiki>x</nowiki>3000000.txt |                           16:25,66 |                    0,675 |

Die optimierte Lösung benötigt für das gleiche Ergebnis deutlich weniger Zeit. Natürlich werden bei diesem Vergleich einige wesentliche Dinge vernachlässigt, wie etwa die verwendete Hardware oder Caches. Das Ergebnis ist trotzdem relativ eindeutig.

===== Siehe auch =====
  * [[algo:prefix-sum:start]]
  * [[algo:prefix-sum:optimization:area]]