Cykeldetektering

Inom datavetenskap är cykeldetektering eller cykelfynd det algoritmiska problemet med att hitta en cykel i en sekvens av itererade funktionsvärden .

För vilken funktion $f som helst$ som mappar en ändlig mängd $S$ till sig själv, och varje initialvärde $x 0$ i $S$ , sekvensen av itererade funktionsvärden

x_{0},\ x_{1}=f(x_ {0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots

måste så småningom använda samma värde två gånger: det måste finnas något par distinkta index $i$ och $j$ så att $x i = x j$ . När detta händer måste sekvensen fortsätta med jämna mellanrum , genom att upprepa samma sekvens av värden från $x i$ till $x j - 1$ . Cykeldetektering är problemet med att hitta $i$ och $j$ , givet $f$ och $x 0$ .

Flera algoritmer för att hitta cykler snabbt och med lite minne är kända. Robert W. Floyds sköldpadda- och harealgoritm flyttar två pekare i olika hastigheter genom värdesekvensen tills de båda pekar på lika värden. Alternativt är Brents algoritm baserad på idén om exponentiell sökning . Både Floyds och Brents algoritmer använder endast ett konstant antal minnesceller, och tar ett antal funktionsutvärderingar som är proportionella mot avståndet från början av sekvensen till den första repetitionen. Flera andra algoritmer byter ut större mängder minne för färre funktionsutvärderingar.

Tillämpningarna för cykeldetektering inkluderar testning av kvaliteten på pseudoslumptalsgeneratorer och kryptografiska hashfunktioner , beräkningsalgoritmer för talteori , detektering av oändliga slingor i datorprogram och periodiska konfigurationer i cellulära automater , automatiserad formanalys av länkade listdatastrukturer och detektering av dödlägen för transaktionshantering i DBMS .

Exempel

En funktion från och till uppsättningen {0,1,2,3,4,5,6,7,8} och motsvarande funktionsdiagram

Figuren visar en funktion $f$ som mappar mängden $S = {0,1,2,3,4,5,6,7,8}$ till sig själv. Om man utgår från $0 x = 2$ och upprepade gånger tillämpar $f$ , ser man sekvensen av värden

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Cykeln i denna värdesekvens är $6, 3, 1$ .

Definitioner

Låt $S$ vara vilken finit mängd som helst, $f$ vara vilken funktion som helst från $S$ till sig själv och $x 0$ vara vilket element som helst av $S$ . För valfritt $i > 0$ , låt $x i = f (x i - 1)$ . Låt $μ$ vara det minsta indexet så att värdet $x μ$ återkommer oändligt ofta inom sekvensen av värden $x i$ , och låt $λ$ (looplängden) vara det minsta positiva heltal så att $x μ = x λ + μ$ . Cykeldetekteringsproblemet är uppgiften att hitta $λ$ och $μ$ .

Man kan se samma problem graf-teoretiskt , genom att konstruera en funktionell graf (det vill säga en riktad graf där varje vertex har en enda utgående kant) vars hörn är elementen i $S$ och vars kanter mappar ett element till motsvarande funktionsvärde, som visas i figuren. Uppsättningen av hörn som kan nås från startpunkten $x 0$ bildar en subgraf med en form som liknar den grekiska bokstaven rho ( $ρ$ ): en väg med längden $μ$ från $x 0$ till en cykel av $λ$ -hörn.

Datorrepresentation

I allmänhet kommer $f$ inte att anges som en värdetabell, som det visas i figuren ovan. Snarare kan en cykeldetekteringsalgoritm ges åtkomst antingen till sekvensen av värden xi $eller .$ till en subrutin för beräkning av $f$ Uppgiften är att hitta $λ$ och $μ$ samtidigt som man undersöker så få värden från sekvensen eller utför så få subrutinsamtal som möjligt. Vanligtvis är också rymdkomplexiteten hos en algoritm för cykeldetekteringsproblemet viktig: vi vill lösa problemet samtidigt som vi använder en mängd minne som är betydligt mindre än vad det skulle ta för att lagra hela sekvensen.

I vissa tillämpningar, och i synnerhet i Pollards rho-algoritm för heltalsfaktorisering , har algoritmen mycket mer begränsad tillgång till $S$ och till $f$ . I Pollards rho-algoritm, till exempel, $S$ mängden heltal modulo en okänd primfaktor av talet som ska faktoriseras, så även storleken på $S$ är okänd för algoritmen. För att tillåta cykeldetekteringsalgoritmer att användas med sådan begränsad kunskap, kan de utformas baserat på följande möjligheter. Initialt antas algoritmen ha i sitt minne ett objekt som representerar en pekare till startvärdet $x 0$ . I vilket steg som helst kan den utföra en av tre åtgärder: den kan kopiera vilken pekare den har till ett annat objekt i minnet, den kan tillämpa f och $ersätta$ vilken som helst av dess pekare med en pekare till nästa objekt i sekvensen, eller så kan den tillämpas en subrutin för att bestämma om två av dess pekare representerar lika värden i sekvensen. Åtgärden för likhetstestet kan involvera någon icke-trivial beräkning: till exempel, i Pollards rho-algoritm, implementeras den genom att testa om skillnaden mellan två lagrade värden har en icke-trivial största gemensamma divisor med talet som ska faktoriseras. I detta sammanhang, analogt med pekarmaskinsmodellen för beräkning, kan en algoritm som endast använder pekarkopiering, framsteg inom sekvensen och likhetstester kallas en pekaralgoritm.

Algoritmer

Om ingången ges som en subrutin för beräkning av $f$ , kan cykeldetekteringsproblemet trivialt lösas med användning av endast $λ + μ$ funktionsapplikationer, helt enkelt genom att beräkna sekvensen av värden $x i$ och använda en datastruktur såsom en hashtabell för att lagra dessa värden och testa om varje efterföljande värde redan har lagrats. Emellertid är rymdkomplexiteten för denna algoritm proportionell mot $λ + μ$ , onödigt stor. Dessutom, för att implementera denna metod som en pekaralgoritm skulle det krävas att man tillämpar likhetstestet på varje värdepar, vilket resulterar i kvadratisk tid totalt. Således har forskningen inom detta område koncentrerats på två mål: att använda mindre utrymme än denna naiva algoritm, och att hitta pekaralgoritmer som använder färre likhetstester.

Floyds sköldpadda och hare

Floyds cykeldetekteringsalgoritm för "sköldpadda och hare", applicerad på sekvensen 2, 0, 6, 3, 1, 6, 3, 1, ...

Floyds cykelsökningsalgoritm är en pekaralgoritm som endast använder två pekare, som rör sig genom sekvensen med olika hastigheter. Det kallas också för "sköldpaddan och harealgoritmen", vilket anspelar på Aesops fabel om sköldpaddan och haren .

Algoritmen är uppkallad efter Robert W. Floyd , som krediterades för sin uppfinning av Donald Knuth . Algoritmen förekommer dock inte i Floyds publicerade arbete, och detta kan vara en felaktig tillskrivning: Floyd beskriver algoritmer för att lista alla enkla cykler i en riktad graf i en tidning från 1967, men den här artikeln beskriver inte problemet med att hitta cykeln i funktionella grafer det är ämnet för denna artikel. Faktum är att Knuths uttalande (1969), som tillskriver det Floyd, utan citat, är det första kända utseendet på tryck, och det kan således vara en folksats , som inte kan tillskrivas en enda individ.

Den viktigaste insikten i algoritmen är följande. Om det finns en cykel, då, för alla heltal $i \geq μ$ och $k \geq 0$ , $x i = x i + kλ$ , där $λ$ är längden på slingan som ska hittas, är $μ$ indexet för det första elementet i cykeln och $k$ är ett heltal som representerar antalet loopar. Baserat på detta kan det sedan visas att $i = kλ \geq μ$ för något $k$ om och endast om $x i = x 2 i$ (om $x i = x 2 i$ i cykeln, så finns det något $k$ så att $2 i = i + kλ$ , vilket innebär att $i = kλ , och$ $om + kλ det x2i . = xi$ finns några $i$ och $k$ så att $i = kλ$ , då $2i = i + kλ$ och ) Algoritmen behöver alltså bara leta efter upprepade värden av denna speciella form, det ena dubbelt så långt från början av sekvensen som det andra, för att hitta en period $ν$ för en upprepning som är en multipel av $λ$ . När $ν$ väl har hittats spårar algoritmen sekvensen från början för att hitta det första upprepade värdet $x μ$ i sekvensen, med hjälp av det faktum att $λ$ delar $ν$ och därför att $x μ = x μ + v$ . Slutligen, när värdet på $μ$ väl är känt är det trivialt att hitta längden $λ$ för den kortaste upprepade cykeln, genom att söka efter den första positionen $μ + λ$ för vilken $x μ + λ = x μ$ .

Algoritmen håller alltså två pekare in i den givna sekvensen, en (sköldpaddan) vid $x i$ och den andra (haren) vid $x 2 i$ . Vid varje steg i algoritmen ökar den $i$ med ett, flyttar sköldpaddan ett steg framåt och haren två steg framåt i sekvensen, och jämför sedan sekvensvärdena vid dessa två pekare. Det minsta värdet på $i > 0$ för vilket sköldpaddan och haren pekar på lika värden är det önskade värdet $ν$ .

Följande Python- kod visar hur denna idé kan implementeras som en algoritm.

     
    
    
    
    
    
    
    
       
      
       
          
          
  
    
    
    
    
    
    
    

    
      0
      
       
          
             
          
 
    
    
    
      
      
       
          
          
 
       def  floyd  (  f  ,  x0  )  ->  tuple  [  int  ,  int  ]:  """Floyds cykeldetekteringsalgoritm."""  # Algoritmens huvudfas: hitta en upprepning x_i = x_2i.  # Haren rör sig dubbelt så snabbt som sköldpaddan och  # avståndet mellan dem ökar med 1 vid varje steg.  # Så småningom kommer de båda att vara inne i cykeln och sedan,  # vid något tillfälle, kommer avståndet mellan dem att vara  # delbart med perioden λ.  sköldpadda  =  f  (  x0  )  # f(x0) är elementet/noden bredvid x0.  hare  =  f  (  f  (  x0  ))  medan  sköldpadda  !=  hare  :  sköldpadda  =  f  (  sköldpadda  )  hare  =  f  (  f  (  hare  ))  # Vid denna punkt är sköldpaddans position, ν, som också är lika med  # med avståndet mellan haren och sköldpadda, är delbart med  # perioden λ. Så hare som rör sig i cykeln ett steg i taget,   # och sköldpadda (återställ till x0) som rör sig mot cykeln, kommer  # att skära varandra i början av cykeln. Eftersom   # avståndet mellan dem är konstant vid 2ν, en multipel av λ,  # kommer de överens så snart sköldpaddan når index μ.  # Hitta positionen μ för första repetitionen.  mu  =  sköldpadda  =  x0  medan  sköldpadda  !=  hare  :  sköldpadda  =  f  (  sköldpadda  )  hare  =  f  (  hare  )  # Haren och sköldpaddan rör sig i samma hastighet  mu  +=  1  # Hitta längden på den kortaste cykeln från x_μ  # Haren rör sig ett steg i taget medan sköldpaddan är stilla.  # lam inkrementeras tills λ hittas.  lam  =  1  hare  =  f  (  sköldpadda  )  medan  sköldpadda  !=  hare  :  hare  =  f  (  hare  )  lam  +=  1  retur  lam  ,  mu

Denna kod kommer bara åt sekvensen genom att lagra och kopiera pekare, funktionsutvärderingar och likhetstester; därför kvalificeras den som en pekaralgoritm. Algoritmen använder $O (λ + μ)$ operationer av dessa typer och $O (1)$ lagringsutrymme.

Brents algoritm

Richard P. Brent beskrev en alternativ cykeldetektionsalgoritm som, precis som sköldpadds- och harealgoritmen, bara kräver två pekare in i sekvensen. Det bygger dock på en annan princip: att söka efter den minsta potensen av två $2 i$ som är större än både $λ$ och $μ$ . För $i = 0, 1, 2, ...$ jämför algoritmen $x 2 i -1$ med varje efterföljande sekvensvärde upp till nästa potens av två, och stoppar när den hittar en matchning. Den har två fördelar jämfört med algoritmen för sköldpadda och hare: den hittar den korrekta längden $λ$ av cykeln direkt, snarare än att behöva söka efter den i ett efterföljande steg, och dess steg involverar bara en utvärdering av $f$ istället för tre.

Följande Python-kod visar mer detaljerat hur denna teknik fungerar.

     
    
    
        
      
        
       
             
              
              
              0
          
          

    
        
       
    
          
    

    
      0
       
          
          
          
 
       def  brent  (  f  ,  x0  )  ->  tuple  [  int  ,  int  ]:  """Brents cykeldetekteringsalgoritm."""  # huvudfas: sök successiva potenser av två  potenser  =  lam  =  1  sköldpadda  =  x0  hare  =  f  (  x0  )  # f(x0) är elementet/noden bredvid x0.  medan  sköldpadda  !=  hare  :  om  makt  ==  lam  :  # dags att starta en ny tvåkraft?  sköldpadda  =  harkraft  *=  2  lam  =  hare  =  f  (  hare  )  lam  +=  1  #  Hitta positionen för den första upprepningen av längden λ  sköldpadda  =  hare  =  x0  för  i  i  intervallet  (  lam  ):  # range(lam) ger en lista med värdena 0, 1, ... , lam-1  hare  =  f  (  hare  )  # Avståndet mellan haren och sköldpaddan är nu λ.  # Därefter rör sig haren och sköldpaddan i samma hastighet tills de kommer överens  mu  =  medan  sköldpadda  !=  hare  :  sköldpadda  =  f  (  sköldpadda  )  hare  =  f  (  hare  )  mu  +=  1  retur  lam  ,  mu

Liksom sköldpadda- och harealgoritmen är detta en pekaralgoritm som använder $O (λ + μ)$ tester och funktionsutvärderingar och $O (1)$ lagringsutrymme. Det är inte svårt att visa att antalet funktionsutvärderingar aldrig kan bli högre än för Floyds algoritm. Brent hävdar att hans cykelsökningsalgoritm i genomsnitt går cirka 36 % snabbare än Floyds och att den snabbar upp Pollard rho-algoritmen med cirka 24 %. Han utför också en genomsnittlig fallanalys för en randomiserad version av algoritmen där sekvensen av index som spåras av den långsammare av de två pekarna inte är två potenser själva, utan snarare en randomiserad multipel av två potenser. Även om hans huvudsakliga avsedda tillämpning var i heltalsfaktoriseringsalgoritmer, diskuterar Brent också tillämpningar för att testa pseudoslumptalsgeneratorer.

Gospers algoritm

RW Gospers algoritm hittar perioden $\lambda$ , och den nedre och övre gränsen för startpunkten, $\mu _{l}$ och $\mu _{u }$ , av den första cykeln. Skillnaden mellan den nedre och övre gränsen är av samma storleksordning som perioden, t.ex. $\mu _{l}+\lambda \sim \mu _{h}$ .

Fördelar

Huvuddragen i Gospers algoritm är att den aldrig säkerhetskopierar för att omvärdera generatorfunktionen och är ekonomisk i både rum och tid. Det skulle grovt kunna beskrivas som en samtidig version av Brents algoritm. Medan Brents algoritm gradvis ökar gapet mellan sköldpaddan och haren, använder Gospers algoritm flera sköldpaddor (flera tidigare värden sparas), som är ungefär exponentiellt fördelade. Enligt anteckningen i HAKMEM punkt 132 kommer denna algoritm att detektera upprepning före den tredje förekomsten av något värde, dvs cykeln kommer att itereras högst två gånger. Denna anteckning anger också att det räcker att lagra $\Theta (\log \lambda )$ tidigare värden; emellertid lagrar den tillhandahållna implementeringen ${\displaystyle \Theta (\log(\mu +\lambda ))}-$ värden. Anta till exempel att funktionsvärdena är 32-bitars heltal, och därför slutar den andra iterationen av cykeln efter högst 2 ³² funktionsutvärderingar sedan början (dvs. $\mu +2\ lambda \leq 2^{32}$ ). Då kommer Gospers algoritm att hitta cykeln efter högst 2 ³² funktionsutvärderingar, samtidigt som den konsumerar utrymmet på 33 värden (varje värde är ett 32-bitars heltal).

Komplexitet

Vid den $i$ -e utvärderingen av generatorfunktionen, jämför algoritmen det genererade värdet med $O(\log i)$ tidigare värden; observera att $i$ går upp till minst $\mu +\lambda$ och som mest $\mu +2\lambda$ . Därför är tidskomplexiteten för denna algoritm $O((\mu +\lambda )\cdot \log(\mu +\lambda ))$ . Eftersom den lagrar ${\displaystyle \Theta (\log(\mu +\lambda ))}-$ värden, är dess rymdkomplexitet $\ Theta (\log(\mu +\lambda ))$ . Detta är under det vanliga antagandet, som finns i denna artikel, att storleken på funktionsvärdena är konstant. Utan detta antagande är rymdkomplexiteten $\Omega (\log ^{2}(\mu +\lambda ))$ eftersom vi behöver minst ${\ displaystyle \mu +\lambda }$ distinkta värden och därmed är storleken på varje värde $\Omega (\log(\mu +\lambda ))$ .

Avvägningar mellan tid och rum

Ett antal författare har studerat tekniker för cykeldetektion som använder mer minne än Floyds och Brents metoder, men som upptäcker cykler snabbare. I allmänhet lagrar dessa metoder flera tidigare beräknade sekvensvärden och testar om varje nytt värde är lika med ett av de tidigare beräknade värdena. För att göra det snabbt använder de vanligtvis en hashtabell eller liknande datastruktur för att lagra de tidigare beräknade värdena, och är därför inte pekaralgoritmer: i synnerhet kan de vanligtvis inte tillämpas på Pollards rho-algoritm. Där dessa metoder skiljer sig är hur de bestämmer vilka värden som ska lagras. Efter Nivasch granskar vi dessa tekniker kort.

Brent beskriver redan varianter av sin teknik där indexen för sparade sekvensvärden är potenser av ett tal $R$ annat än två. Genom att välja $R$ som ett tal nära ett, och lagra sekvensvärdena vid index som är nära en sekvens av på varandra följande potenser av $R$ , kan en cykeldetekteringsalgoritm använda ett antal funktionsutvärderingar som ligger inom en godtyckligt liten faktor av det optimala $λ + μ$ .
Sedgewick, Szymanski och Yao tillhandahåller en metod som använder $M$ minnesceller och kräver i värsta fall endast $(\lambda +\mu )(1+cM ^{-1/2})$ funktionsutvärderingar, för någon konstant $c$ , som de visar vara optimala. Tekniken innebär att bibehålla en numerisk parameter $d$ , lagra i en tabell endast de positioner i sekvensen som är multiplar av $d$ , och tömma tabellen och dubbla $d$ när för många värden har lagrats.
Flera författare har beskrivit framstående punktmetoder som lagrar funktionsvärden i en tabell baserat på ett kriterium som involverar värdena, snarare än (som i metoden av Sedgewick et al.) baserat på deras positioner. Till exempel kan värden lika med noll modulo något värde $d$ lagras. Mer enkelt, Nivasch krediterar DP Woodruff med förslaget att lagra ett slumpmässigt urval av tidigare sett värden, göra ett lämpligt slumpmässigt val vid varje steg så att urvalet förblir slumpmässigt.
Nivasch beskriver en algoritm som inte använder en fast mängd minne, men för vilken den förväntade mängden minne som används (under antagandet att ingångsfunktionen är slumpmässig) är logaritmisk i sekvenslängden. Ett objekt lagras i minnestabellen, med denna teknik, när inget senare objekt har ett mindre värde. Som Nivasch visar kan objekten med denna teknik underhållas med hjälp av en stackdatastruktur , och varje successivt sekvensvärde behöver endast jämföras med toppen av stacken. Algoritmen avslutas när det upprepade sekvenselementet med minsta värde hittas. Att köra samma algoritm med flera stackar, genom att använda slumpmässiga permutationer av värdena för att ordna om värdena inom varje stack, möjliggör en avvägning mellan tid och rum som liknar de tidigare algoritmerna. Men även versionen av denna algoritm med en enda stack är inte en pekalgoritm, på grund av de jämförelser som behövs för att avgöra vilket av två värden som är mindre.

Varje cykeldetekteringsalgoritm som lagrar högst $M$ värden från ingångssekvensen måste utföra minst $(\lambda +\mu )\left(1+{\frac { 1}{M-1}}\right)$ funktionsutvärderingar.

Ansökningar

Cykeldetektering har använts i många applikationer.

Att bestämma cykellängden för en pseudoslumptalsgenerator är ett mått på dess styrka. Detta är den ansökan som Knuth citerade när han beskrev Floyds metod. Brent beskriver resultaten av att testa en linjär kongruentialgenerator på detta sätt; dess period visade sig vara betydligt kortare än vad som annonserades. För mer komplexa generatorer representerar sekvensen av värden i vilken cykeln finns kanske inte utsignalen från generatorn, utan snarare dess interna tillstånd.
Flera talteoretiska algoritmer är baserade på cykeldetektion, inklusive Pollards rho-algoritm för heltalsfaktorisering och hans relaterade kängurualgoritm för det diskreta logaritmproblemet .
I kryptografiska applikationer kan förmågan att hitta två distinkta värden x _μ−-1 och x _λ+μ−-1 mappade av någon kryptografisk funktion ƒ till samma värde x _μ indikera en svaghet i ƒ. Till exempel använder Quisquater och Delescaille cykeldetekteringsalgoritmer i sökningen efter ett meddelande och ett par datakrypteringsstandardnycklar som mappar det meddelandet till samma krypterade värde; Kaliski , Rivest och Sherman använder också cykeldetekteringsalgoritmer för att attackera DES. Tekniken kan också användas för att hitta en kollision i en kryptografisk hashfunktion .
Cykeldetektering kan vara till hjälp som ett sätt att upptäcka oändliga loopar i vissa typer av datorprogram .
Periodiska konfigurationer i cellulära automatsimuleringar kan hittas genom att tillämpa cykeldetekteringsalgoritmer på sekvensen av automattillstånd.
Formanalys av länkade listdatastrukturer är en teknik för att verifiera riktigheten av en algoritm med hjälp av dessa strukturer. Om en nod i listan felaktigt pekar på en tidigare nod i samma lista kommer strukturen att bilda en cykel som kan detekteras av dessa algoritmer. I Common Lisp upptäcker S-expression- skrivaren , under kontroll av variabeln *print-circle*, cirkulär liststruktur och skriver ut den kompakt.
Teske beskriver tillämpningar inom beräkningsgruppteori : att bestämma strukturen för en Abelisk grupp från en uppsättning av dess generatorer. De kryptografiska algoritmerna av Kaliski et al. kan också ses som ett försök att härleda strukturen hos en okänd grupp.
Fich (1981) nämner kort en applikation för datorsimulering av himlamekanik , som hon tillskriver William Kahan . I denna applikation kan cykeldetektering i fasutrymmet hos ett omloppssystem användas för att bestämma huruvida systemet är periodiskt till inom simuleringens noggrannhet.
I Mandelbrot Set fraktalgenerering används vissa prestationstekniker för att påskynda bildgenereringen. En av dem kallas "periodkontroll", som går ut på att hitta cyklerna i en punktbana. Den här artikeln beskriver tekniken " periodkontroll ". Du hittar en annan förklaring här . Vissa cykeldetekteringsalgoritmer måste implementeras för att implementera denna teknik.

externa länkar

Gabriel Nivasch, Cykeldetektionsproblemet och stackalgoritmen
Tortoise and Hare , Portland Pattern Repository
Floyd's Cycle Detection Algorithm (Sköldpaddan och haren)
Brent's Cycle Detection Algorithm (The Teleporting Turtle)