Sliding window-algoritmer

La oss si at vi har en liste med n tall, og at vi ønsker å finne summen av alle sammenhengende dellister med k elementer (k <= n). Brute force-løsningen er:

for (int i = 0; i < n - k + 1; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += numbers[j];
    }
    cout << sum << endl;
}

Kjøretiden er O((n – k) * k), som tilsvarer O(n^2) hvis k er proporsjonal med n. Men trenger vi å regne ut hele summen på nytt for hvert element? Summen av element 1 til k er jo det samme som summen av element 0 til k – 1, bortsett fra at vi legger til element k og fjerner element 0. Dette kan vi fortsette med videre bortover – altså vedlikeholder vi en løpende sum over et “vindu” som vi skyver bortover, og hele tiden justere den ved å trekke fra elementet som forsvinner ut og legge til elementet som rykker inn. Dette kalles en sliding window-algoritme:

// Bygg opp det initielle vinduet
int windowSum = 0;
for (int i = 0; i < k; i++)
    windowSum += numbers[i];
cout << windowSum << endl;
// Skyv vinduet bortover (i markerer starten av det nye vinduet, 
// som altså starter på element i og slutter på element i + k - 1)
for (int i = 1; i < n - k + 1) {
    windowSum += numbers[i + k - 1] - numbers[i - 1];
    cout << windowSum << endl;
}

Men hva gjør vi når informasjonen om element x har rykket ut og element y har rykket inn ikke er nok til å svare på det vi lurer på om hvert vindu? Dette skjer eksempelvis når det vi lurer på er hva som er den største verdien i vinduet. Til dette kan vi bruke en heap, også kjent som en prioritetskø (priority queue). Denne datastrukturen kommer i to utgaver. En max-heap er en struktur hvor du kan legge inn elementer i en hvilken som helst rekkefølge, og hver gang du tar ut et element, vil du få det største elementet i heapen. En min-heap vil alltid gi deg det minste elementet. Å sette inn og å ta ut fra en heap som inneholder n elementer tar O(lg n) tid. Det anbefales å studere hvordan en heap er bygd opp, men til daglig bruker vi den ferdigbygde implementasjonen i C++, som heter priority_queue og ligger i <queue>.

Tanken er altså å bruke en heap til å holde rede på elementene som til enhver tid ligger i vinduet – dermed vet vi at det største elementet i vinduet vil ligge øverst i heapen. Men hvordan skal vi fjerne elementet som skal ut hver gang vi forskyver vinduet? Det å fjerne et element (annet enn toppelementet) fra en heap er egentlig ikke så vanskelig, men det krever at man vedlikeholder en peker til elementets plassering inni heapen, slik at man ikke bruker tid på å finne ut hvor elementet befinner seg. Dette støttes ikke av priority_queue i C++. Heldigvis kan man bruke følgende triks: vi kan ganske enkelt la være å fjerne elementene etterhvert som vi forskyver vinduet, men hver gang vi henter ut det største elementet, kontrollerer vi at elementet befinner seg inni det nåværende vinduet – hvis ikke, forkaster vi det og henter ut på nytt. For raskt å kunne finne ut hvorvidt elementet vi hentet ut av heapen befinner seg inni vinduet eller ikke, registrerer vi både tallverdien og indeksen når vi legger noe inn i heapen. Fordi heap-operasjonene har kjøretid O(lg n), blir det ingen merkbar ytelsesforskjell pga. de ekstra elementene. (Tilsvarende triks kan man bruke i Dijkstras korteste vei-algoritme.)

Når vi skal ha egendefinerte structs inni en heap, er vi nødt til å fortelle heapen hvordan elementene skal sorteres – dette må gjøres ved å overloade <-operatoren (og det må gjøres etter at man har definert structen, og før resten av koden). En detalj her er at priority_queue alltid er en max-heap, så hvis du ønsker en min-heap må du implementere den slik at hvis element a er mindre enn element b, slik at du vil at a skal havne øverst, må a < b returnere false (slik at heapen tror at a er størst og dermed skal gis ut først):

#include <queue>
#include <iostream>

using namespace std;

struct Entry {
    int value;
    int index;
};

bool operator < (const Entry & a, const Entry & b) {
    if (a.value == b.value)
        return a.index < b.index;
    return a.value < b.value;
}

OPPGAVE: Implementer resten av algoritmen for å finne største verdi inni et sliding window av størrelse k ved hjelp av en heap. Heapen kan deklareres slik: priority_queue<Entry> window;. Nye elementer deklareres og legges inn slik: Entry e = {someValue, someIndex}; window.push(e);. Største element hentes ut slik: Entry e = window.top();, og slettes slik: window.pop();. Løsningen står nedenfor.

int main() {
    // Les input
    int n, k;
    cin >> n >> k;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++)
        cin >> numbers[i];
    
    // Bygg opp det initielle vinduet
    priority_queue<Entry> window;
    for (int i = 0; i < k; i++) {
        Entry entry = {numbers[i], i};
        window.push(entry);
    }
    cout << window.top().value << endl;
    // top() returnerer toppelementet uten å fjerne det, 
    // og pop() fjerner toppelementet uten å returnere det, så man trenger begge to
    
    // Skyv vinduet bortover (i er elementet som skal inn, så i - k + 1 er det første elementet i det nye vinduet)
    for (int i = k; i < n; i++) {
        Entry newEntry = {numbers[i], i};
        window.push(newEntry);
        Entry greatest;
        while (true) {
            greatest = window.top();
            if (greatest.index > i - k) // Bare avbryt løkken dersom elementet vi fikk ut er inni det nåværende vinduet
                break;
            else
                window.pop();
        }
        cout << greatest.value << endl;
    }
}

Dersom man hadde slettet elementene fra heapen med en gang de gikk ut av vinduet, ville heapen aldri ha inneholdt mer enn k elementer, og kjøretiden ville ha blitt O(n lg k). Med vår fremgangsmåte risikerer vi at heapen ender opp med å inneholde alle elementene (hvilken situasjon vil forårsake dette?), så kjøretiden blir O(n lg n), som er omtrent like bra, og mye bedre enn O(n^2).

OPPGAVE: “Pyramid” fra IOI 2006 (testdata her). I tillegg til at det er to todimensjonale sliding windows inni hverandre (som man riktignok ikke trenger en heap til, så vidt jeg husker) trenger man et ekstra triks for å få optimal kjøretid.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>