Filetype PDF | Posted on 03 Feb 2023 | 3 years ago
Authentication
digital resources
303x Filetype PDF File size 0.23 MB Source: ecs.wgtn.ac.nz
Analysing Costs (in general) COMP103: 89 Benchmarking: program cost COMP103: 90
How can we determine the costs of a program? Measure:
• actual programs, on real machines, with specific input
• Time: • measure elapsed time
• Run the program and count the milliseconds/minutes/days. • System.currentTimeMillis ()
• Count number of steps/operations the algorithm will take. → time from the system clock in milliseconds
• measure real memory
• Space: Problems:
• Measure the amount of memory the program occupies. • what input? ⇒ use large data sets
• Count the number of elementary data items the algorithm stores.
don’t include user input
• other users/processes? ⇒ minimise
• Applies to Programs or Algorithms? Both. average over many runs
• programs “benchmarking” • which computer? ⇒ specify details
• algorithms “analysis” • how to compare cross-platform? ⇒ measure cost at an abstract level
© Peter Andreae © Peter Andreae
Analysis: Algorithm “complexity” COMP103: 91 Big-O Notation COMP103: 92
• Abstract away from the details of • Only care about large input sets
• the hardware, the operating system • Lower-order terms become insignificant for large n
• the programming language, the compiler • We care about how cost grows with input size
• the specific input
• Don’t care about constant factors
• Measure number of “steps” as a function of the data size
• best case (easy, but not interesting) • Multiplication factors don’t tell us how things “scale up”
• worst case (usually easy)
• average case (harder) 2 2
3.47 n + 102n + 10064 steps O(n )
• The precise number of steps is not required 3n log n + 12n steps O(n log n)
2
• 3.47 n - 67n + 53 steps
• 3n log(n) + 5n - 3 steps
• Rather, we are interested in how the cost grows with data size on large data
© Peter Andreae © Peter Andreae
Big-O classes COMP103: 93 How the different costs grow COMP103: 94
“Asymptotic cost”, or “big-O” cost describes how cost grows with input size
• Examples:
• O(1) constant: cost is independent of n : Fixed cost! 100,000 log2 n
90,000
• O(log n) logarithmic: cost grows by 1, when n doubles : almost constant 80,000 n
70,000 n logn
• O(n) linear: cost grows linearly with n : 60,000 n^2
50,000 n^3
• O(n log n) log linear: cost grows a bit more than linear: Slow growth! 40,000 2^n
2 30,000
• O(n ) quadratic: costs x 4 when n doubles: limits problem size 20,000
n 10,000
• O(2 ) exponential: costs doubles when n increases by 1: 0
severely limits problem size 0 100 200 300 400 500 600 700 800 900 1000
n: size of input
© Peter Andreae © Peter Andreae
Manageable Problem Sizes COMP103: 95 What is a “step”? COMP103: 96
• How big can the data be if • Any important actions that are at the center of the algorithm
• one step takes around a microsecond • comparing data
• algorithm is O(….) • moving data
1 min 1 h 1 day 1 week 1 year • anything you consider to be “expensive”
• Doesn’t depend on size of data
O(n) 107 109 1011 1012 1013
public E remove (int index){
6 8 9 10 12 if (index < 0 || index >= count) throw new ….Exception();
O(n logn) 10 10 10 10 10 Eans= data[index];
2 4 5 5 6 7 for (int i=index+1; i< count; i++)
O(n ) 10 10 10 10 10 data[i-1]=data[i];
← Key Step
3 2 3 3 4 4 count--;
O(n ) 10 10 10 10 10 data[count] = null;
n return ans;
O(2 ) 25 31 36 39 44 }
half million seconds in a year
© Peter Andreae © Peter Andreae
What’s a step: Pragmatics COMP103: 97 Costs of Standard Collection classes COMP103: 98
• Count the most expensive actions: • ArrayList: O(1): clear, add, set, remove from end:
• Adding 2 numbers is cheap O(n): add, remove, contains, Collections.reverse, .shuffle
• Raising to a power is not so cheap O(n log(n)) Collections.sort,
• Comparing 2 strings may be expensive • ArrayDeque: O(1): clear, push, pop, offer, poll, add/remove First/Last:
• Reading a line from a file may be very expensive O(n): contains, remove(obj)
• PriorityQueue: O(log(n)): offer, poll
• Waiting for input from a user or another program may take forever…
• Sometimes we need to know about how the underlying operations are • HashSet: O(1): add, remove, contains
implemented in the computer to choose well (NWEN241/342).
• TreeSet: O(log(n)): add, remove, contains
• HashMap: O(1): clear, containsKey, put, get
But depends on the cost of hashCode
© Peter Andreae © Peter Andreae
Example Algorithms COMP103: 99 Finding the Mode of a list COMP103: 100
• Finding the Mode of a set of numbers • Mean = total/count
• Median = middle value, separating top 50% from bottom 50%
• Reverse a List • Mode = most frequent number.
• Find combinations of items to fill a pallett 23,22,49,25,43,23,5,31,43,27,21,45,43,16,5,21,18,27,39,18,21,7,42,28,21,19
• Find permutations of letters to make words. Algorithm:
• (fix the dictionary!) • set mode to the first number and modeCount to 1
• for each value in the list:
• step through the list to count how many times value occurs in the list
• if count > modeCount then set mode and modeCount to value and count
What’s the cost if there
are n numbers?
© Peter Andreae © Peter Andreae
Mode: the bad way COMP103: 101 Finding the Mode of a list faster COMP103: 102
public int mode(Listnumbers){ Analysis • Much easier to see if the list is sorted in order:
int mode = numbers.get(0); 1 x O(1) 23,22,49,25,43,23,5,31,43,27,21,45,43,16,5,21,18,27,39,18,21,7,42,28,21,19
int modeCount = 1; 1 time
for (int value : numbers){ 5,5,7,16,18,18,19,21,21,21,21,22,23,23,25,27,27,28,31,39,42,43,43,43,45,49
int count = 0; n times • Algorithm
for (int other : numbers){
if (other == value) { nxntimes • sort the list What’s the cost if there
count++; n … nxn times n*n iterations • set mode to first number and modeCount to 1 are n numbers?
} niterations • set count to 1
} • step through the list from index 1
if (count > modeCount) { n times
mode = value; 1 … n times • if the number is the same as the previous number, then increment count
modeCount = count;
} 1 … n times • else
} • if count > modeCount, then set mode and modeCount to previous value and count
return mode; 1 time • reset count to 1
} • if count > modeCount, then set mode and modeCount to previous value and count
© Peter Andreae © Peter Andreae
Finding the Mode of a list faster COMP103: 103 Finding the Mode of a list even faster COMP103: 104
• Algorithm Analysis • Count using a map to count without sorting:
• sort the list 1 x O(n log(n))
• set mode to first number and modeCount to 1 1 time 23,22,49,25,43,23,5,31,43,27,21,45,43,16,5,21,18,27,39,18,21,7,42,28,21,19
• set count to 1 1 time
• step through the list from index 1 5-2 7-1 16-1 18-2 19-1 21-4 22-1 23-2 25-1
• if number is same as previous number, then n times 27-2 28-1 31-1 39-1 42-1 43-3 45-1 49-1
• increment count
n 1 … n times
• else What’s the cost if there
iterations • if count > modeCount, then n… 1 times • Algorithm are n numbers?
• set mode and modeCount to previous number and count n… 1 times • for each value in the list
• reset count to 1 n… 1 times • if the value is in the map, then increment the associated count
• if count > modeCount, then 1 time • else add the value to the map with an associated count of 1.
• set mode and modeCount to previous value and count • for each key in map,
Total: O(n log(n)) • if associated count > modeCount, then set mode and modeCount to key and count
© Peter Andreae © Peter Andreae
no reviews yet
Please Login to review.
