algorithm
Online-algoritmer

Anmärkningar

Sökning (cachning online)

Förord

Istället för att börja med en formell definition är målet att närma sig detta ämne via en rad exempel och införa definitioner på vägen. Anmärkningsavsnittet Teori kommer att bestå av alla definitioner, satser och förslag för att ge dig all information för att snabbare slå upp specifika aspekter.

Källorna för kommentareravsnittet består av grundmaterialet som används för detta ämne och ytterligare information för vidare läsning. Dessutom hittar du de fullständiga källkoderna för exemplen där. Var uppmärksam på att för att göra källkoden för exemplen mer läsbar och kortare avstår det från saker som felhantering osv. Det vidarebefordrar också vissa specifika språkfunktioner som skulle dölja exemplets tydlighet som omfattande användning av avancerade bibliotek etc.

personsökning

Personsökningsproblemet uppstår genom begränsningen av ändligt utrymme. Låt oss anta att vår cache C har k sidor. Nu vill vi bearbeta en sekvens av m sidförfrågningar som måste ha placerats i cachen innan de behandlas. Naturligtvis om m<=k så sätter vi bara alla element i cachen och det kommer att fungera, men vanligtvis är m>>k .

Vi säger att en begäran är en cache-hit , när sidan redan är i cache, annars kallas det en cache-miss . I så fall måste vi ta med den önskade sidan i cachen och släppa ut en annan, förutsatt att cachen är full. Målet är ett evictionschema som minimerar antalet utkastningar .

Det finns många strategier för detta problem, låt oss titta på några:

1. Först in, först ut (FIFO) : Den äldsta sidan släpps
2. Senast in, först ut (LIFO) : Den senaste sidan släpps ut
3. Minst använda nyligen (LRU) : Evict-sida vars senaste åtkomst var tidigast
4. Minst ofta använda (LFU) : Avlägsna den sida som minst begärdes
5. Längsta framsträcka (LFD) : Avlägsna sidan i cachen som inte begärs förrän längst framöver.
6. Spola när det är fullt (FWF) : rensa cacheminnet komplett så snart en cachemiss inträffade

Det finns två sätt att närma sig detta problem:

1. offline : sekvensen av sidförfrågningar är känd i förväg
2. online : sekvensen av sidförfrågningar är inte känd i förväg

Offline-strategi

För den första metoden titta på ämnet Applications of Greedy-teknik . Det är det tredje exemplet Offline Caching tar hänsyn till de första fem strategierna ovanifrån och ger dig en bra startpunkt för följande.

Exempelprogrammet förlängdes med FWF- strategin:

class FWF : public Strategy {
public:
    FWF() : Strategy("FWF")
    {
    }

    int apply(int requestIndex) override
    {
        for(int i=0; i<cacheSize; ++i)
        {
            if(cache[i] == request[requestIndex])
                return i;

            // after first empty page all others have to be empty
            else if(cache[i] == emptyPage)
                return i;
        }

        // no free pages
        return 0;
    }

    void update(int cachePos, int requestIndex, bool cacheMiss) override
    {

        // no pages free -> miss -> clear cache
        if(cacheMiss && cachePos == 0)
        {
            for(int i = 1; i < cacheSize; ++i)
                cache[i] = emptyPage;
        }
    }
};

Den fullständiga koden finns här . Om vi återanvänder exemplet från ämnet får vi följande utgång:

Strategy: FWF

Cache initial: (a,b,c)

Request cache 0 cache 1 cache 2 cache miss
  a       a       b       c
  a       a       b       c
  d       d       X       X       x
  e       d       e       X
  b       d       e       b
  b       d       e       b
  a       a       X       X       x
  c       a       c       X
  f       a       c       f
  d       d       X       X       x
  e       d       e       X
  a       d       e       a
  f       f       X       X       x
  b       f       b       X
  e       f       b       e
  c       c       X       X       x

Total cache misses: 5

