Treffer: Analysis of the Performance Impact of Black-box Randomization for 7 Sorting Algorithms

Can black-box randomization change the performance of algorithms? The problem of worst-case behaviour in algorithms is difficult to handle, black-box randomization is one method that has not been rigorously tested. If it could be used to mitigate worst-case behaviour for our chosen algorithms, black-box randomization should be seriously considered for active usage in more algorithms. We have found variables that can be put through a black-box randomizer while our algorithm still gives correct output. These variables have been disturbed and a qualitative manual analysis has been done to observe the performance impact during black-box randomization. This analysis was done for 7 different sorting algorithms using Java openJDK 8. Our results show signs of improvement after black-box randomization, however our experiments showed a clear uncertainty when con- ducting time measurements for sorting algorithms.
Kan svartlåde-slumpning förändra prestandan hos algoritmer? Problemet med värsta-fall beteende hos algoritmer är svårt att hantera, svartlåde-slumpning är en metod som inte testast rigoröst än. Om det kan utnyttjas för att mildra värsta-fall beteende för våra utval- da algoritmer, bör svartlåde-slumpning beaktas för aktiv användning i fler algoritmer. Vi har funnit variabler som kan köras igenom svartlåde-slumpning samtidigt som vår algoritm ger korrekt utmatning. Dessa variabler har blivit utsatta för små störningar och en kvalitativ manuell ana- lys har gjorts för att observera huruvida prestandan förändrats under svartlåde-slumpning. Denna analys har gjorts för 7 sorteringsalgoritmer med hjälp av Java openJDK 8. Våra resultat visar tecken på förbättring efter svartlåde-slumpning, men våra experiment visade en klar osäkerhet när man utför tidsmätningar på sorteringsalgoritmer.