Prioritetsköer i Java och Python

Hur kan man prata om en "prioritetskö", en kö-datastruktur där element får lov att "hoppa före i kön" om de är viktiga? I den här artikeln jämförs de (ganska olika) svaren från Java och Pythons standardbibliotek.

Att tränga sig före i en kö är inte snällt, och folk som gör så är ofta svin, eller VIP. Eller bägge. Men ibland kan semantiken bakom detta vara användbar, och det finns en datastruktur som tillåter detta vid namn prioritetskö.

Värden som man infogar i en prioritetskö hamnar inte nödvändigtvis i slutet; istället infogas de på ett ordningsbevarande sätt. Så om jag infogar en 5:a i den här prioritetskön:

1 3 4 7 8

Så kommer den att se ut så här efter infogningen:

1 3 4 5 7 8

"Så det är som en lista som håller sig själv sorterad?" undrar den skeptiske läsaren vid den här punkten. Ja och nej. Vad du ser ovan ser från utsidan sett ut som en lista som håller sig själv uppdaterad. Men internt kan vi lagra saker som en heap eller som ett binärträd, och få bättre prestanda när vi infogar eller hittar/tar bort element. Ett bra sätt att tänka på de här interna datastrukturerna är att de är som olika sorteringsalgoritmer, men "frusna i tiden" som datastrukturer. (Detta är inte bara en poetisk formulering; Wikipedia gör ekvivalensen explicit här.)

Prioritetsköer är bra till ett antal saker. Kanske man ska implementera en jobbkö av framtida uppgifter att utföra, men vissa jobb kanske ska ges förtur framför andra. (Dessa viktigare jobb är svinen, eller VIP:arna, som tränger sig före så att vi vanliga jobb får vänta längre.) Det hela är ganska flexibelt; man kan ha en nivå av brådska, eller flera.

Eller kanske man ska bygga en diskret händelsesimulering, för att simulera en hiss eller ett biljardspel eller en SimCity-liknande värld genom att hantera händelser i kronologisk ordning. En prioritetskö hjälper genom att konstant servera nästa händelse som ska hanteras. Värdet som eventen sorteras på är en ökande tidskoordinat; skönheten med datastrukturen är att vi inte konstant måste sortera om saker — prioritetskön upprätthåller ordningen åt oss.

Prioritetsköer är en generalisering av vanliga köer. Om vi har en prioritetskö, så kan vi få den att fungera som en vanlig kö genom att använda ett ständigt ökande sekvensnummer som prioritetsvärde, så att alla infogade värden hamnar i slutet. Vanlig kö; inga svin.

"Prioritetskö" är namnet på den abstrakta datastrukturen, på samma sätt som "lista" eller "associativt fält". Det abstrakta konceptet säger ingenting om hur saker är implementerade under huven. Implementationer av en prioritetskö (konkreta datastrukturer) har namn som "binär heap" eller "balanserat binärt träd". Denna distinktion mellan abstrakt och konkret blir viktig om en stund.

Java och Python, bägge objektorienterade språk, har en implementation vardera av prioritetsköer. De landar på samma ställe och man kan göra samma saker med bägge, men sättet de exponerar sina datastrukturer är ganska olika.

Java

Javas Collection Framework är genomgående och imponerande, och prioritetsköer är inget undantag. Klassen PriorityQueue implementerar en prioritetskö. Vi återkommer till vårt löpande exempel (och använder Java 11s var-syntax):

var queue = new PriorityQueue<>(List.of(4,  8,  7,  3, 1));
queue.add(5);

Vi använder add -metoden, som ovan, för att infoga nya element i kön. Värdet 5 hamnar mellan 4 och 7 i den bemärkelsen att om vi börjar plocka ut element, så kommer 5 att trilla ut på fjärde plats.

queue.poll();      //  1
queue.poll();      //  3
queue.poll();      //  4
queue.poll();      //  5

Dessa heltal lagras i stigande ordning, eftersom det är den naturliga ordningen för typen Integer . Vi har också valet, när vi skapar vår PriorityQueue , att skicka in en skräddarsydd Comparator som anger en föredragen ordning.

PriorityQueue implementerar interfacet Queue . Om vi vill ha en vanlig kö så skulle vi förmodligen föredra ArrayDeque . Om vi bytte ut PriorityQueue mot ArrayDeque i koden ovan så skulle den fortfarande fungera, men 5 skulle nu infogas i slutet istället.

En ArrayDeque kan add och poll element på (amorterat) konstant tid. En PriorityQueue behöver upprätthålla ordningen, och tar därmed logaritmisk tid för både add och poll .

Slutligen, om man delar kön mellan trådar så vill man troligen plugga in en PriorityBlockingQueue istället. (Återigen, koden ovan kommer att Bara Funka om man gör det.) Med denna får man trådsäkerhet med i paketet — många samtidiga add - och poll -anrop från olika trådar kommer inte att förstöra ordningen eller kasta ett ConcurrentModificationException . (Istället ställer sig anropen "i kö" för att använda kön. En liten smula meta.)