Även om LFD är optimal har FWF färre cachemissningar. Men huvudmålet var att minimera antalet utkastningar och för FWF betyder fem missningar 15 utkastningar, vilket gör det till det fattigaste valet för detta exempel.

Online-strategi

Nu vill vi närma oss onlineproblemet med sökning. Men först behöver vi en förståelse för hur vi gör det. Uppenbarligen kan en online-algoritm inte vara bättre än den optimala offline-algoritmen. Men hur mycket värre är det? Vi behöver formella definitioner för att besvara den frågan:

Definition 1.1: Ett optimeringsproblem Π består av en uppsättning instanser Σ _Π . För varje instans σ∈Σ _Π finns det en uppsättning Ζ _σ av lösningar och en objektiv funktion f _σ : Ζ _σ → ℜ _≥0 som tilldelar apositivt verkligt värde till varje lösning.
Vi säger att OPT (σ) är värdet på en optimal lösning, A (σ) är lösningen för en algoritm A för problemet Π och w _A (σ) = f _σ (A (σ)) dess värde.

Definition 1.2: En online-algoritm A för ett minimeringsproblem Π har ett konkurrensförhållande av r ≥ 1 om det finns en konstant τ∈ℜ med

w _A (σ) = f _σ (A (σ)) ≤ r ⋅ OPT (σ) + τ

för alla fall σ∈Σ _Π . A kallas en r-konkurrenskraftig online-algoritm. Är jämnt

w _A (σ) ≤ r ⋅ OPT (σ)

för alla fall σ∈Σ _Π kallas A en strikt r-konkurrenskraftig online-algoritm.

Så frågan är hur konkurrenskraftig är vår online-algoritm jämfört med en optimal offline-algoritm. I sin berömda bok använde Allan Borodin och Ran El-Yaniv ett annat scenario för att beskriva situationen för onlinesökning:

Det finns en ond motståndare som känner till din algoritm och den optimala offline-algoritmen. I varje steg försöker han begära en sida som är värst för dig och samtidigt bäst för offline-algoritmen. konkurrensfaktorn i din algoritm är faktorn på hur illa din algoritm gjorde mot motståndarens optimala offline-algoritm. Om du vill försöka vara motståndaren kan du prova Adversary Game (försök att slå sidans strategier).

Markeringsalgoritmer

Istället för att analysera varje algoritm separat, låt oss titta på en speciell online-algoritmfamilj för sökningsproblemet som kallas markeringsalgoritmer .

Låt σ = (σ ₁ , ..., σ _p ) en instans för vårt problem och k vår cachestorlek än σ kan delas in i faser:

• Fas 1 är maximal efterföljande av σ från början tills maximal k olika sidor begärs
• Fas i ≥ 2 är maximal efterföljande av σ från slutet av fas i-1 tills maximal k olika sidor begärs

Till exempel med k = 3:

En markeringsalgoritm (implicit eller uttryckligen) upprätthåller om en sida är markerad eller inte. I början av varje fas är alla sidor omarkerade. Är en sida begärd under en fas som den markeras. En algoritm är en markering algoritm iff det aldrig evicts en markant sida från cache. Det betyder att sidor som används under en fas inte kommer att tas bort.

Förslag 1.3: LRU och FWF är markeringsalgoritm.

Bevis: I början av varje fas (utom den första) har FWF en cache-miss och rensat cachen. det betyder att vi har k tomma sidor. I varje fas är maximala k olika sidor begärda, så det kommer nu att bli utkast under fasen. Så FWF är en markeringsalgoritm.
Låt oss anta att LRU inte är en markeringsalgoritm. Sedan finns det en instans σ där LRU en markerad sida x i fas i evicted. Låt σ _t begäran i fas i där x väljs ut. Eftersom x är markerat måste det finnas en tidigare begäran σ _{t *} för x i samma fas, så t * <t. Efter att t * x är cacharnas senaste sida, så för att bli utkastad vid t kommer sekvensen σ _{t * + 1} , ..., σ _t måste begära minst k från x olika sidor. Det innebär att fasen i har begärt minst k + 1 olika sidor vilket är motsägelsefullt till fasdefinitionen. Så LRU måste vara en markeringsalgoritm.

