Speed of Algorithms: Importance and Impact on Performance
Algorithmic complexity:
Speed of algorithms
CSE 160
Spring 2015
University of Washington
1
How fast does your program run?
•
Usually, this
does not matter
•
Correctness
trumps speed
•
Computer time is much cheaper than human time
•
The cost of your program depends on:
–
Time to write and verify it
•
High cost: salaries
–
Time to run it
•
Low cost: electricity
•
An inefficient program may give results faster
2
Sometimes, speed does matter
•
Ridiculously inefficient algorithms
•
Very large datasets
Google:
67 billion pages indexed (2014)
5.7 billion searches per day (2014)
Number of pages searched per day??
3
Program Performance
We’ll discuss two things a programmer can do to
improve program performance:
•
Good Coding Practices
•
Good Algorithm Choice
4
Good Coding Practices
•
Minimize amount of work inside of loops
y = 500
for i in range(n):
z = expensive_function()
x = 5.0 * y / 2.0 + z
lst.append(x + i)
5
Good Coding Practices
•
Minimize amount of work inside of loops
for i in friends_of_friends(n):
for j in friends_of_friends(n):
# do stuff with i and j
6
Good Coding Practices
for base in nucleotides:
if base == 'A':
# code here
for base in nucleotides:
if base == 'C':
# code here
for base in nucleotides:
if base == 'T':
# code here
for base in nucleotides:
if base == 'G':
# code here
for base in nucleotides:
if base == 'A':
# code here
elif base == 'C':
# code here
elif base == 'T':
# code here
elif base == 'G':
# code here
7
•
Avoid iterating over data multiple times when possible
Good Algorithm Choice
•
Good choice of algorithm can have a much
bigger impact on performance than the good
coding practices mentioned.
•
However good coding practices can be applied
fairly easily
•
Trying to come up with a better algorithm can
be a (fun!) challenge
•
Remember:
Correctness trumps speed!!
8
How to compare two algorithms?
9
Example: Processing pairs
def make_pairs(list1, list2):
"""Return a list of pairs.
Each pair is made of corresponding elements of list1 and list2.
list1 and list2 must be of the same length."""
…
assert make_pairs([100, 200, 300], [101, 201, 301]) == [[100, 101],
[200, 201], [300, 301]]
•
2 nested loops vs. 1 loop
•
Quadratic (n
2
) vs. linear (n) time
10
Searching
def search(value, lst):
"""Return index of value in list lst.
The value must be in the list."""
…
•
Any list vs. a sorted list
•
Linear (n) vs. logarithmic (log n) time
11
Sorting
def sort(lst):
"""Return a sorted version of the list lst.
The input list is not modified."""
…
assert sort([3, 1, 4, 1, 5, 9, 2, 6, 5]) == [1, 1,
2, 3, 4, 5, 5, 6, 9]
•
selection sort vs. quicksort
•
2 nested loops vs. recursive decomposition
•
time: quadratic (n
2
) vs. log-linear (n log n) time
12
Algorithms play a crucial role in program performance. While correctness is paramount, the speed at which a program executes can significantly impact the overall cost. This article highlights the balance between speed and correctness, emphasizing the importance of good coding practices and algorithm choice in optimization. It discusses the trade-offs between program efficiency and computational resources, showcasing how efficient algorithms can handle vast datasets and large-scale operations. Additionally, it provides insights into enhancing program performance through efficient coding techniques and algorithm selection.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Algorithmic complexity: Speed of algorithms CSE 160 Spring 2015 University of Washington 1
How fast does your program run? Usually, this does not matter Correctness trumps speed Computer time is much cheaper than human time The cost of your program depends on: Time to write and verify it High cost: salaries Time to run it Low cost: electricity An inefficient program may give results faster 2
Sometimes, speed does matter Ridiculously inefficient algorithms Very large datasets Google: 67 billion pages indexed (2014) 5.7 billion searches per day (2014) Number of pages searched per day?? 3
Program Performance We ll discuss two things a programmer can do to improve program performance: Good Coding Practices Good Algorithm Choice 4
Good Coding Practices Minimize amount of work inside of loops y = 500 for i in range(n): z = expensive_function() x = 5.0 * y / 2.0 + z lst.append(x + i) 5
Good Coding Practices Minimize amount of work inside of loops for i in friends_of_friends(n): for j in friends_of_friends(n): # do stuff with i and j 6
Good Coding Practices Avoid iterating over data multiple times when possible for base in nucleotides: if base == 'A': # code here for base in nucleotides: if base == 'C': # code here for base in nucleotides: if base == 'T': # code here for base in nucleotides: if base == 'G': # code here for base in nucleotides: if base == 'A': # code here elif base == 'C': # code here elif base == 'T': # code here elif base == 'G': # code here 7
Good Algorithm Choice Good choice of algorithm can have a much bigger impact on performance than the good coding practices mentioned. However good coding practices can be applied fairly easily Trying to come up with a better algorithm can be a (fun!) challenge Remember: Correctness trumps speed!! 8
Example: Processing pairs def make_pairs(list1, list2): """Return a list of pairs. Each pair is made of corresponding elements of list1 and list2. list1 and list2 must be of the same length.""" assert make_pairs([100, 200, 300], [101, 201, 301]) == [[100, 101], [200, 201], [300, 301]] 2 nested loops vs. 1 loop Quadratic (n2) vs. linear (n) time 10
Searching def search(value, lst): """Return index of value in list lst. The value must be in the list.""" Any list vs. a sorted list Linear (n) vs. logarithmic (log n) time 11
Sorting def sort(lst): """Return a sorted version of the list lst. The input list is not modified.""" assert sort([3, 1, 4, 1, 5, 9, 2, 6, 5]) == [1, 1, 2, 3, 4, 5, 5, 6, 9] selection sort vs. quicksort 2 nested loops vs. recursive decomposition time: quadratic (n2) vs. log-linear (n log n) time 12
