Prioritetskö

Från Wikipedia, den fria encyklopedin
Hoppa till navigation Hoppa till sökning

Inom datavetenskap kallas en prioritetskö (även prioritetslista, prioritetskön, prioritetskön eller engelsk prioritetskö ) en viss abstrakt datastruktur , närmare bestämt en utökad form av en . Elementen som placeras i kön får en nyckel som bestämmer i vilken ordning elementen bearbetas.

Operationer

Prioriterade köer behöver operationerna

  • infoga , för att infoga ett element och
  • extractMin , för att returnera och ta bort elementet med den lägsta nyckeln (= högsta prioritet)
  • isTom , för att kontrollera om kön är tom,

Stöd.

Det finns också operationer som är särskilt viktiga för onlinealgoritmer :

  • ta bort ta bort ett element
  • minskaKey minska nyckelvärdet (= öka prioriteten)

Andra vanliga operationer är:

  • kika , returnera objektet med högsta prioritet utan att ändra kön
  • sammanslagning , sammanslagning av två prioriterade köer

genomförande

Genomförandet av prioriterade köer kan göras via AVL -träd . Både insatsen och extractMin kan sedan utföras i O (log n) tid. En annan möjlighet är att använda delvis ordnade träd ( högar ). Även här är tidskomplexiteten O (log n).

Exempel på datastrukturer som effektivt implementerar prioritetsköer är

Följande tabell visar en översikt över de olika drifttiderna för vissa implementeringar i O -notation .

kirurgi titt extraktMin Föra in minska nyckeln sammanfoga
Binär hög [1] Θ (1) Θ (logga n ) O (logg n ) O (logg n ) Θ ( n )
Vänster träd [2] Θ (1) Θ (logga n ) Θ (logga n ) O (logg n ) Θ (logga n )
Binomial hög [1] [3] Θ (1) Θ (logga n ) Θ (1) a Θ (logga n ) O (log n ) b
Fibonacci -hög [1] [4] Θ (1) O (log n ) a Θ (1) Θ (1) a Θ (1)
en amorterad
b n är storleken på den större högen

Ansökningar

Prioritetsköer kan användas för att implementera diskreta händelsessimuleringar. Tiderna för respektive händelser beräknas som en nyckel, tid-händelseparet sätts in i prioritetskön och prioritetskön matar sedan ut den aktuella (dvs nästa att bearbetas) händelse.

I allmänhet behövs prioritetsköer för många algoritmer eller till och med klasser av algoritmer.

Giriga algoritmer använder till exempel prioritetsköer, eftersom de ofta måste bestämma lägsta eller högsta av en uppsättning. En av de mest kända algoritmerna av denna typ är Dijkstras algoritm för att beräkna de kortaste vägarna.

Du kan också använda prioritetsköer för bästa sökalgoritmer . En prioritetskö används vanligtvis för att hitta den näst mest lovande noden i en iteration. Ett exempel på detta är A * -algoritmen för att beräkna de kortaste banorna i grafer.

En speciell algoritm som också kan implementeras med prioriterade köer är Huffman -kodning . Prioritetskön används för att hitta de tecken med lägsta sannolikhet.

Tillägg

Förutom den klassiska, enda ändade prioritetskön, finns det också dubbla köer. Dessa stöder också en extractMax -operation för att extrahera elementet med den största nyckeln. Dubbla högar erbjuder en möjlighet för implementering av sådana datastrukturer . Alternativt kan datastrukturer som min-max-högar också användas, som direkt stöder prioriterade köer i två ändar.

Parallell prioritetskö

För att påskynda prioritetsköerna ytterligare kan de parallelliseras. Det finns tre olika alternativ för parallellisering. Det första alternativet är att helt enkelt parallellisera de enskilda operationer (insert, extractMin ...). Det andra alternativet gör att flera processer kan komma åt prioritetskön samtidigt. Det sista alternativet är att utföra varje operation på k -element istället för bara ett element i taget. I fallet med extractMin, till exempel, skulle de första k -elementen med högsta prioritet tas bort från prioritetskön.

Parallellisera enskilda operationer

Ett enkelt sätt att parallellisera prioritetsköer är att parallellisera de enskilda operationerna. Detta innebär att kön fungerar exakt som en sekventiell, men de enskilda operationerna accelereras genom användning av flera processorer. Den maximala hastigheten som kan uppnås här är genom begränsad eftersom det finns sekventiella implementeringar för prioritetsköer vars långsammaste operation är i Tiden tar slut (t.ex. binomialhög).

På Samtidig Läs, Exclusive Skriv (CREW) PRAM modell verksamheten infoga, extractMin, decreaseKey och ta bort kan utföras i konstant tid om Processorer finns tillgängliga, med är storleken på prioritetskön. [5] I det följande implementeras kön som en binomial hög. Efter varje operation måste det vara så att högst tre träd av samma ordning finns och att den minsta roten av träden är av ordning är mindre än alla rötter av högre ordens träd.

  • infoga (e) : Ett nytt binomialt träd med ordning 0, vars enda nod innehåller elementet e , infogas. Därefter kommer två träd att vara av samma ordning till ett ordens träd sätt ihop om tre träd i ordning existera. Trädet med den minsta roten av träden med ordning används inte för detta. Detta steg utförs parallellt med att varje processor tar hand om träd i en order. Så sätt in möjlig.