"Plug-and-play"-aspekten hos Collections Framework är en av dess många undervärderade fördelar. Det finns ett litet antal generella interface (som Queue eller Deque ), och många implementationer av dem.

Python

Python har ett annat synsätt på prioritetsköer. Den här Python-koden (körd i Pythons REPL) är den moraliska motsvarigheten till Java-koden med PriorityQueue :

>>> queue = [4, 8, 7, 3, 1]
>>> import heapq
>>> heapq.heapify(queue)
>>> heapq.heappush(queue, 5)

Vänta, vad nu? En prioritetskö är en list i Python!? Jo, ja. Mer exakt så är det en vanlig list där vi lovar att upprätthålla "heap-invarianten", som räknar med att elementen är sorteade till en viss grad. Till exempel, om vi skriver ut vår queue vid den här punkten:

>>> queue
[1, 3, 5, 4, 8, 7]

Precis som förut så kommer element att komma ut i rätt ordning när vi poppar ut dem:

>>> heapq.heappop(queue)
1
>>> heapq.heappop(queue)
3
>>> heapq.heappop(queue)
4
>>> heapq.heappop(queue)
5
>>> queue
[7, 8]

En kollega som korrekturläste den här artikeln tittade på heapq s beteende ovan och mumlade "det måste finnas nån dold datastruktur någonstans som håller koll på ordningen..." Men nej, allting görs med själva listan. Om vi återkommer till listan [1, 3, 5, 4, 8, 7] och varför den uppfyller invarianten, så illustreras det bäst med en bild:

1 
|
 +----+----+      
        |     |     
        3    5--------------+      
        |                        |      
        +---------+----+    7                
                      |    |               
                      4    8

Listan kodar ett implicit träd. Ett element på index k har barn (om de finns) på indexen k*2+1 och k*2+2 . Heap-invarianten kräver att barn är större än eller lika med sina föräldrar, vilket stämmer för ovanstående lista. När vi kör heapq.heapify (och efter ytterligare operationer) så sker precis tillräckligt mycket sortering för att heap-invarianten ska hålla.

(Min kollega tog in allt detta, och sade "Jag föredrar hur Java gör det". Fair enough.)

Pythons heapq -modul har en känsla av "ta med din egen datastruktur" jämfört med Javas PriorityQueue . Rörläggningen sticker ut; den underliggande listan är bara en vanlig lista, och heap-invarianten är din att schabbla bort. (Men om du gör det, så är det ägg i ditt ansikte; din kod kommer inte att fungera som den ska.)

Det här visar en skillnad i filosofi och kultur mellan Java och Python. Java exponerar en klass PriorityQueue som kapslar in och döljer alla implementationsdetaljer; Python exponerar en modul med statiska metoder, och ger dig en algoritm "priority heap" som du kan använda för att modellera en prioritetskö.

Jag var nyfiken så jag gick tillbaka i mailarkiven för python-dev för att se om angreppssättet någonsin diskuterades. Jag hittade det här citatet av Guide van Rossum 2002:

[...] en klass verkar för tungrott för det här, precis som det är overkill för bisect [...]

(En annan utvecklare hade skrivit en alternativ implementation som dolde allting i en klass. Så de hade chansen att kapsla in i en klass, men de valde att exponera allting.)

Två approacher

I Java är allting snyggt undanstuvat. I Python sticker rören fram — du får verktygen, men det är upp till dig att använda dem rätt. Det finns inget rätt eller fel här, det är bara två approacher till biblioteks-API-design.

Men det speglar ganska väl hur båda språken (och deras omgivande kultur) tänker på inkapsling. I Java deklarerar man sina medlemsvariabler som privata om inget annat anges — det så man skyddar sitt objekts invarianter, och gör det möjligt att refaktorisera i framtiden. Python har inget <em>private</em> -nyckelord, och inget motsvarande idiomatiskt sätt att skydda sitt objekts data — den allmänna förväntan är att man lagrar sin objeksdata som attribut, och att ingen konsument av objektet sedan missbrukar rätten att läsa eller skriva dem. Javas system bygger på verkställande av lag och ordning; Pythons bygger på social konvention.

Kan det vara så att denna kulturella skillnad är knuten till hur språken (ofta) används, och förväntningarna från deras respektive communities? Java, som man hittar i affärsvärlden där "att signera/godkänna kod" ofta är ett fenomen, opererar i miljöer där det är en allvarlig sak om en kollega ställer till det för ens klassinvarianter; Python, som används i utbildning, i småföretagande, och i öppen källkod, prioriterar öppenhet och att "visa sitt arbete", och accepterar risken för missbruk med attityden "gör inte så då". Nära två decennier av användning av heapq i det vilda visar på att de informella reglerna är lätta att hålla sig till.

Jag är inte säker på vilken approach jag gillar bäst. Javas inkapsling eller Pythons implicita tillit? Jag kan argumentera för endera ståndpunkten. Det kan ju vara så att det finns plats för bägge sätten i världen.

Av Carl Mäsak