Exercise 9
Download and extract the code skeleton for this exercise. As last week, the code includes an outline of how to organize your work and some tests.
Go Get
The tests provided for this exercise use the assert package which is excellent, but not part of the standard library. It will give us a chance to see how easily Go can install external dependencies:
go get github.com/stretchr/testify/assert
Mutating Methods
Our Point
class from last week was effectively immutable (from outside the package) since there were no exported members, and not methods that changed its state.
Let's add some methods that change the Point
in place. In order to modify the struct, a method must use a pointer receiver argument. Feel free to copy your Point
implementation from last week, and in points.go
, change the package to exer9
and…
Scale
Add a .Scale(f)
method to the Point
from last week. It should change an existing point in place and stretch it by a factor of f
. For example:
p := Point{1, 2}
p.Scale(5)
fmt.Println(p)
… should print (5, 10).
Rotate
We can add another transformation to a Point
: rotation. We would like to call .Rotate(angle)
and have the point rotated by angle
radians around the origin. For angle \(a\), the transformation is:
\[
x \leftarrow x \cdot \cos(a) - y\cdot\sin(a) \\
y \leftarrow x \cdot \sin(a) + y\cdot\cos(a)
\]
The result should be that this code:
p := Point{1, 0}
p.Rotate(math.Pi / 2)
fmt.Println(p)
p.Rotate(math.Pi / 2)
fmt.Println(p)
… should print (0, 1) and (-1, 0) (but probably not exactly due to floating-point error, but the results will be close to these values).
Random Arrays
We want to generate some random arrays. In array_stats.go
, write a function that creates and returns an array with length
integers and values from 0 to maxInt-1
with this signature:
func RandomArray(length int, maxInt int) []int { … }
When doing this, create a new random number generator that has a reasonable initial seed.
Array Summary Stats
We want to calculate the mean and standard deviation of values in an array/slice. For arrays with values \(x\) and \(n\) elements, we will use these formulas:
\(\mu = \left(\sum x\right) / n \)
\(\sigma = \sqrt{\left(\sum x^2\right)/n - \left(\left(\sum x\right)/n\right)^2} \)
In order to calculate these, we need the length of the slice (easy), \(\sum x\) and \(\sum x^2\). Those are things we can calculate in parallel on a large array.
We will break the array into some evenly-sized slices and want to calculate the two sums on each of the chunks concurrently in goroutines. Our function will take the array/slice and number of chunks to break the array into:
func MeanStddev(arr []int, chunks int) (mean, stddev float64) { … }
You can assume that the length of arr
is divisible by chunks
: no rounding error to worry about.
In order to do this, you need to create:
- A
struct
to hold partial sums as they are generated. - A channel to communicate these partial sums back to the
MeanStddev
function. - A function that can run in a goroutine, calculate the sum and sum of squares on a slice, and send the values back along the channel.
In MeanStddev
, you will need to create chunks
goroutines to calculate partial sums. Then receive chunks
values from the channel, create the final sums, and return the correct values.
Sorting
There is a built-in sort package in Go, but that doesn't have to stop us from implementing some sorting algorithms. In sort.go
…
Insertion Sort
Implement an insertion sort that sorts an array slice in-place:
func InsertionSort(arr []float64) { … }
Quicksort
Implement a Quicksort that sorts an array slice in-place:
func QuickSort(arr []float64) { … }
There is a function partition
in the provided sort.go
file that might be useful.
Tuning Quicksort
Quicksort is actually slower than insertion sort for small arrays: the mechanics of Quicksort only make sense for larger arrays.
Update your Quicksort function so that for slice lengths below insertionSortCutoff
, it calls InsertionSort
instead of recursing to QuickSort
.
The provided benchmark functions will time your Quicksort: adjust insertionSortCutoff
to a reasonable value (of which there is a fairly wide range).
The built-in sorting implementation is included in the benchmark: it's noticeably slower that (at least my) Quicksort. I think that it's because the built-in sort promises to be stable, and our Quicksort doesn't. If anybody has an alternate explanation, let Greg know.
Writing Tests
In the provided exer9_test.go
, add some test functions that test for correct behaviour in:
Point.Scale()
Point.Rotate()
MeanStddev()
You can (and maybe should?) use the functions from the assert package in your tests.
Submitting
Submit your files through CourSys for Exercise 9.