Följande är operationen i pseudokod .

 infoga (e) {
  L [0] = L [0] ∪ e
  parallell sammanfogning ()
}
parallell sammanfogning () {
  för varje order i parallell :
    om | L [i] | > = 3:
      slå ihop två träd från L [i] \ min (L [i]) till ett nytt träd b
      L [i + 1] = L [i + 1] ∪ b
}
  • extractMin : Det minsta som ska tas bort är det minsta elementet i träd av ordning 0. Detta element tas bort. För att se till att det nya minimumet också är i ordning 0, för varje beställning trädet med minsta rotdelning och ordningens två nya träd Lagt till. Genom att tilldela varje processor exakt en order kan detta steg utföras parallellt i utförs. Efter detta steg, som i insatsoperationen , två ordningsträd till ett ordens träd sätt ihop om minst tre ordningsträd existera. Eftersom detta steg också kan utföras parallellt för varje beställning kan extractMin utföras i konstant tid.
 extractMin () {
  e = min (L [0])
  L [0] = L [0] \ e
  för varje order i parallell :
    om | L [i] | > = 1:
      dela min (L [i]) i två träd a, b
      L [i] = L [i] \ min (L [i])
      L [i-1] = L [i-1] ∪ {a, b}
  parallell sammanfogning ()
  returnera e
}

Konceptet för konstant skär och extractMin operationer kan förlängas för att uppnå en konstant runtime för bort. Förminskningsknappsoperationen kan sedan också implementeras i konstant tid genom en borttagning och en efterföljande insats . [5]

Fördelen med denna parallellisering är att den kan användas precis som en normal sekventiell prioritetskö. Men det kan också bara vara en snabbare kan uppnås. I praktiken begränsas detta ytterligare av det faktum att vid parallellimplementering måste ytterligare ansträngningar göras för kommunikation mellan de olika processorerna.

Samtidig parallellåtkomst

Om samtidig åtkomst till en prioritetskö tillåts kan flera processer samtidigt utföra operationer på prioritetskön. Detta medför dock två problem. Å ena sidan är semantiken för de enskilda operationerna inte längre självklar. Till exempel, om två processer kör extractMin samtidigt, ska båda processerna få samma artikel eller ska de vara olika? Detta begränsar parallelliteten till applikationsnivån med hjälp av prioritetskön. Å andra sidan finns problemet med åtkomstkonflikten, eftersom flera processer har tillgång till samma element.

Nod 3 läggs till och sätter pekaren från nod 2 till nod 3. Omedelbart därefter raderas nod 2 och pekaren från nod 1 sätts till nod 4. Detta innebär att nod 3 inte längre kan nås.

Samtidig åtkomst till en prioritetskö kan implementeras på en PRAM -modell för samtidig läsning, samtidig skrivning (CRCW). I det följande implementeras prioritetskön som en hopplista . [6] [7] Dessutom används ett primitivt CAS- atom för synkronisering för att möjliggöra en låsfri hopplista . Noderna i hopplistan består av en unik nyckel, en prioritet, en rad pekare till nästa nod och en raderingstagg . Raderingsindikatorn indikerar om noden för närvarande raderas av en process. Detta innebär att de andra processerna vet att noden är på väg att raderas och kan reagera därefter, beroende på de operationer de utför.

  • infoga (e) : Först skapas en ny nod med en nyckel och en prioritet. Dessutom överförs ett antal nivåer till noden. Sedan startas en sökning för att hitta rätt position i hopplistan där du måste lägga till den nyskapade noden. Sökningen startar från den första noden och från den högsta nivån och korsar hopplistan ner till den lägsta nivån tills rätt position har hittats. Den senast korsade noden sparas som den föregående noden för varje nivå. Dessutom sparas noden till vilken pekaren på föregångarens nod pekar som den efterföljande noden. Därefter, för varje nivå i den nya noden, ställs pekaren för den sparade föregående noden till den nya noden. Slutligen sätts pekarna för varje nivå i den nya noden till motsvarande efterföljande noder.
  • extractMin () : Först hoppas listan över tills en nod nås vars radering inte är inställd. Sedan är raderingsflaggan inställd för denna nod. Därefter uppdateras pekarna för den föregående noden.

Vid samtidig åtkomst till en prioritetskö måste man vara noga med att undvika potentiella konflikter mellan två processer. Till exempel kan en konflikt uppstå om en process försöker lägga till en nod, men en annan process tar redan bort sin föregående nod. [6] Det finns en risk att den nya noden har lagts till i hopplistan, men inte längre kan nås. ( Se bild )

K elementoperationer

