Alla närmaste mindre värden

Inom datavetenskap är problemet med alla närmaste mindre värden följande uppgift: för varje position i en nummersekvens, sök bland de tidigare positionerna efter den sista positionen som innehåller ett mindre värde. Detta problem kan lösas effektivt både med parallella och icke-parallella algoritmer: Berkman, Schieber & Vishkin (1993), som först identifierade proceduren som en användbar subrutin för andra parallella program, utvecklade effektiva algoritmer för att lösa det i Parallel Random Access Machine modell; det kan också lösas i linjär tid på en icke-parallell dator med hjälp av en stack -baserad algoritm. Senare forskare har studerat algoritmer för att lösa det i andra modeller för parallell beräkning.

Exempel

Antag att ingången är den binära van der Corput-sekvensen

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15.

Det första elementet i sekvensen (0) har inget tidigare värde. Det närmaste (endast) mindre värdet före 8 och till 4 är 0. Alla tre värden före 12 är mindre, men det närmaste är 4. Fortsätter på samma sätt, de närmast föregående mindre värdena för denna sekvens (som indikerar att det inte finns av ett tidigare mindre värde med ett bindestreck) är

—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7.

I de flesta applikationer bör positionerna för de närmaste mindre värdena, och inte värdena själva, beräknas, och i många applikationer bör samma beräkning beräknas för omkastning av sekvensen för att hitta följande mindre värde som är närmast i sekvensen.

Ansökningar

Berkman, Schieber & Vishkin (1993) nämner många andra problem som kan lösas effektivt parallellt med hjälp av en beräkning av närmaste mindre värden. Bland dem inkluderar de följande:

  • Sammanfogningsalgoritmer , beräknar sammanfogningssteget för en sammanslagningssort . Indata till dessa algoritmer består av två sorterade arrayer av tal; den önskade utdata är samma uppsättning siffror i en enda sorterad array. Om man sammanfogar de två sorterade arrayerna, den första i stigande ordning och den andra i fallande ordning, så är föregångaren till varje värde i utdata antingen dess närmaste föregående mindre värde eller dess närmast följande mindre värde (vilket av de två som är störst) och positionen för varje värde i den sorterade utmatningsmatrisen kan lätt beräknas från positionerna för dessa två närmaste mindre värden.
  • Konstruktion av kartesiska träd . Ett kartesiskt träd är en datastruktur som introducerats av Vuillemin (1980) och som studerats vidare av Gabow, Bentley & Tarjan (1984) för tillämpningar för avståndssökning . Kartesiska träd uppstår också i definitionen av treap och randomiserade binära sökträddatastrukturer för binär sökning . Det kartesiska trädet för en värdesekvens har en nod för varje värde. Trädets rot är minimivärdet för sekvensen; för varannan nod är föräldern till noden antingen dess närmaste föregående mindre värde eller dess närmast följande mindre värde (beroende av de två som finns och är större). Således kan kartesiska träd konstrueras i linjär tid baserat på en algoritm med alla närmaste mindre värden.
  • Matchande parenteser . Om en sekvens av öppna och stängda parenteser anges som indata, tillsammans med kapsdjupet för varje parentes, så är matchningen till varje öppen parentes nästa nära parentes utan större kapsdjup, så den kan hittas av en alla närmaste beräkning av mindre värden som bryter banden till förmån för nära parenteser. Om häckningsdjupen inte anges kan de beräknas med en prefixsummaberäkning .

Liknande tekniker kan också appliceras på problem med polygontriangulering , konvex skrovkonstruktion (som parallelliserar den sekventiella Graham scan konvexa skrovalgoritmen), rekonstruktion av träd från två av trädens korsningsordningar och quadtree-konstruktion.

Sekventiell algoritm

På en sekventiell dator kan alla närmaste mindre värden hittas genom att använda en stackdatastruktur : man bearbetar värdena i sekvensordning, använder stacken för att upprätthålla en efterföljd av de värden som har bearbetats hittills och är mindre än något senare värde som redan har bearbetats. I pseudokod är algoritmen följande. 

     S = ny tom stackdatastruktur  för  x i inmatningssekvensen  gör  medan  S är icke-tom och det översta elementet i S är större än eller lika med x  gör  pop S  om  S  är  tomt  så  har x inget föregående mindre värde  annars  det närmaste mindre värdet till x är det översta elementet i S tryck x till S

Trots att den har en kapslad loopstruktur är körtiden för denna algoritm linjär, eftersom varje iteration av den inre loopen tar bort ett objekt som hade lagts till i någon tidigare iteration av den yttre loopen. Det är nära besläktat med en algoritm av Knuth för sortering med en stack (för ingångar som kan sorteras på detta sätt).

En ännu enklare linjär-tidssekventiell algoritm ( Barbay, Fischer & Navarro (2012), Lemma 1) behöver inte ens en stack; den antar att inmatningssekvensen ges som en array A[1,n] av storleken n och lagrar index j för det föregående mindre värdet av det i: te värdet A [i] i P[i] . Vi antar ett konstgjort totalt minimum vid A[0] : 

 för  i från 1 till n: j = i-1  medan  A[j] >= A[i]: j = P[j] P[i] = j

Parallella algoritmer

Berkman, Schieber & Vishkin (1993) visade hur man löser problemet med alla närmaste mindre värden effektivt på en parallell-läs-sam-skriv- Parallel Random Access Machine . För en sekvens av n värden, lagrade som en array , visar de att problemet kan lösas i tid O(log log n ) med hjälp av en linjär mängd totalt arbete. För sekvenser där alla värden är heltal i intervallet [1, s ] förbättrade Berkman, Matias & Ragde (1998) denna gräns till O(log log log s ); de visade också att, för tillräckligt stora värden på s , är den tidigare dubbellogaritmiska tidsgränsen det bästa som kan uppnås för problemet. Sedan detta arbete har parallella algoritmer för problemet med alla närmaste mindre värden också utvecklats på andra modeller av parallell beräkning, inklusive parallella datorer med ett hyperkubstrukturerat kommunikationsnätverk och den synkrona parallella bulkmodellen.

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=All_nearest_smaller_values&oldid=1136225073 "