Izziv 1

Eksperimentalno ovrednotenje zahtevnosti

V programskem jeziku java ali C++ napišite program za empirično primerjavo dveh algoritmov za iskanje elementa v urejeni tabeli:

• navadnega zaporednega iskanja in
• dvojiškega iskanja.

Oba algoritma poženite večkrat za različne velikosti tabele. Pri tem izmerite in izračunajte povprečni čas iskanja. Izpišite čase za oba algoritma. Predlagamo, da izziv rešujete postopoma po naslednjih točkah.

a) Generiranje testnih primerov

Za generiranje testnih primerov napišite metodo (oz. funkcijo), ki vam za podani n vrne (urejeno) tabelo celih števil z vrednostmi od 1 do n. Na primer:

• int[] generateTable(int n)
• vector<int> generateTable(int n)

b) Implementacija obeh algoritmov iskanja elementa

Napišite oba algoritma za iskanje elementa. Na primer:

• int findLinear(int[] a, int v)
• int findLinear(const vector<int>& a, int v)
• int findBinary(int[] a, int l, int r, int v)
• int findBinary(const vector<int>& a, int l, int r, int v)

Pri tem je a tabela elementov, v iskana vrednost, l leva meja v tabeli, r desna meja v tabeli, vrnemo pa mesto (indeks), kjer se element v nahaja. Kakšno vrednost imata l in r ob prvem klicu metode findBinary?

c) Izvedba enega testa za tabelo dolžine n

Napišite metodi (za vsak način iskanja svojo metodo), ki izmerita povprečni čas iskanja v tabeli dolžine n. Na primer:

• long timeLinear(int n)
• long timeBinary(int n)

Vsaka izmed metod naj izvede naslednje:

• Ustvari tabelo dolžine n z metodo, ki ste jo implementirali predhodno.
• Začne meriti čas.
• Nato 1000-krat ponovi naslednje:
• Ustvari naključno število med 1 in n.
• Poišče število v tabeli.
• Ustavi merjenje časa.
• Izračuna povprečje.

Čas izvajanja v javi merite na sledeči način:

long startTime = System.nanoTime();
// iskanje elementa
long executionTime = System.nanoTime() - startTime;
  

V C++ merite čas takole:

#include <chrono>
using namespace std::chrono;
...
auto begin = high_resolution_clock::now();
// iskanje elementa
auto end = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(end - begin);
// čas v mikrosekundah pridobimo z duration.count()
  

d) Eksperimentalno ovrednotenje algoritmov

Na učilnico oddajte izvorno kodo (datoteko .java ali .cpp, ne .zip!) te naloge.

Za vrednosti n od $10^3$ do $10^5$ s korakom po $10^3$ tabelirajte povprečni čas izvajanja. Izpišite tabelo s tremi stolpci:

• prvi stolpec naj vsebuje n,
• drugi naj vsebuje povprečni čas izvajanja navadnega iskanja,
• tretji pa povprečni čas dvojiškega iskanja.

Primer izpisa:

     n   |     linearno  |    dvojisko |
---------+--------------+--------------+
    1000 |          662 |           41 |
    2000 |         1444 |           46 |
    3000 |         2135 |           50 |
    4000 |         2706 |           47 |
    5000 |         3433 |           52 |
    6000 |         3751 |           51 |
     ...            ...            ...
  

e) Razmislite

• Zakaj so časi pri vas drugačni kot v zgornji tabeli?
• Kateri algoritem je hitrejši?
• Kdaj bi lahko bil počasnejši algoritem hitrejši?
• Kako je čas odvisen od velikosti naloge (linearno, kvadratno, ...)?
• Je časovna odvisnost dvojiškega iskanja bližje linearni ali konstantni?

f) Grafični prikaz -- neobvezno, a zabavno in poučno

Narišite graf zgoraj izmerjenih vrednosti časa izvajanja v odvisnosti od dolžine tabele. Za izris priporočamo uporabo knjižnice StdLib in razreda StdDraw. Za barvno izvedbo morate dodati 6 vrstic v zgornjo rešitev.

V skrajni sili lahko uporabite tudi druge možnosti:

• Uporabite lahko program za izdelavo razpredelnic (OpenOffice, Excel, ...).
• Izris neposredno iz jave z uporabo enostavne knjižnice jMathPlot. Na povezavi najdete enostaven uvod v uporabo te knjižnice.
• itd.