Introselekt
| Klass | Urvalsalgoritm |
|---|---|
| Datastruktur | Array |
| Prestanda i värsta fall | O( n ) |
| Bästa möjliga prestanda | O( n ) |
| Klass | Urvalsalgoritm |
|---|---|
| Datastruktur | Array |
| Prestanda i värsta fall | O( n log n ) |
| Bästa möjliga prestanda | O( n ) |
Inom datavetenskap är introselect (förkortning för "introspektivt urval") en urvalsalgoritm som är en hybrid av snabbval och median av medianer som har snabb medelprestanda och optimal prestanda i värsta fall . Introselect är relaterat till introsort- sorteringsalgoritmen : dessa är analoga förbättringar av de grundläggande quickselect- och quicksort -algoritmerna, i det att de båda börjar med snabbalgoritmen, som har bra medelprestanda och låg overhead, men faller tillbaka till en optimal algoritm för värsta fall. (med högre overhead) om den snabba algoritmen inte utvecklas tillräckligt snabbt. Båda algoritmerna introducerades av David Musser i ( Musser 1997 ), med syftet att tillhandahålla generiska algoritmer för C++ Standard Library som har både snabb genomsnittlig prestanda och optimal prestanda i värsta fall, vilket gör att prestandakraven kan skärpas.
I de flesta C++ Standard Library-implementeringar används dock en annan "introselect"-algoritm, som kombinerar snabbval och heapselect , och har en värsta möjliga körtid på O ( n log n ). C++-utkaststandarden, från och med 2022, har inga krav på sämsta tänkbara prestanda och tillåter därför ett sådant val.
Algoritmer
O ( n log n ) worst-case-beteende bevaras genom att skapa en hybrid av quicksort och heapsort . Introsort börjar med quicksort, så det uppnår prestanda liknande quicksort om quicksort fungerar, och faller tillbaka till heapsort (som har optimal värsta tänkbara prestanda) om quicksort inte går tillräckligt snabbt framåt. På liknande sätt kombinerar introselekt snabbval med median för median för att uppnå linjärt urval i värsta fall med prestanda som liknar snabbval.
Introselect fungerar genom att optimistiskt börja med snabbval och bara byta till en värsta tänkbar linjär-tidsvalsalgoritm (Blum-Floyd-Pratt-Rivest-Tarjans median för medianalgoritmen ) om den återkommer för många gånger utan att göra tillräckliga framsteg. Växlingsstrategin är det huvudsakliga tekniska innehållet i algoritmen. Att bara begränsa rekursionen till konstant djup är inte tillräckligt bra, eftersom detta skulle få algoritmen att slå på alla tillräckligt stora listor. Musser diskuterar ett par enkla tillvägagångssätt:
- Håll reda på listan över storlekar på de underpartitioner som bearbetats hittills. Om vid något tillfälle k rekursiva anrop har gjorts utan att halvera liststorleken, för några små positiva k , byt till den värsta linjära algoritmen.
- Summa storleken på alla partitioner som har genererats hittills. Om detta överskrider liststorleken gånger någon liten positiv konstant k , byt till den linjära algoritmen i värsta fall. Denna summa är lätt att spåra i en enda skalär variabel.
Båda tillvägagångssätten begränsar rekursionsdjupet till k ⌈log n ⌉ = O (log n ) och den totala körtiden till O ( n) .
Tidningen föreslog att mer forskning om introselekt var på gång, men författaren gick i pension 2007 utan att ha publicerat någon sådan ytterligare forskning.
Se även
- Musser, David R. (1997). "Introspektiva sorterings- och urvalsalgoritmer" . Programvara: Övning och erfarenhet . 27 (8): 983–993. doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# .