Chapter 2

These are the solutions to the .

1. Personally, I would have guessed that the first version is faster. This is because the first version relies on linear search, which is O(N), while the second version relies on sorting, which is O(N log N). Indeed, my benchmarking bears out this hypothesis. Here is my benchmarking code:

   ​	​import​ ​timeit​
   ​
   ​	setup_code = ​'''​
   ​	​import random​
   ​	​import exercise_1a​
   ​
   ​	​array = []​
   ​	​for i in range(1000000):​
   ​	​ n = random.randint(1, 1000000)​
   ​	​ array.append(n)​
   ​	​'''​
   ​
   ​	test_code = ​'''​
   ​	​exercise_1a.minimum(array)​
   ​	​'''​
   ​
   ​	​print​(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

   This code benchmarks the first version, which I saved in a file called exercise_1a.py.

   When I benchmarked the first version, my results were:

   ​	0.029821541000000007, 0.030344957999999922, 0.03037758299999993,
   ​	0.029123583000000064, 0.030518541999999815

   I saved my second version in a file named exercise_1b.py and updated my benchmarking code accordingly. The benchmarking results of my second version, as I’d predicted, were slower:

   ​	0.22374379099999997, 0.21845316700000006, 0.21908141599999986,
   ​	0.22122462500000006, 0.218094958

2. For this scenario, I predicted that the two functions would have the same speed. I based this hypothesis on the fact that in the exercises for Chapter 1, we saw that the bytecode for a for..range loop and a while loop were similar.

   But it turns out that my prediction was not entirely correct. Here is my benchmarking code:

   ​	​import​ ​timeit​
   ​
   ​	setup_code = ​'''​
   ​	​import random​
   ​	​import exercise_2a​
   ​	​'''​
   ​
   ​	test_code = ​'''​
   ​	​exercise_2a.sum_up_to_one_million()​
   ​	​'''​
   ​
   ​	​print​(timeit.repeat(stmt=test_code, setup=setup_code, repeat=5, number=1))

   This code works just as well for the second version; I only needed to change the module name.

   Here are my benchmarking results for the for..range code:

   ​	0.05982770799999999, 0.05473741700000001, 0.054945541000000014,
   ​	0.05513195900000001, 0.055346958

   My benchmarking results for the while loop code showed that this second version was slightly slower:

   ​	0.087291291, 0.08183283300000001, 0.08237899999999998,
   ​	0.08279591600000002, 0.08296995899999998

   As to why this is, well, that’s hard to know for sure without delving into Python’s source code to see how its loops are implemented. There’s discussion on the Internet about this, and I invite you to do further research if you’re interested in learning more.

3. The most important case to test when it comes to sorting is a list of jumbled values, which is the average case. In my setup code, though, I created an array of sorted integers. Sorting presorted values can either be much faster or slower than the average case, and it may be worthwhile benchmarking as well. However, it’s certainly a mistake to only benchmark this edge case and ignore the performance of the typical case, which is to sort unsorted values. To fix this, the setup code should instead create an array of integers that are in random order.

4. First, I shouldn’t be including the print command in my testcode, as printing takes time, and we’re not interested in testing how fast printing is.

   Second, in my setup code for linear search, my array only contains 100,000 values, while my binary search benchmark creates an array of one million values. This isn’t an apples-to-apples comparison, and is therefore an experiment that is not properly controlled. It’s pretty messed up, to be honest.