```
import random
def randomList(n,d):
"returns a list of n random integers in [0..d-1]"
L = []
for i in range(0,n):
# randint(a..b) returns a random integer in [a..b]
L.append(random.randint(0,d-1))
return L
```
To time a piece of code, you can use the time module:
import time
startTime = time.time()
#do your thing here
...
endTime = time.time()
print(endTime-startTime)
There is also a timeit module. Give timeit.timeit
the instruction you want to time:
import timeit
t = timeit.timeit('"-".join(str(n) for n in range(100))', number=10000)
print(t)
Then make a plot that has list size in the x axis
and running time in the y axis. Use list sizes large enough
that e.g. selection sort takes of the order of 2-3 minutes.
You don't have to try every single list size up to them,
try for example powers of 2 or so.
In my laptop, selection sort of lists with about 16000 elements takes about 1 minute.
Can you guess how much it would take for one with 1 million elements?
Of course, it's nicer if you make a program that actually
tries all these points one after the other, rather than
you calling the base program by hand many times.
Can you note the difference between O(n^2) and O(n log n) sort?
Take into account that if you choose sizes that are too small
then the time to start up the program may dominate the
overall running time (like an additive O(n)) term.
--------
Part 2:
Program Solutions 1, 2, 3, 4 to the keeping counts problem.
If not all four, program at least 1 and 4.
- Solution 1 keeps an unordered table and searches elements linearly.
You may need an ad-hoc function for linear search that returns
a position or -1, and that "knows" that the list has pairs (x,c)
when searching for x
- Solution 2 keeps an ordered table and searches elements using
binary search. You may need and ad-hoc function for binary search
for lists of pairs (x,c) that compares only x, and a function
that inserts pair (x,1) in a list of pairs, which is similar
to a piece of insertion sort
(in your first trial, you'll get index out of bounds trial;
remember that insertion sort moves "up" an element that
is already part of the list, while you are adding a new one.
- Solution 3 sorts the list, then "compresses" all occurrences
of every x in the sorted list into a pair (x,c) in the new list.
- Solution 4 uses a dictionary.
Note that in Python3 when you want to convert a dictionary into
a list you do
lst = list(d.items())
(an explicit conversion to list is necessary)
Now run your four solutions for random lists of size n = 1, 2, 4, ... up to
where you can. Start with few different elements in every list (d=10, for example).
In my laptop, with d=10, the slowest solution takes about 12 seconds for
n=1 milion or so.
Do the methods scale in time as predicted by the theory?
Now, we also know that Solutions 3 and 4 are pretty much independent of
d = number of distinct elements in list = the size of the resulting list.
But the running times of Solutions 1 and 2 do depend on d.
Now fix for example n = 500,000 and try for d = 10, 20, 40, ... up to
where you can, see if you observe the dependence in the running time.
In all the lab:
Aim at having clean code. Use functions a lot. Document them.