Analyze the following code and reorganize the code to provide the best optimization in your opinion. Provide a brief write up justifying your optimizing choices.
import graphics as g
win = g.GraphWin(“Welcome Home”, 500, 500)
houseBrown = (g.color_rgb(150, 103, 85))roofBrown = (g.color_rgb(79, 56, 47))
daySky = g.Rectangle(g.Point(0, 0), g.Point(500, 160))daySky.setFill(‘skyBlue’)daySky.setWidth(0)daySky.draw(win)
grass = g.Rectangle(g.Point(0, 160), g.Point(500, 500))grass.setFill(‘darkgreen’)grass.setWidth(0)grass.draw(win)
street = g.Rectangle(g.Point(0, 375), g.Point(500, 500))street.setFill(‘gray’)street.setWidth(0)street.draw(win)
streetLine = g.Line(g.Point(15, 435), g.Point(55, 435))streetLine.setWidth(6)streetLine.setFill(“white”)streetLine.draw(win)
currentStreetLine = streetLinefor i in range(6):currentStreetLine = currentStreetLine.clone()currentStreetLine.move(80, 0)currentStreetLine.draw(win)
frontWall = g.Rectangle(g.Point(100, 200), g.Point(300, 325))frontWall.setFill(houseBrown)frontWall.draw(win)
address = g.Text(g.Point(200, 260), “2317”)address.draw(win)
centerRoofPoint = g.Point(200, 130)
roof = g.Polygon(g.Point(100, 200), centerRoofPoint, g.Point(300, 200))roof.setFill(houseBrown)roof.draw(win)
roofSide = g.Polygon(centerRoofPoint, g.Point(300, 200), g.Point(430, 160), g.Point(330, 90),)roofSide.setFill(roofBrown)roofSide.draw(win)
sideWall = g.Polygon(g.Point(300, 200), g.Point(430, 160), g.Point(430, 270), g.Point(300, 325))sideWall.setFill(houseBrown)sideWall.draw(win)
sideWindow = g.Polygon(g.Point(330, 218), g.Point(350, 210), g.Point(350, 275), g.Point(330, 285))sideWindow.setFill(‘white’)sideWindow.setWidth(3)sideWindow.draw(win)
sideWindowVertical = g.Line(g.Point(340, 215), g.Point(340, 282))sideWindowVertical.setWidth(2)sideWindowVertical.draw(win)
sideWindowHorizontal = g.Line(g.Point(330, 255), g.Point(350, 245))sideWindowHorizontal.setWidth(2)sideWindowHorizontal.draw(win)
rightSideWindow = sideWindow.clone()rightSideWindow.move(53, -20)rightSideWindow.draw(win)
rightSideWindowVertical = sideWindowVertical.clone()rightSideWindowVertical.move(53, -20)rightSideWindowVertical.draw(win)
rightSideWindowHorizontal = sideWindowHorizontal.clone()rightSideWindowHorizontal.move(53, -20)rightSideWindowHorizontal.draw(win)
door = g.Rectangle(g.Point(180,270), g.Point(220, 325))door.setFill(‘black’)door.draw(win)
doorKnob = g.Circle(g.Point(212, 300), 4)doorKnob.setFill(‘yellow’)doorKnob.draw(win)
leftWindow = g.Rectangle(g.Point(125, 230), g.Point(150, 260))leftWindow.setFill(‘white’)leftWindow.setWidth(3)leftWindow.draw(win)
hWindowLine = g.Line(g.Point(125, 245), g.Point(150, 245))hWindowLine.setWidth(2)hWindowLine.draw(win)
vWindowLine = g.Line(g.Point(137.5, 230), g.Point(137.5, 260))vWindowLine.setWidth(2)vWindowLine.draw(win)
rightWindow = leftWindow.clone()rightWindow.move(125, 0)rightWindow.draw(win)
rightHorizWindowLine = hWindowLine.clone()rightHorizWindowLine.move(125, 0)rightHorizWindowLine.draw(win)
rightVertWindowLine = vWindowLine.clone()rightVertWindowLine.move(125, 0)rightVertWindowLine.draw(win)
circleWindow = g.Circle(g.Point(200, 170), 15)circleWindow.setFill(‘white’)circleWindow.setWidth(3)circleWindow.draw(win)
circleLine = g.Line(g.Point(185, 170), g.Point(215, 170))circleLine.setWidth(2)circleLine.draw(win)
circleLineTwo = g.Line(g.Point(200, 155), g.Point(200, 185))circleLineTwo.setWidth(2)circleLineTwo.draw(win)
path = g.Rectangle(g.Point(180, 326), g.Point(220, 375))path.setFill(‘tan3’)path.setWidth(0)path.draw(win)
frontChimney = g.Polygon(g.Point(315, 90), g.Point(345, 80), g.Point(345, 140), g.Point(315, 150))frontChimney.setFill(houseBrown)frontChimney.draw(win)
sideChimney = g.Polygon(g.Point(295, 75), g.Point(315, 90), g.Point(315, 150), g.Point(295, 135))sideChimney.setFill(houseBrown)sideChimney.draw(win)
topChimney = g.Polygon(g.Point(295,75), g.Point(323, 65), g.Point(345, 80), g.Point(315, 90))topChimney.setFill(‘black’)topChimney.draw(win)fencePost = g.Polygon(g.Point(3, 340), g.Point(8, 335), g.Point(13, 340), g.Point(13, 370), g.Point(3, 370))fencePost.setFill(‘white’)fencePost.setOutline(‘white’)fencePost.draw(win)
current_fence_post = fencePostfor i in range(9):current_fence_post = current_fence_post.clone()current_fence_post.move(17, 0)current_fence_post.draw(win)
leftBeginningPost = fencePost.clone()leftBeginningPost.move(230, 0)leftBeginningPost.draw(win)
newLeftPost = leftBeginningPostfor i in range(17):newLeftPost = newLeftPost.clone()newLeftPost.move(17, 0)newLeftPost.draw(win)
upperRightFenceLine = g.Line(g.Point(0, 350), g.Point(170, 350))upperRightFenceLine.setWidth(3)upperRightFenceLine.setFill(‘white’)upperRightFenceLine.draw(win)
lowRightFenceLine = g.Line(g.Point(0, 365), g.Point(170, 365))lowRightFenceLine.setWidth(3)lowRightFenceLine.setFill(‘white’)lowRightFenceLine.draw(win)
upperLeftFenceLine = g.Line(g.Point(228, 350), g.Point(500, 350))upperLeftFenceLine.setWidth(3)upperLeftFenceLine.setFill(‘white’)upperLeftFenceLine.draw(win)
lowLeftFenceLine = g.Line(g.Point(228, 365), g.Point(500, 365))lowLeftFenceLine.setWidth(3)lowLeftFenceLine.setFill(‘white’)lowLeftFenceLine.draw(win)
cloudPuff = g.Circle(g.Point(50, 70), 8)cloudPuff.setFill(‘white’)cloudPuff.setWidth(0)cloudPuff.draw(win)
cloudPuffTwo = g.Circle(g.Point(60, 68), 10)cloudPuffTwo.setFill(‘white’)cloudPuffTwo.setWidth(0)cloudPuffTwo.draw(win)
cloudPuffThree = g.Circle(g.Point(75, 65), 13)cloudPuffThree.setFill(‘white’)cloudPuffThree.setWidth(0)cloudPuffThree.draw(win)
cloudPuffFour = cloudPuffTwo.clone()cloudPuffFour.move(30, 0)cloudPuffFour.draw(win)
sun = g.Circle(g.Point(500, 0), 65)sun.setFill(‘yellow’)sun.setOutline(‘orange’)sun.draw(win)
midCloud = g.Circle(g.Point(238, 50), 10)midCloud.setFill(‘white’)midCloud.setWidth(0)midCloud.draw(win)
midCloudTwo = g.Circle(g.Point(250, 48), 12)midCloudTwo.setFill(‘white’)midCloudTwo.setWidth(0)midCloudTwo.draw(win)
midCloudThree = g.Circle(g.Point(265, 46), 16)midCloudThree.setFill(‘white’)midCloudThree.setWidth(0)midCloudThree.draw(win)
midCloudFour = midCloudTwo.clone()midCloudFour.move(30, 0)midCloudFour.draw(win)
midCloudFive = g.Circle(g.Point(290, 50), 8)midCloudFive.setFill(‘white’)midCloudFive.setWidth(0)midCloudFive.draw(win)
lastCloud = g.Circle(g.Point(430, 50), 10)lastCloud.setFill(‘white’)lastCloud.setWidth(0)lastCloud.draw(win)
lastCloudTwo = g.Circle(g.Point(420, 49), 7)lastCloudTwo.setFill(‘white’)lastCloudTwo.setWidth(0)lastCloudTwo.draw(win)
lastCloudThree = g.Circle(g.Point(443, 48), 14)lastCloudThree.setFill(‘white’)lastCloudThree.setWidth(0)lastCloudThree.draw(win)
lastCloudFour = lastCloud.clone()lastCloudFour.move(30, 0)lastCloudFour.draw(win)
win.getMouse()
nightSky = g.Polygon(g.Point(0, 0), g.Point(500, 0), g.Point(500, 160), g.Point(430, 160), g.Point(330, 90), centerRoofPoint, g.Point(156, 160), g.Point(0, 160))nightSky.setFill(‘black’)nightSky.draw(win)
frontChimney = g.Polygon(g.Point(315, 90), g.Point(345, 80), g.Point(345, 140), g.Point(315, 150))frontChimney.setFill(houseBrown)frontChimney.draw(win)sideChimney = g.Polygon(g.Point(295, 75), g.Point(315, 90), g.Point(315, 150), g.Point(295, 135))sideChimney.setFill(houseBrown)sideChimney.draw(win)
topChimney = g.Polygon(g.Point(295,75), g.Point(323, 65), g.Point(345, 80), g.Point(315, 90))topChimney.setFill(‘black’)topChimney.setOutline(‘darkgray’)topChimney.draw(win)
lightMoon = g.Circle(g.Point(450, 50), 40)lightMoon.setFill(‘yellow’)lightMoon.draw(win)
darkMoon = g.Circle(g.Point(420, 50), 40)darkMoon.setFill(‘black’)darkMoon.draw(win)
star = g. Polygon(g.Point(10, 30), g.Point(12, 25), g.Point(14, 30), g.Point(19, 30), g.Point(15, 35), g.Point(18, 40), g.Point(13, 37), g.Point(7, 40), g.Point(9, 35), g.Point(4, 30))star.setFill(‘yellow’)star.draw(win)
starTwo = star.clone()starTwo.move(100, -15)starTwo.draw(win)
starThree = star.clone()starThree.move(55, 15)starThree.draw(win)
starFour = star.clone()starFour.move(20, 60)starFour.draw(win)
starFive = star.clone()starFive.move(60, 95)starFive.draw(win)
starSix = starFour.clone()starSix.move(80, 0)starSix.draw(win)
starSeven = starTwo.clone()starSeven.move(150, 0)starSeven.draw(win)
starEight = starThree.clone()starEight.move(126, 28)starEight.draw(win)
starNine = starThree.clone()starNine.move(80, 0)starNine.draw(win)
starTen = starFive.clone()starTen.move(80, 0)starTen.draw(win)
starEleven = starFour.clone()starEleven.move(420, 48)starEleven.draw(win)
starTwelve = starTwo.clone()starTwelve.move(280, 12)starTwelve.draw(win)
starThirteen = starEight.clone()starThirteen.move(45, 15)starThirteen.draw(win)
starFourteen = starThirteen.clone()starFourteen.move(-20, -50)starFourteen.draw(win)
starFifteen = starFourteen.clone()starFifteen.move(69, 16)starFifteen.draw(win)
smokePuff = g.Oval(g.Point(315, 50), g.Point(330, 20))smokePuff.setFill(‘gray’)smokePuff.setWidth(0)smokePuff.draw(win)
secondSmokePuff = smokePuff.clone()secondSmokePuff.move(-5, 20)
thirdSmokePuff = secondSmokePuff.clone()thirdSmokePuff.move(5, 8)thirdSmokePuff.draw(win)
fourthSmokePuff = secondSmokePuff.clone()fourthSmokePuff.move(10, -3)fourthSmokePuff.draw(win)secondSmokePuff.draw(win)
paleYellow =(g.color_rgb(244, 242, 127))sideWindow.setFill(paleYellow)rightSideWindow.setFill(paleYellow)circleWindow.setFill(paleYellow)leftWindow.setFill(paleYellow)rightWindow.setFill(paleYellow)
Design Level Optimization
Highest Level Optimization
Design level optimization is the highest level of optimization. This also will give us our
greatest ability to customize our code to the problem we are trying to address. We can
gear the optimization toward the best use of resources, goals, restrictions, or the general
expected user load and use cases.
Our main focus on looking at design level optimization is the architectural design of the
system in total. For example, if we have a system that is network latency-bound, we
would want to minimize the number of requests that the client would make to the
server. This is because, in a network latency issue, our main restriction to better
performance would be the network itself.
Dependent on Goals For Program
The main thing to understand about design level optimization is that it is truly dependent
on our goals for the program or application. Notably, one of the foundational goals of
Facebook was that the system never went down even as it scaled a great number of
users. This lead to a more minimalistic design in front end and simplified algorithm
construction in the PHP on the backend. This didn’t put as much strain on the servers of
Facebook (which were in the house at the time) and would reduce the risk of a network
outage.
We can see that the choice of language or architecture hits this. If we are in a new
system, we might not program it in C or Java because of longevity and support
issues. Mainly because we would have to rewrite it completely if we were to change the
language to increase efficiency because the goal of the program changed. We can also
see this in the architecture. For a system like Bitcoin which is peer-to-peer, it takes the
network longer to communicate between those clients. However, since the Bitcoin
network has become so big and the trading so volatile, it would be incredibly difficult to
change that structure. You could also make the argument that it would disrupt the key
principle of Bitcoin in general because you would have to create a central system in
order to navigate through this and handle the request load easier. Like a Bank of Bitcoin
which would be odd for a system looking to disrupt banks.
Because of design level optimization has the greatest impact both in development and
long term, we need to be cognizant of it at the beginning of our development.
Algorithm and Data Structure
Optimization
Algorithms
Once our overall design is structured effectively, then we should implement algorithms
and data structures that can provide more efficient processing. Again, remember that
this is done after our initial development so we are able to make another pass and see
how the problem was solved then move from there.
Data Structures
Algorithms are usually easier to change than data structures so we should focus on these
first. Data structures are used throughout the program as is their assumed structure so
we might have to modify the entire program because of their reach. Algorithms may just
focus on one piece of processing done with that data structure. One way to address this
is to use a pure function principle and incorporate the abstract idea of the data structure
into functions so they are modular and can be addressed.
The technique most commonly used is the idea of a fast path. This is a shorter
instruction path length through a program compared to the “normal” path. It handles the
most commonly occurring tasks while the normal path is used more for unique cases and
error handling.
Think of a conditional that requires a specific value. The fast path would take it straight
through the conditional while the normal path would be a branch of the conditional in
order to handle the error from a user (say they enter a negative number when a positive
is needed).
Compiler Optimization
When we are looking at compiler optimization, we are following the same principle of
trying to consume fewer resources as a way to ensure that the program will run faster
and more efficiently. There are some objectives and techniques that are specific to
compiler optimization.
When we conduct compiler optimization, we should be concerned with the following
ideas and ensure that our optimization does this:
•
•
•
•
It must not change the meaning of the program
It should increase the speed and the performance of the program
The compilation time should be kept reasonable
The optimization process should not delay the overall compiling process.
If our optimization violates one of the following principles, then we should not conduct it
or redo it.
To ensure these techniques work, study the following visual:
You can see that we have several techniques and some branches that can be utilized.
Depending on the style of our code, we would have to undertake different techniques
and strategies.
Let’s look at these techniques from the above graphic individually.
Compile-time evaluation – This is moving code to have the evaluation of a function
move from execution to compile time. This would store the validity of the function and
allow for a smoother transition.
This can be divided into two parts:
•
o
Constant folding – This involves the folding of constants as the
name self describes. If an expression has a constant value, it is
evaluated at compile time. They are then replaced with their
respective result. This saves on resources because the program
does not need to constantly evaluate that value since it knows it
will always be the same.
For example: If we are calculating the circumference of a circle we would want to use
the formula:
Circumference = pi * diameter
We would be able to calculate pi with the value of 22/7. When this is evaluated, it would
provide a constant value of 3.14 and moves it away from runtime.
•
o
Constant (Variable) Propagation – if a variable has been assigned a
constant value, then it replaces the variable with its constant value
during compilation.
For example: if we are to calculate the area of a circle, we would take pi times the radius
squared:
Our program may look like:
Pi = 3.14
Radius = 5
Area = pi * radius * radius
The values would be substituted at compile time and would save time at runtime.
Common Sub-Expression Elimination – This eliminates common subexpressions.
Redundant expressions are eliminated to avoid re-computation and the draining of
resources. Review the following table as an example:
Notice how S4 is not needed since it is the same as S1. This means that it would be
calculated again and eat up resources.
Code movement – Here we would move code outside of loops if it is not necessary. This
would prevent the code from being calculated repeatedly and wasting time at run time.
Review the following table as an example:
The expression x= y + z is trapped in the for loop so it would have to be calculated every
time the loop runs even if it is not necessary. From the loop, it is not because it is not
referenced in other calculations in the loop.
Dead code elimination – for this we remove unnecessary code. Dead code is statements
that are unreachable, would never be executed or whose output is never used.
For example:
i = 0 ;
if (i == 1)
{
a = x + 5 ;
}
Since we are setting the variable i to 0 at the beginning, it will never enter the
conditional statement because it will never be equal to 1. This means that the conditional
block is dead so we could eliminate it entirely.
Strength Reduction – This reduces the strength of expressions. It would replace costly
operators in memory with similar ones. For example, multiplication operators are more
“expensive” to memory than addition operators because of the extra steps the binary
uses to calculate them at the machine level language.
If we would have an expression like
A = N * 2
We could reduce the strength of the expression by converting it to:
A = N + N
Now it should be clear that some of these techniques do not make sense all the time.
Optimization at the compiler is about managing resources and can beef up our run time
but it should also simplify the code and not make the meaning of the program change.
This is why we conduct the optimization at the end of the development process and
after testing.
Summary
Compiler optimization can be used to consume fewer resources as a way to ensure that
the program will run faster and more efficiently.
Recursion for Optimization
Recursion
One of the aspects of computer science and code optimization is the elimination of
redundant code. In some cases, we would want to build in recursion help with this
process.
Below is a function that starts a background for a graphical image:
def background():
daySky = g.Rectangle(g.Point(0, 0), g.Point(500, 160))
daySky.setFill(‘skyBlue’)<
daySky.setWidth(0)
daySky.draw(win)
grass = g.Rectangle(g.Point(0, 160), g.Point(500, 500))
grass.setFill('darkgreen')
grass.setWidth(0)
grass.draw(win)
street = g.Rectangle(g.Point(0, 375), g.Point(500, 500))
street.setFill('gray')
street.setWidth(0)
street.draw(win)
You can see that there are three components that are held in the background
function. We could break these out into individual functions which would lead to some
increased modularity. However, we would have to call all of these individual functions
and that would lead to greater memory use during run time. Containing them in this one
function allows a single evaluation at the compile-time and saves the resources at run
time.
Summary
Recursion can be built into a program to eliminate redundant code.