Re: More accurate time feedback
On Wed, Oct 24, 2001 at 06:29:39PM -0500, Ian Patrick Thomas wrote: Is there a way to get a more accurate time value, preferably to a nanosecond, using the system clock? I need to write a program that needs to output the time it takes various sorting algprithms to sort various numbers of integers. For smaller numbers of integers on algorithms like quicksort, and mergesort, I am getting 0 for the runtime. I need a function that I can call before the sort begins and after it ends that would return a time value, preferably to the nanosecond. Is there a library out there that can do this or is the answer right on my machine and I just haven't found it yet? The standard way of handling this is to use a large data set and shuffle/re-sort it many (like, say, 10,000) times. In addition to making the time more easily measurable, this also avoids the possibility of your test returning incorrect results because of anomalies in the data's original order. (e.g., if your shuffled data just happens to be in order already, a bubblesort is likely to be faster than a quicksort.) If you are required to use a small data set, just perform more repetitions to get measurable data. -- When we reduce our own liberties to stop terrorism, the terrorists have already won. - reverius Innocence is no protection when governments go bad. - Mr. Slippery
Re: More accurate time feedback
Dave Sherohman writes: On Wed, Oct 24, 2001 at 06:29:39PM -0500, Ian Patrick Thomas wrote: to a nanosecond, using the system clock? I need to write a program that needs to output the time it takes various sorting algprithms to sort various numbers of integers. For smaller numbers of integers on algorithms like quicksort, and mergesort, I am getting 0 for the runtime. I need a function that I can call faster than a quicksort.) If you are required to use a small data set, just perform more repetitions to get measurable data. This also allows you to obtain statistics like standard deviations and confidence intervals. Andrew.
Re: More accurate time feedback
On Thu, Oct 25, 2001 at 09:06:29AM -0700, Andrew Agno wrote: Dave Sherohman writes: faster than a quicksort.) If you are required to use a small data set, just perform more repetitions to get measurable data. This also allows you to obtain statistics like standard deviations and confidence intervals. Umm... No. If you run 10,000 reps and only measure the total time (because each rep is too quick to be measured individually), you can only determine the mean time per rep. You'd need the individual rep times to derive any other stats, unless there are some fancy techniques that I'm not aware of. (If you do 2 reps and only measure that the total time is 10 ms, you have no way of knowing whether the individual times were 5 ms and 5 ms or 1 ms and 9 ms. This makes computing anything other than the mean rather difficult.) -- When we reduce our own liberties to stop terrorism, the terrorists have already won. - reverius Innocence is no protection when governments go bad. - Mr. Slippery
RE: More accurate time feedback
-Original Message- From: Dave Sherohman [mailto:[EMAIL PROTECTED] Sent: Thursday, October 25, 2001 12:58 PM To: debian-user@lists.debian.org Subject: Re: More accurate time feedback On Thu, Oct 25, 2001 at 09:06:29AM -0700, Andrew Agno wrote: Dave Sherohman writes: faster than a quicksort.) If you are required to use a small data set, just perform more repetitions to get measurable data. This also allows you to obtain statistics like standard deviations and confidence intervals. Umm... No. If you run 10,000 reps and only measure the total time (because each rep is too quick to be measured individually), you can only determine the mean time per rep. You'd need the individual rep times to derive any other stats, unless there are some fancy techniques that I'm not aware of. (If you do 2 reps and only measure that the total time is 10 ms, you have no way of knowing whether the individual times were 5 ms and 5 ms or 1 ms and 9 ms. This makes computing anything other than the mean rather difficult.) You might run many batches of 1,000 reps. The statistics of that population would be useful, if the error in the time measurement is small enough.
Re: More accurate time feedback
On Wed, Oct 24, 2001 at 06:29:39PM -0500, Ian Patrick Thomas wrote: | Is there a way to get a more accurate time value, preferably to a | nanosecond, using the system clock? I need to write a program that needs to | output the time it takes various sorting algprithms to sort various numbers | of integers. For smaller numbers of integers on algorithms like quicksort, | and mergesort, I am getting 0 for the runtime. I need a function that I can | call before the sort begins and after it ends that would return a time | value, preferably to the nanosecond. Is there a library out there that can | do this or is the answer right on my machine and I just haven't found it | yet? One way is to use a dataset that is big enough to measure. If you encapsulate the algorithm in an application (that is, something that can be run as a process) then the 'time' program can do all the measuring for you. Otherwise you need to determine what sort of time measuring stuff is available for the development environment you are using. For example, if you are using python : #!/usr/bin/env python import random import time def qsort( data ) : for i in xrange( random.randint( 5 , 10 ) ) : time.sleep( 1 ) # take up time as if we did something useful def mergesort( data ) : for i in xrange( random.randint( 5 , 10 ) ) : time.sleep( 1 ) # take up time as if we did something useful start = time.time() qsort( [ some data ] ) end = time.time() print qsort took %d units of time % (end - start) start = time.time() mergesort( [ some data ] ) end = time.time() print mergesort took %d units of time % (end - start) $ time ./test.py # demonstrating both at once qsort took 6 units of time mergesort took 5 units of time real0m17.047s user0m0.040s sys 0m0.000s $ From the python docs : time() Return the time as a floating point number expressed in seconds since the epoch, in UTC. Note that even though the time is always returned as a floating point number, not all systems provide time with a better precision than 1 second. HTH, -D