Förslag 1.4: Varje markeringsalgoritm är strikt k-konkurrenskraftig .

Bevis: Låt σ vara ett exempel på personsökningsproblemet och l antalet faser för σ. Är l = 1 då är varje markeringsalgoritm optimal och den optimala offline-algoritmen kan inte vara bättre.
Vi antar att l ≥ 2. kostnaden för varje markeringsalgoritm, till exempel är σ avgränsat ovanifrån med l ⋅ k eftersom i varje fas en markeringsalgoritm inte kan avvisa mer än k sidor utan att avvisa en markerad sida.
Nu försöker vi visa att den optimala offline-algoritmen avvisar minst k + l-2 sidor för σ, k i den första fasen och minst en för varje följande fas utom för den sista. För bevis kan vi definiera l-2 disjunktionssekvenser av σ. Därefter i i {1, ..., l-2} börjar vid den andra positionen i fas i + 1 och slutar med den första positionen i fas i + 2.
Låt x vara den första sidan i fas i + 1. I början av efterföljande i finns det sidan x och högst k-1 olika sidor i den optimala offline-algoritmcachen. I efterföljande är jag k sida begäran annorlunda än x, så den optimala offline-algoritmen måste vända minst en sida för varje senare. Eftersom i fasen 1 början är cachen fortfarande tom, orsakar den optimala offline-algoritmen k-utkast under den första fasen. Det visar det

w _A (σ) ≤ l⋅k ≤ (k + l-2) k ≤ OPT (σ) ⋅ k

Corollary 1.5: LRU och FWF är strikt k-konkurrenskraftiga .

Övning: Visa att FIFO inte är någon markeringsalgoritm, utan strikt k-konkurrenskraftig .

Finns det ingen konstant r för vilken en online-algoritm A är r-konkurrenskraftig, kallar vi A inte konkurrenskraftig

Förslag 1.6: LFU och LIFO är inte konkurrenskraftiga .

Bevis: Låt l ≥ 2 vara konstant, k ≥ 2 cachestorleken. De olika cachesidorna är nuverserade 1, ..., k + 1. Vi tittar på följande sekvens:

Den första sidan 1 begärs l gånger än sidan 2 och så en. I slutet finns det (l-1) alternerande förfrågningar för sida k och k + 1.
LFU och LIFO fyller sin cache med sidorna 1-k. När sida k + 1 begärs sänds k ut och vice versa. Det betyder att varje begäran om efterföljande (k, k + 1) ^l-1 avvisar en sida. Dessutom är deras k-1-cachemissar för första gången användningen av sidorna 1- (k-1). Så LFU och LIFO släpper ut exakta k-1 + 2 (l-1) sidor.
Nu måste vi visa att för varje konstant τ∈ℜ och varje konstant r ≤ 1 finns det en l så att

vilket är lika med

För att tillfredsställa denna ojämlikhet måste du bara välja l tillräckligt stort. Så LFU och LIFO är inte konkurrenskraftiga.

Förslag 1.7: Det finns ingen r-konkurrerande deterministisk online-algoritm för sökning med r <k .

Beviset för detta sista förslag är ganska långt och baserat på påståendet att LFD är en optimal offline-algoritm. Den intresserade läsaren kan slå upp den i boken om Borodin och El-Yaniv (se källor nedan).

Frågan är om vi kan göra bättre. För det måste vi lämna den deterministiska metoden bakom oss och börja randomisera vår algoritm. Det är uppenbart att det är mycket svårare för motståndaren att straffa din algoritm om den är slumpmässig.

Randomiserad sökning kommer att diskuteras i ett av nästa exempel ...