Matkapuhelimen puhelinmuistiopalvelimen tietorakenteiden ja lajittelualgoritmien analysointi ja suunnittelu

Abstract

Puhelinmuistio on yksi matkapuhelimen käytetyimmistä ominaisuuksista. Puhelinmuistion tulee siksi olla kaikissa tilanteissa mahdollisimman nopeasti käytettävissä. Tämä edellyttää puhelinmuistiopalvelimelta tehokkaita tietorakenteita ja lajittelualgoritmeja. Nokian matkapuhelimissa puhelinmuistiopalvelin käyttää hakurakenteena järjestettyjä taulukoita. Työn tavoitteena oli kehittää puhelinmuistiopalvelimen hakutaulukoiden lajittelu mahdollisimman nopeaksi. Useita eri lajittelualgoritmeja vertailtiin ja niiden suoritusaikoja analysoitiin eri tilanteissa. Insertionsort-lajittelualgoritmin todettiin olevan nopein algoritmi lähes järjestyksessä olevien taulukoiden lajitteluun. Analyysin perusteella Quicksort-algoritmi lajittelee nopeimmin satunnaisessa järjestyksessä olevat taulukot. Quicksort-insertionsort –hybridialgoritmin havaittiin olevan paras lajittelualgoritmi puhelinmuistion lajitteluun. Sopivalla parametroinnilla tämä algoritmi on nopea satunnaisessa järjestyksessä olevalle aineistolle. Se kykenee hyödyntämään lajiteltavassa aineistossa valmiina olevaa järjestystä. Algoritmi ei kasvata merkittävästi muistinkulutusta. Uuden algoritmin ansiosta hakutaulukoiden lajittelu nopeutuu parhaimmillaan useita kymmeniä prosentteja.

Phonebook is one of the most used feature in mobile phone. Therefore it is of primary importance that phonebook is always ready to use as soon as possible. Clearly phonebook server must have efficient data structures and sorting algorithms to be able to offer this. The phonebook server of Nokia's mobile phone uses fixed-length sorted arrays as search structure. The goal of the thesis was to develop the sorting of search arrays in phonebook server to run as fast as possible. Many sorting algorithms was compared and their running time was analyzed in various situations. Insertionsort sorting algorithm was realized to sort nearly sorted arrays the most quickly. The analysis showed that quicksort is the fastest sorting algorithm for arrays in random order. Quicksort-insertionsort hybrid algorithm was found to be the fastest algorithm to sort the phonebook in mobile phone. After parameterizing this algorithm properly it is the fastest algorithm for random input. It can utilize the presortedness of the array to be sorted. The algorithm does not increase memory consumption substantially. The new algorithm speeds up the sorting of search arrays dozens of per cent at its best.