0

I want to measure time execution of licz() function which calls two more functions. Am I using window.performance.now(); in the right way? Because whether I set size of the array 100, 1000 or 10000 the time shows 0 or 1 ms. There's something wrong with it. Does someone have any idea? I'd like to make a diagram depending on time execution and size of the array but firstly I need to figure out why it doesn't work to me correctly. Don't pay attention on polish names... I care about this time.

//generator tablicy
    var size = 10000; // rozmiar tablicy
    var max = 100; // maksymalna możliwa liczba do wylosowania
    var tab = [];
    
    for(k=0; k<size; k++)
    {
        input = Math.floor(Math.random() * max) + 1;
        tab[k] = input;
    }
    tab.sort(function(a, b) {return a - b;}); // uporządkowanie tablicy
    //------------------------------------------------
    
    
    function licz(tab, w, n)
    {
        //indeks pierwszego wystąpienia "w"
        idMin = pierwszy(tab, 0, n-1, w, n);
        
        //jeśli "w" nie istnieje w tablicy
        if (idMin == -1){return idMin};
        
        //indeks ostatniego wystąpienia
        idMax = ostatni(tab, idMin, n-1, w, n);
        ile = idMax-idMin+1;
        //zwracamy ilość powtórzeń wartości "w"
        return ile;
    }
    
    function pierwszy(tab, l, p, w, n) //indeks pierwszego wystąpienia
    {
        if(l <= p) //l - początek zakresu listy p - koniec zakresu listy
        {
            mid = Math.floor((l+p)/2); //środkowy indeks, zaokrąglamy w dół gdy l;p to lista z parzystą liczbą elementów
            
            if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) //mid == 0 gdy tablica ma 1 element
            {
                return mid; // zwraca indeks pierwszego wystapienia
            }
            else if(w > tab[mid])
            {
                return pierwszy(tab, (mid+1), p, w, n);
            }
            else
            {
                return pierwszy(tab, l, (mid-1), w, n);
            }
        }
        return -1;
    }
    
    function ostatni(tab, l, p, w, n)//indeks ostatniego wystąpienia
    {
        if(l <= p)
        {
            mid2 = Math.floor((l+p)/2);
                
            if((mid2 == n-1 || w < tab[mid2+1]) && (tab[mid2] == w))
            {
                return mid2; //zwraca indeks ostatniego wystąpienia
            }
            else if(w < tab[mid2])
            {
                return ostatni(tab, l, (mid2-1), w, n);
            }
            else
            {
                return ostatni(tab, (mid2+1), p, w, n);
            }
        }   
    }
    
    //Wywołanie funkcji
    w = 49; // szukana wartość
    n = tab.length; // długość tablicy
    
    var start = window.performance.now();
    ilosc = licz(tab, w, n); // zwraca liczbe powtórzeń szukanej wartośći w tablicy
    var end = window.performance.now();
    
    if(ilosc == -1)
    {
        document.write("Wartość "+w+" pojawiła się 0 razy<br/>");
    }
    else
    {
        document.write("Wartość "+w+" pojawiła się "+ilosc+" raz/razy<br/>");
    }

    console.table(tab); // wypisanie tablicy
    console.log(`Time execution: ${end - start} ms`);
2
  • Pretty sure that just means your code is running really fast. Or your browser is set to "resist fingerprinting" which - among other things - reduces the precision of performance.now to the nearest 100ms. Commented Jan 30, 2021 at 16:08
  • Use: console.time("My 1st test"); /* YOUR TEST HERE */ console.timeEnd("My 1st test"); Commented Jan 30, 2021 at 16:10

1 Answer 1

1

I think this time it's not a problem of code but of user protection.

This might be fast enough to execute that you are always less than 1ms and if the precision is more than that then you are always gonna get 0ms or 1ms.

What this means is that until you crank up the number of iterations to a lot more you are not gonna see the real time it takes. It could be for a different reason but I can't really figure out your code and I'm under the impression it's a binary search. This means that until you go some order of magnitudes more elements you are not gonna see the difference in time.

Binary search is log2(n) so just adding one zero (meaning n is now 10 * n) is not gonna cut it.

Sign up to request clarification or add additional context in comments.

4 Comments

Alright, so to see a difference I should mostly increase size of the array or max value that can be draw and put into array?
Just the size of the array but before you should confirm the running time of the algorithm, if it's really a log2(n) it would make sense to increase the array size as it's n = tab.length(). In the code it's the size variable to change.
Yes, time complexity is logn. second and third function is logn and first just O(1) so generally there's O(logn). Only after increasing size by 10 000 000 element I see some difference in ms so I guess it's pretty fast algorithm.
yep that would fit the idea as 10'000'00 ~ 10 * 2^20 and this would make it do at least 20 steps more so it's not that much more but it should be visible i your benchmarks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.