Results 1 to 12 of 12
  1. #1
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default Best resolution timer

    I am using a call to System.nanoTime() in order to time the speeds of the elemetary sorts. However, the number fluctuates if I run the program repeatedly. What is the reason for this? Shouldn't execution time always be the same? Is there a better way to time execution speed?
    Tabish Chasmawala

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    nanoTime() returns the available system timer, in nanoseconds. Obviously when you are running your application repeatedly its not return the same. If you could post some code that you work on we can have a look at it.

  3. #3
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    Here is the code that I am implementing:

    Java Code:
    public class OrderedArray {
        
        int [] array;
        int num_elements = 0;
        int size = 0;
            
        public OrderedArray (int size)
        {
            this.size = size;
            array = new int [size];        
        }
        
        public int search (int key)
        {
            int lowerBound = 0;
            int higherBound = num_elements - 1;
            int binary = 0;
            int count = 0;
            
            while (true)
            {
                binary = (higherBound + lowerBound) / 2;
                
                if (count > num_elements)
                    return -1;
                else if (higherBound == lowerBound && array[higherBound] == key)
                    return higherBound;
                else if (array[binary] == key)
                    return binary;                
                else if (array[binary] < key)
                    lowerBound = binary + 1;
                else if (array[binary] > key)
                    higherBound = binary - 1;
                
                count += 1;
            }     
        }
        
        public void bubblesort ()
        {
            for (int i = 0; i < num_elements - 1; i++)
            {
                for (int j = 0; j < num_elements - 1; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
        
        public void selectionsort ()
        {
            int temp;
            
            for (int i = 0; i < num_elements - 1; i++)
            {
                temp = i;
                for (int j = i + 1; j < num_elements; j++)
                    if (array[j] < array[temp])
                        temp = j;
                
                int temp2 = array[i];
                array[i] = array[temp];
                array[temp] = temp2;
            }
        }
        
        
        public void insertionsort ()
        {
            boolean x;
            
            for (int i = 1; i < num_elements; i++)
            {
                int temp = array[i];
                    
                for (int j = i; j > 0; j--)
                {    
                    if (temp < array[j - 1])
                    {
                       array[j] = array[j - 1];
                       array[j - 1] = temp;                   
                    }
                    else
                    {
                        array[j] = temp;                    
                        break;
                    }            
                }              
            }
        }      
        
        public void insert (int x)
        {
            if (num_elements < size)
            {
                array[num_elements] = x;
                
                num_elements += 1;
                
            }
            else 
                System.out.println("Too many items!");     
        }
        
        public void delete (int x)
        {
            int target_element = search(x);
            
            if (target_element == -1)
                System.out.println("Number cannot be found!");
            else
            {
                array[target_element] = 0;
                
                for (int i = target_element; i < num_elements - 1; i++)
                    array[i] = array[i + 1];                
                
                array[num_elements - 1] = 0;
                num_elements -= 1;
            }            
        }   
        
        public void print (String s)
        {   
            long startTime; 
            
            if (s.equals("bubblesort"))
            {        
                startTime = System.nanoTime();
                bubblesort();
                System.out.println("Bubble Sort Time: " + (System.nanoTime() - startTime));
            } 
            else if (s.equals("selectionsort"))
            {
                startTime = System.nanoTime();
                selectionsort();
                System.out.println("Selection Sort Time: " + (System.nanoTime() - startTime));
            }
            else if (s.equals("insertionsort"))
            {
                startTime = System.nanoTime();
                insertionsort();
                System.out.println("Insertion Sort Time: " + (System.nanoTime() - startTime));
            }
            
            if (num_elements != 0)
            {
                System.out.print("[");
            
                for(int i = 0; i < num_elements - 1; i++)
                    System.out.printf("%d, ", array[i]);     
            
                System.out.printf("%d]\n", array[num_elements - 1]);     
                
            }
            else 
            {
                System.out.print("[");
            
                for(int i = 0; i < array.length - 1; i++)
                    System.out.printf("%d, ", array[i]);     
            
                System.out.printf("%d]\n", array[array.length - 1]);
            }
        }
        
        public void clear ()
        {
            for (int i = 0; i < num_elements; i++)
            {
                array[i] = 0;
            }
            num_elements = 0;
        }
    }
    To use this class, here is the app for it:

    Java Code:
    public class OrderedArrayApp {
    
        public static void main(String[] args) {
            OrderedArrayApp main = new OrderedArrayApp();
            main.initialize();
        }
    
        private void initialize() {
            
            OrderedArray array = new OrderedArray(40);        
            array.insert(63);
            array.insert(37);
            array.insert(209);
            array.insert(110);
            array.insert(96);
            array.insert(32);
            array.insert(90);
            array.insert(2);
            array.insert(4);
            array.insert(87);
            array.insert(93);
            array.insert(46);
            array.insert(98);
            array.insert(90);
            array.insert(32);
            array.insert(35);
            array.insert(53);
            array.insert(67);
            array.insert(76);
                    
            
            array.print("insertionsort");
        }
    }
    All you have to do is to type "bubblesort", "selectionsort", or "insertionsort" in the parameter of the print method that is being called in OrderedArrayApp. If you look at my print method's code, you can see that I am subtracting the time between the method start and complete times to determine the method execution time.
    Tabish Chasmawala

  4. #4
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

  5. #5
    tabchas's Avatar
    tabchas is offline Member
    Join Date
    Mar 2011
    Location
    Austin
    Posts
    60
    Rep Power
    0

    Default

    If I run 5 times consecutively, I get:

    For Bubble Sort, I get: 41052, 38734, 39066, 37742 38404
    For Selection Sort, I get: 35093, 34100, 33107, 32776, 33106
    For Insertion Sort, I get: 33438, 32114, 33107, 32776, 32114
    Last edited by tabchas; 06-14-2011 at 08:11 AM.
    Tabish Chasmawala

  6. #6
    Toll's Avatar
    Toll is offline Senior Member
    Join Date
    May 2011
    Location
    Sweden
    Posts
    393
    Rep Power
    4

    Default

    Given that all OS today (at least as far as I know) are multitasking (i.e. you can do more than one thing at once), execution time will vary slightly due to the overhead and background processes. At least that's my assumption as to why it's happening.

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,732
    Blog Entries
    7
    Rep Power
    21

    Default

    Timing isn't very accurate, at least on MS Windows machines; ignoring the fact that other tasks may steal some time before a timer can be read the accuracy is in the range +- 10ms for an MS Windows machine; nano timers aren't any better, the numbers are just multiplied by 1000000. Linux claims to be accurate to +- 1 ms. I don't know of any JVM running on a RTOS (Real Time Operating System).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    Toll's Avatar
    Toll is offline Senior Member
    Join Date
    May 2011
    Location
    Sweden
    Posts
    393
    Rep Power
    4

    Default

    I can't speak for any other Windows, but it seems like Vista has millisecond accuracy too. I know I used to get increments of 13ms or so in older versions, but right now it seems to count the milliseconds properly. At least it works properly for my framerate-thread, keeping it at 30FPS.

  9. #9
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    12,185
    Rep Power
    20

    Default

    Also note that the nature of the JVM means it can recompile code as that code runs.
    So individual timings (as you're doing above) are not all that useful.

  10. #10
    dlorde is offline Senior Member
    Join Date
    Jun 2008
    Posts
    339
    Rep Power
    7

    Default

    Timing code this way, even with sub-millisecond resolution, is notoriously difficult due to a whole range of influences, from OS loading to memory management and caching at all levels. To get anything useful, you should write code to repeatedly run each method to be timed for as long as you can bear - for example 10,000 or 100,000 times, then get the average duration to compare.

    If possible, do this with a profiling tool - they are written with this kind of measurement in mind and often use clever techniques to minimize the influence of external factors on execution time.
    Last edited by dlorde; 06-14-2011 at 02:46 PM.

  11. #11
    Toll's Avatar
    Toll is offline Senior Member
    Join Date
    May 2011
    Location
    Sweden
    Posts
    393
    Rep Power
    4

    Default

    Slightly off-topic, but if you're working with sorting algorithms, I can heartily recommend watching "Sorting out Sorting". It's an old educational movie from the 80's, and you can find it on YouTube. The qualty of the sound and video is what you'd expect from the 80's, but it's a good watch nonetheless.

  12. #12
    dlorde is offline Senior Member
    Join Date
    Jun 2008
    Posts
    339
    Rep Power
    7

    Default

    Continuing that 'ancient wisdom' line ;), Donald Knuth's 'Searching and Sorting' section from 'The Art of Programming' is a timeless classic. Here are some C implementations of sorting algorithms which shouldn't be too hard to translate: Sorting Knuth

Similar Threads

  1. Stopping a Timer from Inside the timer
    By krishnan in forum Java Applets
    Replies: 2
    Last Post: 10-05-2010, 12:15 AM
  2. Resolution of the application
    By senorita2007 in forum New To Java
    Replies: 1
    Last Post: 04-08-2010, 05:30 AM
  3. Resolution problem!
    By jan1ey in forum New To Java
    Replies: 1
    Last Post: 03-03-2009, 08:36 AM
  4. Replies: 0
    Last Post: 04-04-2008, 03:46 PM
  5. How to change the resolution ?
    By samson in forum Java 2D
    Replies: 1
    Last Post: 07-17-2007, 12:15 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •