What a difference a line of code makes
32 little lines
...
Ok, now that we have Renee Olstead's song in our heads lets get what it is I'm trying to say:
Code that works may very well not perform well. I wanted to see about writing some code to figure out the first n prime numbers. Pretty easy stuff:
I got to thinking that the downside of this is that I am running the modulo operator on each and every number. This clunkiness isn't so apparent on testing the first 100 numbers, but, what if we are talking about 100,000?!?
More to the point, how to even see what is the time spent?
require 'benchmark' => from ruby docs we can see that this module lets us see what the time factor really is.
From the docs we understand that the time breakdowns are: CPU time, system CPU time, sum of user and system CPU time and, arguably, most importantly, elapsed real time (the on in quotes: (0.000100) )
Lets change array_test(100) to array_test(100000). This will run our benchmark on our method to show us the prime numbers 1 - 100,000.
Yeah, a big time difference. Before coding I wouldda thought there would have been a linear difference, but here we see instead of it taking x1,000 more, it is x100,000. Here is our first taste of Big O, and I'll go over that later. But lets instead focus on making this faster.
Nice... ~x6 faster
what does adding (2..Math::sqrt(max)).each do |i| help us achieve?
Essentially we have to recognize that x * y = z. If z is not a prime then there has to be two numbers x * y = z. If both x and y were are greater than the square root of n then x * y would be greater than n; This then means that x or y must be less than (or equal to) the square root of n (thanks to Edward Guiness's book for really helping me understand this).
So, instead of checking all the numbers 1-100,000 (as the iterated array using i), we can test a much smaller set of numbers.
32 little lines
...
Ok, now that we have Renee Olstead's song in our heads lets get what it is I'm trying to say:
Code that works may very well not perform well. I wanted to see about writing some code to figure out the first n prime numbers. Pretty easy stuff:
I got to thinking that the downside of this is that I am running the modulo operator on each and every number. This clunkiness isn't so apparent on testing the first 100 numbers, but, what if we are talking about 100,000?!?
More to the point, how to even see what is the time spent?
require 'benchmark' => from ruby docs we can see that this module lets us see what the time factor really is.
From the docs we understand that the time breakdowns are: CPU time, system CPU time, sum of user and system CPU time and, arguably, most importantly, elapsed real time (the on in quotes: (0.000100) )
Lets change array_test(100) to array_test(100000). This will run our benchmark on our method to show us the prime numbers 1 - 100,000.
Yeah, a big time difference. Before coding I wouldda thought there would have been a linear difference, but here we see instead of it taking x1,000 more, it is x100,000. Here is our first taste of Big O, and I'll go over that later. But lets instead focus on making this faster.
what does adding (2..Math::sqrt(max)).each do |i| help us achieve?
Essentially we have to recognize that x * y = z. If z is not a prime then there has to be two numbers x * y = z. If both x and y were are greater than the square root of n then x * y would be greater than n; This then means that x or y must be less than (or equal to) the square root of n (thanks to Edward Guiness's book for really helping me understand this).
So, instead of checking all the numbers 1-100,000 (as the iterated array using i), we can test a much smaller set of numbers.
No comments:
Post a Comment