Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Analysis of the Performance Impact of Black-box Randomization for 7 Sorting Algorithms
KTH, School of Engineering Sciences (SCI).
KTH, School of Engineering Sciences (SCI).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Analys av svartlåde-slumpnings effekt på prestandan hos 7 sorteringsalgoritmer (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2018. , p. 55
Series
TRITA-SCI-GRU ; 2018-091
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:kth:diva-231089OAI: oai:DiVA.org:kth-231089DiVA, id: diva2:1222203
Supervisors
Examiners
Available from: 2018-06-21 Created: 2018-06-21 Last updated: 2018-06-21Bibliographically approved

Open Access in DiVA

fulltext(2076 kB)17 downloads
File information
File name FULLTEXT01.pdfFile size 2076 kBChecksum SHA-512
472e1cbd60e11ee6c373aad110741bbcf1fecaefe67a4c82edf64a420fcb6c220847a4974e5f587e8ef26e42a15e08f88a3aabe40aa6aadd187969226cad61e9
Type fulltextMimetype application/pdf

By organisation
School of Engineering Sciences (SCI)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 44 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf