{"id":2367,"date":"2011-08-10T08:26:15","date_gmt":"2011-08-10T08:26:15","guid":{"rendered":"http:\/\/cemclinux1.math.uwaterloo.ca\/~cscircles\/wordpress\/?page_id=2367"},"modified":"2011-08-10T08:26:15","modified_gmt":"2011-08-10T08:26:15","slug":"18-efficiency","status":"publish","type":"page","link":"https:\/\/olescs.hkmu.edu.hk\/python\/18-efficiency\/","title":{"rendered":"18: Efficiency"},"content":{"rendered":"<!-- Please retain this notice and add more notes if you create a new version.<br \/>\nOriginal lesson author: David Pritchard, daveagp@gmail.com, http:\/\/cscircles.ca<br \/>\nLicense: http:\/\/creativecommons.org\/licenses\/by-nc-sa\/3.0\/-->\n<p>Many programming tasks can be done in more than one way, but one way might be much faster than another. Designing fast programs is part of the art and science of computer programming. We look at a couple of examples in this exercise.<\/p>\n<h1>Part 1: Don't Recompute The Same Thing Twice<\/h1>\n<p>The <a href=\"http:\/\/en.wikipedia.org\/wiki\/Fibonacci_number\">Fibonacci numbers<\/a> are a fascinating and simple sequence of numbers. You start with two numbers, 1 and 1. Then the rule is, <em>to get the next number, add the previous two<\/em>. Therefore, the next number is 1+1=2. This gives the first three terms,<\/p>\n<p style=\"text-align: center\"><code>1, 1, 2<\/code><\/p>\n<p>and the fourth term is 1+2=3, then we have 2+3=5, and so forth:<\/p>\n<p style=\"text-align: center\"><code>1, 1, 2, 3, 5, 8, 13, ...<\/code><\/p>\n<p>The Fibonacci sequence was originally invented to talk about rabbit populations, and it has fantastic connections to the architecture of plants. Here is part of an awesome video series about the Fibonacci numbers: <div style='text-align: center;'>\n<iframe width='560' height='315' src='https:\/\/www.youtube.com\/embed\/ahXIMUkSXX0?rel=0' frameborder='0' allowfullscreen>\n<\/iframe>\n<\/div>\n<p>The definition of the Fibonacci numbers lends itself naturally to a recursive function. The next exercise defines a function <code>Fibonacci(n)<\/code> to give the <code>n<\/code>th item in the list above (starting from <code>n=1<\/code>).<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform0\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox0'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>Nibofacci<\/span><\/div>Unscramble this program so that it gives a recursive definition of the Fibonacci numbers. The grader will print out the first ten of them.<ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble0\">\n <li class=\"pyscramble\">def Fibonacci(n):<\/li>\n <li class=\"pyscramble\">        return 1<\/li>\n <li class=\"pyscramble\">    else:<\/li>\n <li class=\"pyscramble\">    if (n==1 or n==2):<\/li>\n <li class=\"pyscramble\">        return Fibonacci(n-1) + Fibonacci(n-2)<\/li>\n<\/ul>\n<input type='hidden' id='usercode0' name='usercode0'\/>\n<div id='pbhistory0' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput0\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit0' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch0\" value=\"Input Switch\" onclick=\"pbInputSwitch(0,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse0\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"0\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"771d5db1d831345d1541a0f9df133ac8\"\/>\n<div id='pbresults0' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(0,\"Y\");<\/script>\n<\/p>\n<p>However, this recursive function becomes too slow to compute entries further down the sequence. Press <strong>Enter test statements<\/strong> and type <code>print(Fibonacci(80))<\/code>. When you test it, you get \"Time Limit Exceeded.\"<\/p>\n<p>Why is it going so slowly? The function has no complicated instructions or loops, just addition. So the slowness turns out to be related to the number of total calls to the function. If we call <code>Fibonacci(3)<\/code>, the recursive function is called three times in total: the initial call, then two recursive calls. If we call <code>Fibonacci(4)<\/code>, the recursive function is called five times: the initial call, the three times just mentioned for <code>n=3<\/code>, and one more recursive call with <code>n=2<\/code>. Computing <code>Fibonacci(5)<\/code> makes a total of nine calls, and <code>Fibonacci(6)<\/code> makes a total of 9+5+1=15 calls. The number of calls gets very large very quickly as <code>n<\/code> grows!<\/p>\n<p>As a rough estimate, <code>Fibonacci(n+2)<\/code> requires at least twice as many total recursive calls as <code>Fibonacci(n)<\/code>, since <code>Fibonacci(n+2)<\/code>\u00a0calls <code>Fibonacci(n)<\/code> once directly, and another time indirectly through the recursive call to <code>Fibonacci(n+1)<\/code>. So the computing time is proportional to an <em>exponential function<\/em>\u00a0at least as large as (\u221a2)<sup>n<\/sup>. This is too slow! E.g., <code>Fibonacci(80)<\/code> requires more than 2<sup>40<\/sup> =\u00a01099511627776 recursive calls.<\/p>\n<p>This argument even outlines the exact conceptual problem: calling\u00a0<code>Fibonacci(n)<\/code> twice and re-computing the answer from scratch the second time is wasteful. We should come up with some approach where we don't waste time re-computing the same thing over and over again.<\/p>\n<h2>The solution<\/h2>\n<p>Let's try doing something in Python more similar to the introduction. We started by writing down 1, 1. Then we kept extending the sequence by adding the last two elements together. Here is what the code looks like; again, it's up to you to unscramble it.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform1\" method=\"POST\">\n<div class='pybox modeNeutral scramble' id='pybox1'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Scramble Exercise: <\/span><span class='title'>Fast Fibonacci<\/span><\/div>Unscramble the fast version to compute larger Fibonacci values.<ul class=\"pyscramble\" name=\"pyscramble\" id=\"pyscramble1\">\n <li class=\"pyscramble\">        sequence.append(sequence[i-1] + sequence[i-2])<\/li>\n <li class=\"pyscramble\">    return sequence[n]<\/li>\n <li class=\"pyscramble\">def Fibonacci(n):<\/li>\n <li class=\"pyscramble\">    for i in range(3, n+1):      <\/li>\n <li class=\"pyscramble\">    sequence = [0, 1, 1]  # Fibonacci(0) is 0, Fibonacci(1) and Fibonacci(2) are 1<\/li>\n<\/ul>\n<input type='hidden' id='usercode1' name='usercode1'\/>\n<div id='pbhistory1' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput1\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit1' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch1\" value=\"Input Switch\" onclick=\"pbInputSwitch(1,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse1\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"1\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"142dda911985eef1c235b123ab62a5ad\"\/>\n<div id='pbresults1' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(1,\"Y\");<\/script>\n<\/p>\n<p>There is still a little room for improvement, since we don't need to re-compute the whole array in each new call, but this is good enough since it runs quickly even on large values of n!<\/p>\n<h1>Part 2: Don't Compute Unnecessary Things, Even Once<\/h1>\n<p>Our second example is about checking whether numbers are <strong>prime<\/strong>, which is important in cryptography and computer security. A number is prime if it has exactly two factors: 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23. (For example, 21 is not prime because it has factors 3 and 7 as well as 1 and 21.)<\/p>\n<p>How can we test whether a number is prime in Python? We saw <a href=\"\/7b-math\/\">earlier<\/a> how to test divisibility:<\/p>\n<p style=\"text-align: center\"><code>N % D == 0 \u00a0# will be True if D is a divisor of N, False otherwise<\/code><\/p>\n<p>So by testing all possible divisors, we arrive at the following program.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform2\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox2'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Testing whether a few numbers are prime<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 162px;'><textarea wrap='off' name='usercode2' id='usercode2'  cols=10 rows=6 readonly='readonly'  style = 'height : 162px;'  class='pyboxCode RO'>\ndef isItPrime(N):\n  for D in range(2, N):                        # test D from 2 to N-1\n    if N % D == 0:                             # is D a divisor of N?\n      print(N, \"is not prime; divisible by\", D)\n      return\n  print(N, \"is prime\")                         # there were no divisors<\/textarea><\/div>\n<div id='pbhistory2' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput2\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit2' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch2\" value=\"Input Switch\" onclick=\"pbInputSwitch(2,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(2)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(2,'Y')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse2\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"2\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"6c26fa224dbd58cfcb868c800ad7b407\"\/>\n<div id='pbresults2' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>pbInputSwitch(2,\"Y\");<\/script>\n<\/p>\n<p>It works! But it is also too slow on large numbers. Pick <strong>Enter input<\/strong> and type <code>isItPrime(324635459)<\/code>. It runs out of time. Try some more values... for primes greater than about 10000000 the code always runs out of time, because the grader can only execute the divisibility-checking loop about 10 million times per second. If we want to check larger numbers, we will need a more efficient idea. Let's make the code work even for numbers as big as a trillion (1000000000000)!<\/p>\n<p>Do we really need to check <strong>all<\/strong> of the numbers between <code>2<\/code> and <code>N-1<\/code>, to check if <code>N<\/code> is prime? <a class=\"hintlink\"  id=\"hintlink3\">Hint<\/a><\/p>\n<h2>The idea, and an argument<\/h2>\n<p>If you read the hint and experimented, you might have noticed that when <code>N<\/code> is not prime, the program usually found a pretty small factor compared to <code>N<\/code>. For example, <code>isItPrime(34827948723948723984729834)<\/code> runs pretty quickly even though its input is gigantic, finding the divisor <code>D=2<\/code>.<\/p>\n<p>Maybe we don't actually need to check all possible factors. Is there some small limit to the number of factors we need to check, before we can be sure that <code>N<\/code> is prime? Thankfully, yes! In fact we can argue that\u00a0<em>if <\/em><code>N<\/code><em> is not prime, one of its divisors is at most <\/em><code>sqrt(N)<\/code>.\u00a0Why? Well, if <code>N<\/code> is not prime, then it has a divisor <code>A<\/code>. Being a divisor means that there is some other number <code>B<\/code> such that<\/p>\n<p style=\"text-align: center\"><code>A*B == N<\/code><\/p>\n<p>Let's continue the argument. If <code>A &lt;= sqrt(N)<\/code> or <code>B &lt;= sqrt(N)<\/code>, then we are happy: we found a factor of <code>N<\/code> that is small, like we wanted. But actually these are the only possibilities: otherwise we get the impossible contradiction<\/p>\n<p style=\"text-align: center\"><code>N = A*B &gt; sqrt(N)*sqrt(N) = N<\/code><\/p>\n<p>Great! So now, let's implement this new idea in Python. The easiest way to change the old approach is to add a test within the <code>for<\/code> loop: once <code>D &gt; sqrt(N)<\/code> (or equivalently, <code>D*D &gt; N<\/code>), we can just <code>break<\/code> out of the loop and stop testing.<\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform4\" method=\"POST\">\n<div class='pybox modeNeutral  facultative' id='pybox4'>\n<div class=\"heading\"><span class=\"title\">Example<\/span><\/div>Faster primality checking<div class='pyboxTextwrap pyboxCodewrap RO '  style='height: 292px;'><textarea wrap='off' name='usercode4' id='usercode4'  cols=10 rows=11 readonly='readonly'  style = 'height : 292px;'  class='pyboxCode RO'>\ndef isItPrime(N): # same as before\n  for D in range(2, N):\n    if (D * D > N):          # first added line\n      break                  # second added line\n    if N % D == 0:\n      print(N, \"is not prime; divisible by\", D)\n      return\n  print(N, \"is prime\")\n\nisItPrime(1000006000009)\nisItPrime(1666666009999)<\/textarea><\/div>\n<div id='pbhistory4' class='flexcontain' style='display:none;'><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit4' value=' '\/><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(4)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(4,'N')\" ><\/td>\n<\/tr><\/table><\/div>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse4\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"4\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"87782243ae066971c8870ad20d35c7d1\"\/>\n<div id='pbresults4' class='pbresults'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>document.getElementById(\"submit4\").value = \"Run program\";document.getElementById(\"inputInUse4\").value = \"N\";<\/script>\n<\/p>\n<p>The program now works on gigantic primes!<\/p>\n<h2>Final Exercise<\/h2>\n<p>In this exercise, we combine the primes from the second half of the lesson with the list-based approach of the first half.\u00a0Your code should fill out a table of length 1000001 so that\u00a0<code>isPrime[N]<\/code>\u00a0equals\u00a0<code>True<\/code> if <code>N<\/code> is prime, and <code>False<\/code> if <code>N<\/code> is composite, for all <code>N<\/code> up to one million.\u00a0(<code>isPrime[0]<\/code> and <code>isPrime[1]<\/code> should be <code>False<\/code>.)<\/p>\n<p><a class=\"hintlink\"  id=\"hintlink5\">Click here for a hint. It's a big one!<\/a><\/p>\n<p><form class=\"pbform\" action=\"#\" id=\"pbform6\" method=\"POST\">\n<div class='pybox modeNeutral ' id='pybox6'>\n<img title='You have not yet completed this problem.' src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/icon.png' class='pycheck'\/><div class=\"heading\"><span class='type'>Coding Exercise: <\/span><span class='title'>Primed for Takeoff<\/span><\/div>Write a program that defines the table <code>isPrime<\/code> we described above (notice that <code>isPrime<\/code> is a list, not a function). <a class=\"hintlink\"  id=\"hintlink7\">Hint<\/a><br\/> <em>The grader will allow a longer-than-usual amount of time, <strong>7 seconds<\/strong>, for your program to execute. However, simply using the <\/em><code>isItPrime<\/code><em> function will not be fast enough.<\/em><div class=\"helpOuter\" style=\"display: none;\"><div class=\"helpInner\"><div style=\"text-align: center\">You need to create an account and log in to ask a question.<\/div><\/div><\/div><div class='pyboxTextwrap pyboxCodewrap RW resizy'  style='height: 526px;'><textarea wrap='off' name='usercode6' id='usercode6'  cols=10 rows=20   class='pyboxCode RW'>\n# delete this comment and enter your code here\n<\/textarea><\/div>\n<div id='pbhistory6' class='flexcontain' style='display:none;'><\/div>\n<div name=\"pyinput\" id=\"pyinput6\">Enter testing statements like <code>print(myfunction(\"test argument\"))<\/code> below.<div class=\"pyboxTextwrap resizy\" style=\"height: 102px;\" ><textarea wrap=\"off\" name=\"userinput\" class=\"pyboxInput\" cols=10 rows=4><\/textarea><\/div><\/div>\n<div class='pyboxbuttons'><table><tr>\n<td><input type='submit' name='submit' id='submit6' value=' '\/><\/td>\n<td><input type='button' name='switch' id=\"switch6\" value=\"Input Switch\" onclick=\"pbInputSwitch(6,'Y')\" ><\/td>\n<td><input type='button' name='consolecopy' value=\"Open in console\" onclick=\"pbConsoleCopy(6)\" ><\/td>\n<td><input type='button' name='visualize' value=\"Visualize\" onclick=\"pbVisualize(6,'Y')\" ><\/td>\n<\/tr><\/table><select id='pbSelect6' class='selectmore'><option name='more'>More actions...<\/option>\n<option name='history' data-pbonclick=\"historyClick(6,'18.sieve')\" >History<\/option>\n<option name='help' data-pbonclick=\"helpClick(6);\" >Help<\/option>\n<\/select><\/div>\n<input type='hidden' name='timeout' value='20000'\/>\n<input type=\"hidden\" name=\"lang\" value=\"en-US\"\/><input type=\"hidden\" id=\"inputInUse6\" name=\"inputInUse\" value=\"Y\"\/>\n<input type=\"hidden\" name=\"pyId\" value=\"6\"\/>\n<input type=\"hidden\" name=\"hash\" value=\"9cb01526813f9b7532c90df42dd658a1\"\/>\n<div id='pbresults6' class='pbresults avoidline'><\/div>\n<\/div>\n<\/form>\n<script type='text\/javascript'>jQuery(function(){pbToggleCodeMirror(6);});pbInputSwitch(6,\"Y\");<\/script>\n<\/p>\n<p><table class='pywarn'><tr><td class='pywarnleft'><img src='https:\/\/olescs.hkmu.edu.hk\/python\/wp-content\/plugins\/pybox\/files\/warning.png'\/><\/td><td class='pywarnright'><span> This is the last exercise in the CS Circles website. Congratulations to those who have tried all of the lessons! See the <a class=\"open-same-window\" href=\"\/resources\/\">resources page<\/a> for some suggestions on what to learn next. \u00a0Have fun, good luck, and code well! <\/span><\/td><\/table><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Many programming tasks can be done in more than one way, but one way might be much faster than another. Designing fast programs is part of the art and science of computer programming. We look at a couple of examples &hellip; <a href=\"https:\/\/olescs.hkmu.edu.hk\/python\/18-efficiency\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2367","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/2367"}],"collection":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/comments?post=2367"}],"version-history":[{"count":0,"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/pages\/2367\/revisions"}],"wp:attachment":[{"href":"https:\/\/olescs.hkmu.edu.hk\/python\/wp-json\/wp\/v2\/media?parent=2367"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}