Dzień dobry, robię właśnie zadanie na zajęcia z algorytmów. Moim zadaniem jest szukanie jakiegoś elementu tablicy z wykorzystaniem algorytmu interpolacyjnego. Mam to zrobić dla 10 tablic o różnych rozmiarach (100 000, 300 000 itd, mało istotne) i zmierzyć czas działania algorytmu i potem te czasy porównać za pomocą wykresu. Ogólnie wszystko mam już zrobione tak jak ma być, problem jednak leży w mierzeniu czasu. Czas mierzę w nanosekundach aby był jak najdokładniejszy i zamieniam go na sekundy z dokładnością do 6 miejsc po przecinku. Pobieram czas przed algorytmem i drugi raz zaraz po zakończeniu algorytmu. Następnie odejmuję te czasy od siebie i wyświetlam. Teoretycznie co może iść nie tak? Wszystko powinno być ok, jednak nie wiem dlaczego czasy są wyświetlane jakby randomowo. Prawidłowo czasy powinny rosnąć w każdej kolejnej tablicy, a tak się nie dzieje... Przy pierwszym mierzeniu czasu, obojętnie jaka by to nie była tablica, dla testów dałem nawet tablice 600 elementową, a wynik zawsze jest baaardzo duży. Dopiero za drugim razem jest w miarę normalny. Jednak raz wynik jest wiekszy, raz mniejszy, mimo tego, że cały czas powinny rosnać... Moi koledzy mają dokładnie to samo i nie potrafimy sobie z tym poradzić.
Wie ktoś może o co chodzi? Bo już nie mam siły do tego... Nie widzę tu nic co by mogło powodować ten błąd. Oto kod i wyniki w załączniku.
package javaapplication7;
public class JavaApplication7 {
public static void zapelnij_tablice(int[] tab)
{
int k=0;
for(int i=0;i<tab.length;i++)
{
tab[k]=i;
k++;
}
}
static int interpolationSearch(int[] tab, int x)
{
int lo = 0, hi = (tab.length - 1);
while (lo <= hi && x >= tab[lo] && x <= tab[hi])
{
int pos = lo + (((hi-lo) /
(tab[hi]-tab[lo]))*(x - tab[lo]));
if (tab[pos] == x)
return pos-1;
if (tab[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
static void Sprawdzenie(int[] tab)
{
int x=20000;
int index=interpolationSearch(tab, x);
if(index!=-1)
{
System.out.println("Element znaleziony przy indeksie: "+index);
}
else System.out.println("Element nie został znaleziony.");
}
static void IleCzasu(int[] tab)
{
double poczatek=System.nanoTime();
Sprawdzenie(tab);
//System.out.println("Czas sortowania: "+ (System.nanoTime()-poczatek));
System.out.format("Czas sortowania: [s] %.6f%n", ((System.nanoTime() - poczatek) / 1000000000));
System.out.println();
}
public static void main(String[] args) {
int n=3;
int wartosc=100000;
int[] tablica= new int [1*n*wartosc];
int[] tablica2= new int [2*n*wartosc];
int[] tablica3= new int [3*n*wartosc];
int[] tablica4 = new int[4*n*wartosc];
int[] tablica5 = new int[5*n*wartosc];
int[] tablica6 = new int[6*n*wartosc];
int[] tablica7 = new int[7*n*wartosc];
int[] tablica8 = new int[8*n*wartosc];
int[] tablica9 = new int[9*n*wartosc];
int[] tablica10 = new int[10*n*wartosc];
zapelnij_tablice(tablica);
IleCzasu(tablica);
zapelnij_tablice(tablica2);
IleCzasu(tablica2);
zapelnij_tablice(tablica3);
IleCzasu(tablica3);
zapelnij_tablice(tablica4);
IleCzasu(tablica4);
zapelnij_tablice(tablica5);
IleCzasu(tablica5);
zapelnij_tablice(tablica6);
IleCzasu(tablica6);
zapelnij_tablice(tablica7);
IleCzasu(tablica7);
zapelnij_tablice(tablica8);
IleCzasu(tablica8);
zapelnij_tablice(tablica9);
IleCzasu(tablica9);
zapelnij_tablice(tablica10);
IleCzasu(tablica10);
}
}
- dziwne.png (21 KB) - ściągnięć: 91
Shalomautomatically eliminate noise due to JIT compilation, garbage collection or undesired heap allocation patterns