Getting the Run Time of a Program

So now we know the selection sort algorithm works. But the data sets we've been giving it to sort are tiny. In the real world, algorithms need to work with data sets of tens of thousands or even millions of items, and do it fast.

• I have another file with 10,000 random numbers in it.
• Let's see if selection sort can handle that.
• Now, let's run the program again, on the 10000.txt file, and see how long it takes.

python selection_sort.py numbers/10000.txt

• It prints out all 10,000 of those numbers, neatly sorted.
• It took a little bit, though. How long? Well, counting the time off vocally isn't very precise. And other programs running on the system can skew the amount of time your program takes to complete.
• Let me show you a Unix command that's available here in Workspaces which can help.
• You type time, followed by a space, and then the command you want to run.
• So this command by itself will print the contents of our 5.txt file:

cat numbers/5.txt

• And this command will do the same thing, but it will also keep track of how long it takes the cat program to complete, and report the result.

time cat numbers/5.txt

real    0m0.006s
user    0m0.001s
sys     0m0.003s

• The real row in the results is the actual amount of time from when the program started running to when it completed. We can see it finished in a fraction of a second. But as we said, other programs running on the system can take CPU resources, in which case your program will seem slower than it is. So we generally want to ignore the real result.
• The user result is the amount of time the CPU actually spent running the program code. So this is the total amount of time the code inside the cat program took to run.
• The sys result is the amount of time the CPU spent running Linux kernel calls that your code made. The Linux kernel is responsible for things like network communications and reading files. So loading the 5.txt file is probably included in this result.

In evaluating code's performance, we're generally going to want to add together the user and sys values.

But cat is a very simple program. Let's try it on our code and see if we get a more interesting result.

time python selection_sort.py numbers/10000.txt

real    0m7.667s
user    0m4.505s
sys     0m0.047s

• This takes much longer to complete. Almost 8 seconds, according to the real time measurement. But as we said, the real result is often skewed, so let's disregard that.
• If we add the user and sys run times together, we get about 5 seconds.
• The time for the program to complete will vary a little bit each time you run it, but if it's doing the same operations it usually won't change more than a fraction of a second. If I run our selection sort script on the same file, you can see it completes in roughly the same time.