diff options
Diffstat (limited to 'gemfeed/2023-04-09-algorithms-in-golang-part-1.gmi')
| -rw-r--r-- | gemfeed/2023-04-09-algorithms-in-golang-part-1.gmi | 229 |
1 files changed, 229 insertions, 0 deletions
diff --git a/gemfeed/2023-04-09-algorithms-in-golang-part-1.gmi b/gemfeed/2023-04-09-algorithms-in-golang-part-1.gmi new file mode 100644 index 00000000..2ac5faa8 --- /dev/null +++ b/gemfeed/2023-04-09-algorithms-in-golang-part-1.gmi @@ -0,0 +1,229 @@ +# Algorithms in Go - Part 1 + +> Published at 2023-04-09T21:48:36+03:00 + +``` + ,_---~~~~~----._ + _,,_,*^____ _____``*g*\"*, + / __/ /' ^. / \ ^@q f +[ @f | @)) | | @)) l 0 _/ + \`/ \~____ / __ \_____/ \ + | _l__l_ I + } [______] I + ] | | | | + ] ~ ~ | + | | + | | +``` + +This is the first blog post about my Algorithms in Go series. I am not a Software Developer in my day job. In my current role, programming and scripting skills are desirable but not mandatory. I have been learning about Data Structures and Algorithms many years ago at University. I thought it would be fun to revisit/refresh my knowledge here and implement many of the algorithms in Go. + +=> ./2023-04-09-algorithms-in-golang-part-1.gmi 2023-04-09 Algorithms in Go - Part 1 (You are currently reading this) + +This post is about setting up some basic data structures and methods for this blog series. I promise, everything will be easy to follow in this post. + +## Type constraints + +First, the package `ds` (data structures) defines the `types.go`. All examples will either operate on the `Integer` or `Number` type: + +```go +package ds + +import ( + "golang.org/x/exp/constraints" +) + +type Integer interface { + constraints.Integer +} + +type Number interface { + constraints.Integer | constraints.Float +} + +``` + +## ArrayList + +Next comes the `arraylist.go`, which defines the underlying data structure all the algorithms of this series will use. `ArrayList` is just a type alias of a Go array (or slice) with custom methods on it: + +```go +package ds + +import ( + "fmt" + "math/rand" + "strings" +) + +type ArrayList[V Number] []V + +func NewArrayList[V Number](l int) ArrayList[V] { + return make(ArrayList[V], l) +} +``` + +As you can see, the code uses Go generics, which I refactored recently. Besides the default constructor (which only returns an empty `ArrayList` with a given capacity), there are also a bunch of special constructors. `NewRandomArrayList` is returning an `ArrayList` with random numbers, `NewAscendingArrayList` and `NewDescendingArrayList` are returning `ArrayList`s in either ascending or descending order. They all will be used later on for testing and benchmarking the algorithms. + +```go +func NewRandomArrayList[V Number](l, max int) ArrayList[V] { + a := make(ArrayList[V], l) + for i := 0; i < l; i++ { + if max > 0 { + a[i] = V(rand.Intn(max)) + continue + } + a[i] = V(rand.Int()) + } + return a +} + +func NewAscendingArrayList[V Number](l int) ArrayList[V] { + a := make(ArrayList[V], l) + for i := 0; i < l; i++ { + a[i] = V(i) + } + return a +} + +func NewDescendingArrayList[V Number](l int) ArrayList[V] { + a := make(ArrayList[V], l) + j := l - 1 + for i := 0; i < l; i++ { + a[i] = V(j) + j-- + } + return a +} +``` + +## Helper methods + +The `FirstN` method only returns the first N elements of the `ArrayList`. This is useful for printing out only parts of the data structure: + +```go +func (a ArrayList[V]) FirstN(n int) string { + var sb strings.Builder + j := n + + l := len(a) + if j > l { + j = l + } + + for i := 0; i < j; i++ { + fmt.Fprintf(&sb, "%v ", a[i]) + } + + if j < l { + fmt.Fprintf(&sb, "... ") + } + + return sb.String() +} +``` + +The `Sorted` method checks whether the `ArrayList` is sorted. This will be used by the unit tests later on: + +```go +func (a ArrayList[V]) Sorted() bool { + for i := len(a) - 1; i > 0; i-- { + if a[i] < a[i-1] { + return false + } + } + return true +} +``` + +And the last utility method used is `Swap`, which allows swapping the values of two indices in the `ArrayList`: + +```go +func (a ArrayList[V]) Swap(i, j int) { + aux := a[i] + a[i] = a[j] + a[j] = aux +} + +``` + +## Sleep sort + +Let's implement our first algorithm, sleep sort. Sleep sort is a non-traditional and unconventional sorting algorithm based on the idea of waiting a certain amount of time corresponding to the value of each element in the input `ArrayList`. It's more of a fun, creative concept rather than an efficient or practical sorting technique. This is not a sorting algorithm you would use in any production code. As you can imagine, it is quite an inefficient sorting algorithm (it's only listed here as a warm-up exercise). This sorting method may also return false results depending on how the Goroutines are scheduled by the Go runtime. + + +```go +package sort + +import ( + "codeberg.org/snonux/algorithms/ds" + "sync" + "time" +) + +func Sleep[V ds.Integer](a ds.ArrayList[V]) ds.ArrayList[V] { + sorted := ds.NewArrayList[V](len(a)) + + numCh := make(chan V) + var wg sync.WaitGroup + wg.Add(len(a)) + + go func() { + wg.Wait() + close(numCh) + }() + + for _, num := range a { + go func(num V) { + defer wg.Done() + time.Sleep(time.Duration(num) * time.Second) + numCh <- num + }(num) + } + + for num := range numCh { + sorted = append(sorted, num) + } + + return sorted +} +``` + +### Testing + +For testing, we only allow values up to 10, as otherwise, it would take too long to finish: + +```go +package sort + +import ( + "fmt" + "testing" + + "codeberg.org/snonux/algorithms/ds" +) + +func TestSleepSort(t *testing.T) { + a := ds.NewRandomArrayList[int](10, 10) + a = Sleep(a) + if !a.Sorted() { + t.Errorf("Array not sorted: %v", a) + } +} +``` + +As you can see, it takes `9s` here for the algorithm to finish (which is the highest value in the `ArrayList`): + +```sh +❯ go test ./sort -v -run SleepSort +=== RUN TestSleepSort +--- PASS: TestSleepSort (9.00s) +PASS +ok codeberg.org/snonux/algorithms/sort 9.002s +``` + +I won't write any benchmark for sleep sort; that will be done for the algorithms to come in this series :-). + +E-Mail your comments to hi@paul.cyou :-) + +=> ../ Back to the main site |