Denna typ av parallellisering av prioritetsköer introducerar nya operationer som inte längre behandlar ett enda element, utan snarare Element samtidigt. Den nya operationen k_extractMin raderar sedan minsta objekt från prioritetskön och returnerar dem. Kön är parallelliserad på distribuerat minne. Varje processor har sitt eget privata minne och en lokal (sekventiell) prioritetskö. Elementen i den globala kön är därför fördelade över alla processorer. I fallet med en k_insert -operation fördelas elementen slumpmässigt jämnt till processorerna och sätts in var och en i de lokala prioritetsköerna. Enskilda element kan fortfarande infogas. Med denna strategi är det stor sannolikhet att de globalt minsta elementen är i föreningen av de lokalt minsta elementen i alla processorer. [8] Varje processor innehar således en representativ del av den globala prioritetskön.

k_extractMin körs på en kö med tre processorer. De gröna artiklarna returneras och tas bort från kön.

Den här egenskapen används med k_extractMin , i det att minsta element tas bort och samlas i en resultatuppsättning. Elementen förblir tilldelade sin ursprungliga processor. Numret antalet objekt som raderas från varje lokal prioritetskö beror på och antalet processorer . [8] Genom parallellt urval, de minsta elementen i resultatuppsättningen. Det är stor sannolikhet att dessa också är de globala minsta element. Om inte, blir det igen Objekt raderade från varje lokal prioritetskö tills global de minsta elementen i resultatuppsättningen. Nu kan de minsta element returneras. Alla andra objekt sätts tillbaka i de lokala prioritetsköerna från vilka de togs bort. Driftstiden för k_extractMin förväntas , om och Beskriver storleken på prioritetskön. [Åttonde]

Prioritetskön kan förbättras genom att inte alltid sätta in resultatuppsättningen direkt i den lokala kön efter en k_extractMin -operation. Detta sparar dig från att behöva ta bort element upprepade gånger från en lokal kö och sedan sätta in dem igen direkt efteråt.

Genom att ta bort flera element samtidigt kan en betydande acceleration uppnås jämfört med sekventiella prioritetsköer. Men inte alla algoritmer kan dra fördel av denna typ av prioritetskö. Till exempel med Dijkstra -algoritmen kan flera noder inte redigeras samtidigt. Dijkstra tar noden med minsta avstånd till startnoden från prioritetskön och slappnar sedan av kanterna. Detta kan ändra prioriteten för de angränsande noder som redan finns i prioritetskön. Genom att ta bort Noder, med det minsta avståndet, kan ske genom att redigera en av Node, prioriteten hos en av de andra Nod ändras. Denna nod bör då bara redigeras senare, men kommer nu att redigeras tidigare. Detta markerar sedan denna nod som besökt för tidigt. I det här fallet har en väg hittats från startnoden till denna nod, men avståndet är inte minimalt. Med andra ord, genom att använda k-elementoperationer för Dijkstras algoritm förstörs egenskapen för etikettinställning.

litteratur

  • George F. Luger: Artificiell intelligens. Strategier för att lösa komplexa problem . Pearson Studies, 2001, ISBN 3-8273-7002-7 .

webb-länkar

Individuella bevis

  1. ^ A b c Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest : Introduktion till algoritmer . I: MIT Press och McGraw-Hill . 1990, ISBN 0-262-03141-8 .
  2. ^ Clark A. Clane: Linjära listor och prioriterade köer som balanserade binära träd (doktorsexamen) . Red.: Institutionen för datavetenskap, Stanford University. 1972, ISBN 0-8240-4407-X ( stanford.edu ).
  3. Binomial hög | Strålande Math & Science Wiki. brilliant.org, åtkomst 30 september 2019 (amerikansk engelska).
  4. ^ Michael Fredman, Robert Tarjan : Fibonacci -högar och deras användning i förbättrade algoritmer för nätverksoptimering . I: Journal of the Association for Computing Machinery . tejp   34 , nej.   3 , juli 1987, sid.   596-615 , doi : 10.1145 / 28869.28874 ( ict.ac.cn [PDF]).
  5. ^ A b Gerth Brodal: Prioriterade köer på parallella maskiner . I: Algoritmteori - SWAT 96 . Springer-Verlag, 1996, sid.   416-427 , doi : 10.1007 / 3-540-61422-2_150 .
  6. a b Håkan Sundell, Philippas Tsigas: Snabba och låsfria samtidiga prioritetsköer för flertrådade system . I: Journal of Parallel and Distributed Computing . tejp   65 , nej.   5 , 2005, s.   609-627 , doi : 10.1109 / IPDPS.2003.1213189 .
  7. ^ Jonsson Lindén: En Skiplist-baserad samtidig prioritetskö med minimalt minneinnehåll . I: Teknisk rapport 2018-003 . 2013 ( uu.se ).
  8. ^ A b c Peter Sanders , Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: Sekventiella och parallella algoritmer och datastrukturer - Den grundläggande verktygslådan . Springer International Publishing , 2019, sid.   226-229 , doi : 10.1007 / 978-3-030-25209-0 .