DEV Community: Dorin

React: Subscribe to events and debounce with RxJS

Dorin — Fri, 27 Mar 2020 23:12:21 +0000

Today I would like to show you an easy way to subscribe to a window event in React and how you can debounce it, so that your callback is not called too often.

One scenario when this could prove useful, is if you want to make some kind of update on your page whenever the size of the window has changed.

So how do we know when the window has been resized? We can use the browser built-in method addEventListener, like so:

window.addEventListener('resize', handleResize);

And we unsubscribe with:

window.removeEventListener('resize', handleResize);

Only we are not going to do any of that. Instead we'll be using RxJS and its fromEvent method:

const listener = fromEvent(window, 'resize');

const subscription = listener.subscribe(handleResize);

// and unsubscribing with
subscription.unsubscribe();

Now let's add this to our React component function and use the useEffect hook to make a custom hook that is going to handle the subscription and unsubscription. We'll call this custom hook useWindowResize.

import { fromEvent, timer } from 'rxjs';
import { debounce } from 'rxjs/operators';

function useWindowResize(people) {
  useEffect(() => {
    const handleResize = () => {
      // Do stuff
    }

    const event = fromEvent(window, 'resize').pipe(debounce(() => timer(1000)));

    const subscription = event.subscribe(handleResize);

    return () => subscription.unsubscribe();
  })
}

Now every time the window is being resizes, we are going to be calling the handleResize method. But, it will never be called more often than once per second (1000ms).

Have a nice day!

JS: The difference between "undefined", "null" and "void 0"

Dorin — Fri, 17 Jan 2020 15:25:52 +0000

🍎🍊🍌

Why am I even asking this question, you might think. Well, the thing is that I have been asked this recently and I feel that I didn't give a good enough answer.

Even though undefined, null and void 0 have something in common, they cannot be compared directly because they represent different concepts with different functionalities.

Instead of doing a one to one comparison between those, I think it makes more sense to explain what each of them is and by doing this, it will be clear how different they are.

`undefined`

It is a global property or a primitive value.

So, as you see, when you say "undefined" you could potentially be referring to two very different things.

The global property named undefined has a value of undefined by default. This property could be modified up until ES5, when it was made read-only. Therefore if you try to change its value, you won't be able to:

undefined = 1

console.log(undefined) // undefined

There is a way though to override the value of the global undefined property, even in the latest version of EcmaScript. This can be done by creating a scoped variable called undefined and giving it an arbitrary value. We are basically shadowing the built-in undefined.

(function() {
  var undefined = 1

  console.log(undefined) // 1
})()

When it comes to the value of undefined, this is the default value for any variable that has been declared but not initialised.

var one

console.log(one) // undefined

Also, undefined is the value of an object's property that does not exist.

var obj = {
  hello: 'world'
}

console.log(obj.goodbye) // undefined

`null`

It is a primitive value.

Similarly to the undefined primitive value it is also falsy, but it is not an identifier or a global property.

Unlike undefined, it is not being assigned by default to anything in JavaScript. You can only manually set the value of null.

var nothing = null

console.log(nothing) // null

The common use case for null is to assign it to an identifier where an object can be expected but none is relevant.

Because both null and undefined are falsy, when compared using the abstract comparison ==, the result is going to be true. But, using the strict comparison ===, the result is going to be false.

console.log(null == undefined) // true
console.log(null === undefined) // false

`void <expression>`

It is an operator.

Unlike both undefined and null, it does not represent a primitive value.

The connection between void and the other two is that it always returns the value of undefined.

Its purpose is to evaluate an expression (usually for its side effects) and then return undefined.

console.log(void 0) // undefined
console.log(void (1 + 1)) // undefined
console.log(void (() => 5)) // undefined

One other use for void is to retrieve the original value of undefined when the undefined identifier could have been overridden.

(function() {
  var undefined = 1

  console.log(undefined) // 1

  var realUndefined = void 1

  console.log(realUndefined) // undefined
})()

But, as you remember the global property undefined is read-only, so we can retrieve its value without using void, like so:

(function() {
  var undefined = 1

  console.log(undefined) // 1

  console.log(global.undefined) // undefined
})()

Conclusion

Quick recap:

undefined is a global property or a primitive value
null is a primitive value
void <expression> is an operator

As we have seen, we can find uses for all of them but only one of them is really indispensable: undefined.

We can easily get by without null and especially void which seems to be an artifact of the past.

Algorithms in Go: Heap Sort

Dorin — Sun, 12 Jan 2020 22:35:18 +0000

Introduction

Heap Sort is a sorting algorithms which uses the Heap data structure to arrange a set of elements in an ascending or descending order.

In a previous post I have shown how to build a Max Heap. I suggest that you check it out first before continuing with the sorting algorithm.

Data Structures in Go: Heap

Dorin ・ Jan 5 '20

#go #datastructure #heap

As you know now, there are two main types of heaps: Max Heap and Min Heap. Once we have implemented those, it is a trivial matter to do the sorting.

In a Max Heap, we are going to always have the largest element at the top, followed by the smaller ones. And in a Min Heap, the opposite is going to be true. Hence we are going to use the Max Heap for sorting in a descending order and the Min Heap for sorting in an ascending order.

Time complexity

The time complexity of a heap sort is O(n lg n), since the initial processing of the input into a heap takes O(n) and for every element extraction we need to make adjustments that take O(lg n ).

How does it work?

If we want to sort a set of elements in ascending order then we:

Create a Min Heap from the elements. This is going to place the smallest element at the top.
Extract the minimum (top) element until we exhaust the heap and place them in a new array/slice, sequentially.
The resulting array/slice will automatically be sorted in an ascending order.

The sort in a descending order, we are going to follow the same steps as above, but instead will create a Max Heap.

Implementation

In this implementation, I have used the Heap data structures I have created earlier and created two methods: SortAscending and SortDescending.

package heapsort

import (
    "github.com/dorin131/go-data-structures/maxheap"
    "github.com/dorin131/go-data-structures/minheap"
)

// SortAscending : sort ascending a slice of integers using Heap Sort
func SortAscending(input []int) []int {
    result := []int{}

    mh := minheap.New(input)

    for range input {
        result = append(result, mh.ExtractMin())
    }

    return result
}

// SortDescending : sort descending a slice of integers using Heap Sort
func SortDescending(input []int) []int {
    result := []int{}

    mh := maxheap.New(input)

    for range input {
        result = append(result, mh.ExtractMax())
    }

    return result
}

To test that our sorting works correctly, I have used Go's built-in sort library.

func TestSortAscending(t *testing.T) {
    tests := []struct {
        Given []int
    }{
        {[]int{4, 9, 10, 0, -4, 7}},
        {[]int{1000, 100, 10, 0, -1000}},
        {[]int{1, 1, 1, 1}},
        {[]int{}},
        {[]int{777}},
    }
    for n, test := range tests {
        correctlySorted := make([]int, len(test.Given))
        copy(correctlySorted, test.Given)
        result := SortAscending(test.Given)

        if len(result) != len(test.Given) {
            t.Errorf("[%d] Lengths don't match", n)
            return
        }

        sort.Slice(correctlySorted, func(i, j int) bool {
            return correctlySorted[i] < correctlySorted[j]
        })

        for k := range correctlySorted {
            if correctlySorted[k] != result[k] {
                t.Errorf("[%v] Expected: %v, Got: %v\n", n, correctlySorted, result)
                return
            }
        }
        fmt.Printf("[%v] Correctly sorted: %v\n", n, result)
    }
}

Source code

dorin131 / go-algorithms

A collection of algorithms implemented in Go

go-algorithms

A collection of algorithms implemented in Go

Insertion Sort
Merge Sort
Heap Sort

View on GitHub

To follow

Stay tuned for the next post which is going to be on Priority Queues, which are also based on Heaps!

Data Structures in Go: Heap

Dorin — Sun, 05 Jan 2020 19:23:04 +0000

Introduction

In this article I want us to look at my implementation of a Heap data structure in Go. I assume that you are already familiar with the theory behind what a Heap is and its properties but if you're not then I will try to briefly explain this to you below and also tell you about some resources where you can learn more.

What is a Heap

If I had to explain it in my own words, I would say that a Heap is a data structure which can be visualised as a nearly-complete binary tree (read my post on Trees) and stores its data in an underlying array. By looking at one, you would probably assume that it is based on a linked list, but in fact it is not. Using a Heap we can sort items at a O(n*logn) time complexity and also create priority queues.

We say that a Heap is a nearly-complete binary tree because the lowest level might not be complete, like in the example above.

Also, there are two types of heaps: Max Heap (see above) and Min Heap. The difference between them is that in a Max Heap, we have the largest element at the top, followed by smaller children. And in a Min Heap we have the smallest element at the top, with larger ones following.

For more information on heaps I recommend the following resources:
Abdul Bari's video explanation
MIT lecture on Heaps

Implementation

I have implemented both a Max Heap and a Min Heap in Go, but for the sake of brevity and because the implementations are very similar, I will only go through the Max Heap in this article. You can find both implementations, plus some other data structures in the repository below.

dorin131 / go-data-structures

A collection of data structures implemented in Go

go-data-structures

An implementation in Go of the following data structures:

Linked List
Stack
Queue
Binary Search Tree
Graph
Hash Table
Min Heap
Max heap

View on GitHub

As I mentioned earlier, the Min and Max Heaps are quite similar, so I created a heap package that I shared between both of them using embedding.

Let's start with the heap package. In it I have created a Heap struct with an Items field of type slice of integers, which will hold all the values in our heap.

Also it has the Size field that holds the size of the heap. We need this because we might have elements in the Items slice which are not part of the heap. This is going to be used for sorting.

All the other methods in here are just helper functions that let us easily access elements in our Heap.

/*
Package heap provides helper methods for a Min Heap or a Max Heap
Not to be used on its own.
*/
package heap

// Heap : contains a slice which holds the underlying heap data
type Heap struct { // the total number of elements, which doesn't go down on extract
    Items []int
}

// GetLeftIndex : get left index of a Heap node
func (h *Heap) GetLeftIndex(parentIndex int) int {
    return 2*parentIndex + 1
}

// GetRightIndex : get right index of a Heap node
func (h *Heap) GetRightIndex(parentIndex int) int {
    return 2*parentIndex + 2
}

// GetParentIndex : get parent index of a Heap node
func (h *Heap) GetParentIndex(childIndex int) int {
    return (childIndex - 1) / 2
}

// HasLeft : check if node at index has left node
func (h *Heap) HasLeft(index int) bool {
    return h.GetLeftIndex(index) < len(h.Items)
}

// HasRight : check if node at index has right node
func (h *Heap) HasRight(index int) bool {
    return h.GetRightIndex(index) < len(h.Items)
}

// HasParent : check if node at index has parent node
func (h *Heap) HasParent(index int) bool {
    return h.GetParentIndex(index) >= 0
}

// Left : get left node value, given an index
func (h *Heap) Left(index int) int {
    return h.Items[h.GetLeftIndex(index)]
}

// Right : get right node value, given an index
func (h *Heap) Right(index int) int {
    return h.Items[h.GetRightIndex(index)]
}

// Parent : get parent node value, given an index
func (h *Heap) Parent(index int) int {
    return h.Items[h.GetParentIndex(index)]
}

// Swap : swap values of two nodes at specified indeces
func (h *Heap) Swap(indexOne, indexTwo int) {
    h.Items[indexOne], h.Items[indexTwo] = h.Items[indexTwo], h.Items[indexOne]
}

Next we have the actual Max Heap package which is going to use the structure we created earlier.

It has two exported methods: Insert and ExtractMax, which let us add and retrieve values off the Heap.

But the most interesting methods are probably maxHeapifyUp and maxHeapifyDown. The first one starts at an index and pushes the value up the heap until it reaches a position where it is smaller than the parent and the children are are smaller than it is. And the second will also start at an index and push the value down until it gets into a position that satisfies the Max Heap data structure.

Lastly we have the buildMaxHeap method that takes any slice of integers and creates a Max Heap out of them. It is called every time we initialise a new heap with a pre-populated slice.

/*
Package maxheap provides a Max Heap data structure
*/
package maxheap

import (
    "log"

    "github.com/dorin131/go-data-structures/heap"
)

// MaxHeap : represents a Max heap data structure
type MaxHeap struct {
    *heap.Heap
}

// New : returns a new instance of a Heap
func New(input []int) *MaxHeap {
    h := &MaxHeap{
        &heap.Heap{
            Items: input,
        },
    }

    if len(h.Items) > 0 {
        h.buildMaxHeap()
    }

    return h
}

func (h *MaxHeap) buildMaxHeap() {
    for i := len(h.Items)/2 - 1; i >= 0; i-- {
        h.maxHeapifyDown(i)
    }
}

// Insert : adds an element to the heap
func (h *MaxHeap) Insert(item int) *MaxHeap {
    h.Items = append(h.Items, item)
    lastElementIndex := len(h.Items) - 1
    h.maxHeapifyUp(lastElementIndex)

    return h
}

// ExtractMax : returns the maximum element and removes it from the Heap
func (h *MaxHeap) ExtractMax() int {
    if len(h.Items) == 0 {
        log.Fatal("No items in the heap")
    }
    minItem := h.Items[0]
    lastIndex := len(h.Items) - 1
    h.Items[0] = h.Items[lastIndex]

    // shrinking slice
    h.Items = h.Items[:len(h.Items)-1]

    h.maxHeapifyDown(0)

    return minItem
}

func (h *MaxHeap) maxHeapifyUp(index int) {
    for h.HasParent(index) && h.Parent(index) < h.Items[index] {
        h.Swap(h.GetParentIndex(index), index)
        index = h.GetParentIndex(index)
    }
}

func (h *MaxHeap) maxHeapifyDown(index int) {
    // iterate until we have a child node smaller than the index value
    for (h.HasLeft(index) && h.Items[index] < h.Left(index)) ||
        (h.HasRight(index) && h.Items[index] < h.Right(index)) {
        // if both children are smaller
        if (h.HasLeft(index) && h.Items[index] < h.Left(index)) &&
            (h.HasRight(index) && h.Items[index] < h.Right(index)) {
            // compare the children and swap with the largest
            if h.Left(index) > h.Right(index) {
                h.Swap(index, h.GetLeftIndex(index))
                index = h.GetLeftIndex(index)
            } else {
                h.Swap(index, h.GetRightIndex(index))
                index = h.GetRightIndex(index)
            }
            // else if only left child is smaller than swap with it
        } else if h.HasLeft(index) && h.Items[index] < h.Left(index) {
            h.Swap(index, h.GetLeftIndex(index))
            index = h.GetLeftIndex(index)
            // else it must be the right child that is smaller, so we swap with it
        } else {
            h.Swap(index, h.GetRightIndex(index))
            index = h.GetRightIndex(index)
        }
    }
}

Once you got your head around the Max Heap, try to have a look at the Min Heap implementation and see what the differences are. There are very few.

If you think you have a better way of doing any of the parts above, please feel free to make a PR!

Happy data structuring! :)

Video

Supercharge your TypeScript with AssemblyScript

Dorin — Fri, 03 Jan 2020 21:04:23 +0000

Introduction

So you’re using TypeScript at work or your personal project? That’s fantastic! Take advantage of those types and produce better, more readable and bug-free JavaScript!
And now you’re looking to take things to the next level and get super-fast execution times? You’re in the right place then.

WebAssembly

You’ve probably heard of WebAssembly already. If not, here is a brief description of what WebAssembly is:

WebAssembly (abbreviated Wasm) is a binary instruction format for a stack-based virtual machine. Wasm is designed as a portable target for compilation of high-level languages like C/C++/Rust, enabling deployment on the web for client and server applications. (https://webassembly.org/)

Yes, you read that right, you can write code in your favourite mega-efficient low level programming language, compile that to WebAssembly (binary V8 code) and call it from within your JS/TS code!

AssemblyScript

What if I told you than you don’t need to know/learn a new language to write dazzling-quick TypeScript? With the help of AssemblyScript, you can write TypeScript-like code with real types and better performance, which compiles to WebAssembly.

So what is AssemblyScript?

AssemblyScript compiles a strict subset of TypeScript (a typed superset of JavaScript) to WebAssembly using Binaryen. (https://docs.assemblyscript.org/)

It’s as simple as that. You write code in a language which is basically a subset of TypeScript which is going to compile to WebAssembly.

How do I get this to work?!

If you start a project from scratch you can follow the steps below exactly. Otherwise if you’re adding AssemblyScript to an existing project, you might want to skip some steps or do them slightly differently, depending on what you’ve already got.
You can also clone the the demo repository I have created just for you:

https://github.com/dorin131/assemblyscript-in-typescript

npm init
Initialising NPM.
npm i -S typescript assemblyscript @types/node
Installing TypeScript, AssemblyScript and Node types.
npx tsc --init
Initialising TypeScript. This will create a tsconfig.json file in your root directory.
npx asinit .
Initialising AssemblyScript. This will add a few NPM scripts in your package.json and also add a few other files which will help us to get started with AssemblyScript much quicker.
In tsconfig.json add the properties below. We are basically just configuring the TypeScript compiler a bit by setting the root and destination paths and telling it to ignore the /node_modules and /assembly folders.
```
  {
    "compilerOptions": {
      "outDir": "./dist",
      "rootDir": "./"
    },
    "exclude": [
      "node_modules",
      "assembly"
    ]
  }
```
In package.json add the scripts below. Every time you make a change to your code, you will have to run npm run build and then npm start. Notice how when we start with Node, we pass two flags to it: --experimental-wasm-modules and --experimental-modules. This is required, so that Node can load the *.wasm files. Also make sure you’re using at least version 12 of Node.
```
  {
    "start": "node --experimental-modules --experimental-wasm-modules ./dist/index.js",
    "build": "npm run asbuild && tsc -p ./tsconfig.json && npm run copy",
    "copy": "rm -rf dist/build/ && cp -r build dist/build/"
  }
```
Rename index.js to loader.ts, add any missing types and export the WebAssembly instance to be used from other files (https://github.com/dorin131/assemblyscript-in-typescript/blob/master/loader.ts)

Demo benchmark

By implementing the fibonacci sequence function, which takes number of the fibonacci element and returns its value, in both TypeScript and AssemblyScript, I wanted to run a very simple benchmark.
This is the TypeScript code:


function fibonacci(n: number): number {
  return n < 1 ? 0
       : n <= 2 ? 1
       : fibonacci(n - 1) + fibonacci(n - 2);
}

And the AssemblyScript code:

export function fibonacci(n: i32): i32 {
  return n < 1 ? 0
       : n <= 2 ? 1
       : fibonacci(n - 1) + fibonacci(n - 2);
}

Running both of these with an input of 45, resulted in the same output 1,134,903,170, but different times!
The TypeScript version took 9331.856ms
The AssemblyScript version took 7285.571ms
A performance improvement of 22% in this specific case.

Conclusion

As you can see, getting started with AssemblyScript is very easy and the syntax is almost the same as TypeScript’s (remember, it’s a subset).
In our very simple fibonacci example we saw a performance increase of 22%, but I am quite sure that the impact can be much greater in more complex code, where the V8 engine will struggle to optimise the untyped JavaScript.

WebAssembly is easy — a hello world example

Dorin — Wed, 01 Jan 2020 17:13:32 +0000

Introduction

I like to think of WebAssembly as of Assembly. It gives you a few simple building blocks that you can arrange and combine to create almost anything. It’s a bit like playing with Legos.

As a new technology though, it has a few entry barriers which can put off someone who just wanted to try it out. The code that is usually referred to as the “glue” between WASM and JS is not pretty and requires you to have a more in-depth knowledge of WASM to be able to make sense of or put together.

But there are ways to make developing in WebAssembly easy and enjoyable. I am going to talk about them below.

Your first “Hello World” in WASM

It has become a tradition already to first attempt to write a “Hello World” application in a new language that you are trying out. Usually this will just print out these words to the standard output or in some other visual way.

In WASM, it is a bit different though. The “Hello World” equivalent is often an addition function, which takes two integer arguments and returns their sum. There is a good reason why we are not attempting to print a string. Strings do not exist in WebAssembly as a type. We can have a string of bytes in memory which have a string encoded but any manipulation will have to be done on a byte level.
This is our addition function in WASM (text format):


(module
  (func (export "add") (param $n1 i32) (param $n2 i32) (result i32)
    get_local $n1
    get_local $n2
    i32.add
  )
)

Let’s break this down quickly and see what’s happening there line by line:

We declare a new module. All of your WebAssembly code has to be contained in a module.
Declaring a function which we export with the name add. This will allow us to call it from JS with add(). Then we say that it has two parameters of type 32bit Integer named $n1 and $n2. Lastly we say that our function is going to return another 32bit Integer.
Put on stack $n1 from local memory.
Put on stack $n2 from local memory.
The built-in i32.add function will take the last two values from the stack, add them and return the sum.

That it pretty much it. The syntax is not C/JS-like but pretty easy to understand. Every element is a node and we can have nodes nested in other nodes, which act as parameters.

How to run it

Now that you have your very first WebAssembly application, you want a quick and easy way to test it. This is where people often stumble.

To be able to test this function you will have to load the WASM code into JavaScript and call it from there. Our goal is to be able to call our add() function with two arguments and read the output number.

The easiest way to do this, that I know of, is using inline-webassembly NPM package. And you would end up with a JS file like this:

const iw = require('inline-webassembly');

iw(`
  (module
    (func (export "add") (param $n1 i32) (param $n2 i32) (result i32)
      get_local $n1
      get_local $n2
      i32.add
    )
  )`
).then((wasmModule) => {
  const sum = wasmModule.add(44, 99);
  console.log(`Sum = ${sum}`); // 143
});

Conclusion

Now that you know how you can easily create and use WebAssembly code, there is nothing stopping you from refactoring performance critical parts of your code using WASM.

Happy assembling!

Video

How can I improve my coding videos

Dorin — Tue, 31 Dec 2019 19:33:15 +0000

Recently I started making video versions for some of the posts that I am posting here. But it's hard to tell whether they're any good as people usually don't leave comments.

Here's my channel:

https://www.youtube.com/channel/UCfFe22CVJ0e0o91QLDrwxPw/

If there was one thing that I could improve, what would it be?

Thank you 🙇

How To Publish an NPM Package in 2020

Dorin — Tue, 31 Dec 2019 16:50:02 +0000

Introduction

In essence, publishing an npm package is just one command, but there are some things that you have to take care of before doing that.

Step-by-Step

Here are the steps I followed before publishing my first package:

Create a free account on https://www.npmjs.com/.
Log into the npm CLI by running npm login.
Create a folder for your new package which would normally have the same name.
Make sure that you ran npm init and have all the right values filled-in in the package.json file.
Carefully choose the name, as that is going to be the name that everyone is going to use to install your package.
Set the version number using the semantic versioning format. It should look something like this: “v1.2.3”. The first number is the major version and should be incremented every time you deploy a breaking change. The second number is the minor version and should go up with every new non-breaking feature. And, lastly, we have the patch/fix number. Also, at the same time, create a new release in GitHub (or your other VCS) with a matching version. (Read more)
Add a types field which will point to your types definition file. You don’t have to do this step but with the rapid increase of TypeScript and better IDEs, you are doing the developer a big favor. The types file will be a *.ts file written in TypeScript and describing the types, interfaces, etc. of your package. (Read more)
Specify the place where your code is hosted by filling in the repository field. (Read more)
Have a think about how you want to license your package and set the correct license value. If you are not sure, go to this website https://choosealicense.com/ which will make this very easy for you.
Check your .gitignore file and verify that you are not including any personal or unnecessary files in your repository.
Add an .npmignore file which will exclude specific files from your npm package. I personally have added the test files in here, as we don’t need to have them in the package.
Take your time to write a nice README.md file, where you explain to your future users how to install the package, how to use it, and maybe give some examples. The contents of this file will also appear on this website.
Now you’re almost ready to publish, but before you do so, run npm pack, which will generate a *.tgz file containing all the files exactly how they will end up in your npm package. This will let you double-check that everything has been set up correctly and you are going to publish the right thing.
Just before publishing, you are going to run a quick test locally. Create a new folder, initialize npm (npm init) and install your package with npm install -S ./path/to/your/package. This will install the package from your local directory and you can try to use it as if it was already published.
Assuming that you have done all the steps above and it all worked as expected, you can now publish your package with npm publish.

Conclusion

Congratulations, you now have a brand new npm package.

You can see your package on npm like so: https://www.npmjs.com/package/inline-webassembly

Algorithms in Go: Merge Sort

Dorin — Mon, 30 Dec 2019 23:47:25 +0000

Introduction

Following the insertion sort algorithm which we have implemented in the previous post, it was only natural to follow with the implementation of merge sort.

Compared with the insertion sort which has a time complexity of O(n²), the merge sort is more efficient, with a time complexity of O(n*log(n)). This means that it will be able to handle an increasing number of elements faster. See the graph below for a visual comparison.

The strategy used by this algorithm is called divide and conquer, which means that we split our problem in smaller chunks, which makes it easier to solve.

There are two main steps in performing this type of a sort. First we have to divide the array and then merge the elements. Both of these will happen recursively. So every time we merge, we have two sorted arrays, which we have to combine into one. This is done easily by popping the smallest element of one of the two arrays until one of them is depleted and then appending the rest.

Visually, it would look something like this.

Implementation

The code for merge sort is not as straight forward as for the insertion sort but it makes sense if analysed carefully.

package mergesort

// This is the only exported function which will take a slice as an input
// and return a different slice with the original integers sorted
func Sort(input []int) []int {
    // making a new slice and copying the contents of the input
    // into it
    // this slice is going to be subsequently mutated so that
    // we get the desired order of elements
    sorted := make([]int, len(input))
    copy(sorted, input)

    // calling the private "subSort" function which can sort a
    // sub-slice, by taking two more arguments: the start and
    // end index
    subSort(sorted, 0, len(input)-1)
    return sorted
}

// this function is going to call itself recursively with the left
// and the right halves of the input slice (the divide)
// then call the "merge" function (the conquest)
func subSort(sorted []int, leftStart int, rightEnd int) {
    // stop the recursion if there is nothing to divide
    if leftStart >= rightEnd {
        return
    }
    // calculating the middle element so that we can divide our
    // slice
    middle := (leftStart + rightEnd) / 2
    // calling itself recursively with both halves
    subSort(sorted, leftStart, middle)
    subSort(sorted, middle+1, rightEnd)
    // merging the two sorted halves
    merge(sorted, leftStart, rightEnd)
}

func merge(sorted []int, leftStart int, rightEnd int) {
    // creating a temporary slice, as we can't easily do it in place
    temp := make([]int, len(sorted))
    copy(temp, sorted)

    // the end of the left sub-slice will end in the middle
    leftEnd := (leftStart + rightEnd) / 2
    // the start of the right slice will be right after the left ends
    rightStart := leftEnd + 1

    left := leftStart
    right := rightStart
    index := leftStart

    // this is the loop where the actual sorting happens
    // we iterate until either the left or the right sub-slice
    // runs out of elements
    for left <= leftEnd && right <= rightEnd {
        // here we start adding elements to the temporary
        // slice we created above
        // we choose the smaller element every time
        if sorted[left] < sorted[right] {
            temp[index] = sorted[left]
            left++
        } else {
            temp[index] = sorted[right]
            right++
        }
        index++
    }

    // here we append to the temporary slice the remaining elements
    // that were not picked in the loop above
    // first we do it for the left and the for the right sub-slice
    // one of them will not contain any remaining elements
    // so will make no changes
    copy(temp[index:rightEnd+1], sorted[right:rightEnd+1])
    copy(temp[index:rightEnd+1], sorted[left:leftEnd+1])
    // finally we store the sorted numbers from the temporary slice
    // into our sorted slice
    copy(sorted, temp)
}

Source code

dorin131 / go-algorithms

A collection of algorithms implemented in Go

go-algorithms

A collection of algorithms implemented in Go

Insertion Sort
Merge Sort
Heap Sort

View on GitHub

Video

Algorithms in Go: Insertion Sort

Dorin — Sun, 29 Dec 2019 18:34:20 +0000

Introduction

One of the most basic sorting algorithms is the insertion sort. It is also relatively easy to understand as it closely mimics a common sorting strategy that humans normally use when sorting playing cards in their hand.
Even though its time complexity is O(n²) for the worst case, it still performs well for small input sizes.
Below is an illustration of the steps taken to perform a insertion sort:

Implementation

The main two parts of the code below are the two for loops. In the first one, we go through every element of the initial slice, starting with the second (see (a) above) and we compare it iteratively backwards with the previous elements. Whenever the previous element is greater than the current one, we move it one position forward. Once the inner loop reaches the condition to stop, we assign the value of the current element to precede the last element that was moved forward. By doing this, we end up with a sorted slice.

func Sort(a []int) []int {
    // creating a new slice of a size equal to the original
    result := make([]int, len(a))
    // copying elements from the original slice to the new slice
    copy(result, a)
    // iterating through all elements of the slice starting with the second
    for i := 1; i < len(result); i++ {
        // key holds the current value 
        key := result[i]
        // j holds the index of the previous value
        j := i - 1
        // we iterate backwards starting with the previous value and compare it with the current value
        for j >= 0 && result[j] > key {
            // if the previous value is greater then we move it forward one position
            result[j+1] = result[j]
            // we decrement the index for the previous value so that we check the next value backwards
            j--
        }
        // at the end of the inner loop we want to potentially move the current value of the main loop to a new position (if anything was shifted above)
        result[j+1] = key
    }
    // returning the sorted slice
    return result
}

Go specific decisions

As Go does not make a copy of the slice after it has been passed into a function, we had to make sure that we are no mutating the underlying array of the original slice and therefore had to create a new slice of the size of the original and copy into it the numbers.

Source code

dorin131 / go-algorithms

A collection of algorithms implemented in Go

Please feel free to make PRs with improvements

More algorithms are coming soon!

Video

Data Structures in Go: Hash Table

Dorin — Sat, 28 Dec 2019 16:22:52 +0000

Introduction

The time has come to implement one of the most commonly used data structures in software development - the Hash Table!

A hash table is a data structure that implements an associative array, allowing us to store pairs of keys and values that can be accessed at an expected O(1) time (O(n) - worst case for a bad implementation).

Personally I love this data structure. It works a bit like magic! How could you access a random key's value at constant time?

Here is how it works:

Create an array of a length equal to the expected number of key/value pairs in your hash table. The bigger the array, the lower the chance of collisions (explained further below).
Create a hashing function which will take the value of the key you want add and transform it into a number. The better this function is, the lower the chance of collisions.
Take the number generated by the hashing function and calculate the modulo with the array length. (e.g. if the hash is 1234 and the array length is 100, then calculate 1234 % 100). This is going to be the index in the array where you are going to store the value.

That is pretty much how it works in a nutshell. One of the most important things in a hash map is probably the hashing function. It can make the difference between a great and a very poor hash map.

In the implementation that follows, for a hash table that allows only string keys, I chose to use the following hash function:
char[0] * 31^n-1 + char[1] * 31^n-2 + ... + char[n-1]

Also, I have mentioned above collisions a couple of times. A collision happens when the array indices for two different keys happens to be the same. This could be because of a bad hashing function or a too small of an underlying array. Both of these can be fixed though. You can use a better hashing function and you can also dynamically grow the array when needed.

But collisions will happen, so then what do we do about it? Instead of storing our value as is in the array, we are going to store it in a linked list (or array) together with the un-hashed key. So, whenever we try to retrieve or modify a key value, we walk through that linked list and make sure that we are manipulating the correct key (if there are multiple at that index).

Luckily we have implemented a linked list already! And we're going to use it here :)

Data Structures in Go: Linked List

Dorin ・ Dec 22 '19

#go #linkedlist #linked #list

Below is an illustration of a hash table:

(Source: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Hashing/hashing.html)

Implementation

To start with, we are going to choose an array size for the underlying data store. In the current implementation this is going to stay fixed, but a more advanced version of this would be able to dynamically create a larger array once the number of keys reaches the length of the array.

const arrayLength = 100

Then as always we create a struct for out data structure. The only field we have is for the array hose every element will be a pointer to a linked list (github.com/dorin131/go-data-structures/linkedlist).

type HashTable struct {
    data [arrayLength]*linkedlist.LinkedList
}

Next we create another struct type for the contents of the linked list nodes. In this implementation, the key has to be a string and the value can be any type.

type listData struct {
    key   string
    value interface{}
}

Also we add a constructor function.

func New() *HashTable {
    return &HashTable{
        [arrayLength]*linkedlist.LinkedList{},
    }
}

And like we discussed earlier we are going to need a hashing function and a function to get the index for a hashed key.

func hash(s string) int {
    h := 0
    for pos, char := range s {
        h += int(char) * int(math.Pow(31, float64(len(s)-pos+1)))
    }
    return h
}

func index(hash int) int {
    return hash % arrayLength
}

Now it's time to add our Set and Get methods. These are going to let us add a key to the map and retrieve the value of a key respectively.

In the Set method, we first calculate the index for our key, by first hashing it and then getting the modulo. Then if there is nothing at that position already then we initialise a new linked list, otherwise we iterate through the list and check whether we need to update an existing value or add a new one.

func (h *HashTable) Set(k string, v interface{}) *HashTable {
    index := index(hash(k))

    if h.data[index] == nil {
        h.data[index] = linkedlist.New()
        h.data[index].Append(listData{k, v})
    } else {
        node := h.data[index].Head
        for {
            if node != nil {
                d := node.Data.(listData)
                if d.key == k {
                    d.value = v
                    break
                }
            } else {
                h.data[index].Append(listData{k, v})
                break
            }
            node = node.Next
        }
    }
    return h
}

And for the Get method we start the same, by calculating the index and then we look through the linked list (if it exists) and look for our value.

func (h *HashTable) Get(k string) (result interface{}, ok bool) {
    index := index(hash(k))
    linkedList := h.data[index]

    if linkedList == nil {
        return "", false
    }
    node := linkedList.Head
    for {
        if node != nil {
            d := node.Data.(listData)
            if d.key == k {
                return d.value, true
            }
        } else {
            return "", false
        }
        node = node.Next
    }
}

Conclusion

The next steps with the current implementation would be to make our underlying array expandable. But I'll leave that to you. Let me know how you went about doing that!

Source code with tests

dorin131 / go-data-structures

A collection of data structures implemented in Go

Video

Data Structures in Go: Graph

Dorin — Thu, 26 Dec 2019 22:28:18 +0000

Introduction

Unlike the queue, the stack and the linked list, the graph is a non-linear data structure, similar to the tree. It is composed of a collection of nodes which are connected to each other. The connections are called edges and can be either directed or non-directed. The edges can also have weights associated to them. These could represent distances, times or any other kind of information which describes that connection.

Implementation

As with the other data structures, there are several types of graphs and I had to make a choice here. Eventually I decided to implement a weighted directed graph. This means that every edge is going to have a direction and a weight associated to it.

To start with we created a struct which will hold the references to all the nodes in the graph. The order of nodes in this slice is going to be important because the index of the graph is going to also be its ID.

// Graph : represents a Graph
type Graph struct {
    nodes []*GraphNode
}

Next we created a struct for an individual node. A node will have an id field and an edges field which is a map of node IDs and weights.

So, if node 0 is linked to node 1, with an edge of weight 7 then we are going to add to the edges map a key 1 with the value 7.

// GraphNode : represents a Graph node
type GraphNode struct {
    id    int
    edges map[int]int
}

As always we add a constructor function.

// New : returns a new instance of a Graph
func New() *Graph {
    return &Graph{
        nodes: []*GraphNode{},
    }
}

Now we are going to add the following methods: AddNode, AddEdge, Neighbors, Nodes and Edges.

The AddNode method is going to add a new node at the first empty position of the Graph's nodes field, which is going to be equal to the length of this field. The return value is going to be the new id.

// AddNode : adds a new node to the Graph
func (g *Graph) AddNode() (id int) {
    id = len(g.nodes)
    g.nodes = append(g.nodes, &GraphNode{
        id:    id,
        edges: make(map[int]int),
    })
    return
}

For AddEdge we have to pass the IDs of two nodes in the order that we want the direction of the edge to be in, and the edge's weight.

// AddEdge : adds a directional edge together with a weight
func (g *Graph) AddEdge(n1, n2 int, w int) {
    g.nodes[n1].edges[n2] = w
}

Next, the Neighbors method is going to iterate through all nodes and their edges to find the neighbors of a specific node ID. This is the most expensive function of all.

// Neighbors : returns a list of node IDs that are linked to this node
func (g *Graph) Neighbors(id int) []int {
    neighbors := []int{}
    for _, node := range g.nodes {
        for edge := range node.edges {
            if node.id == id {
                neighbors = append(neighbors, edge)
            }
            if edge == id {
                neighbors = append(neighbors, node.id)
            }
        }
    }
    return neighbors
}

Then we create a method Nodes that is going to list the IDs of all nodes.

// Nodes : returns a list of node IDs
func (g *Graph) Nodes() []int {
    nodes := make([]int, len(g.nodes))
    for i := range g.nodes {
        nodes[i] = i
    }
    return nodes
}

And finally, we create the Edges method which is going to list all the edges as a slice of arrays, which contain the ID of the start node, the ID of the end node and the weight of the edge.

// Edges : returns a list of edges with weights
func (g *Graph) Edges() [][3]int {
    edges := make([][3]int, 0, len(g.nodes))
    for i := 0; i < len(g.nodes); i++ {
        for k, v := range g.nodes[i].edges {
            edges = append(edges, [3]int{i, k, int(v)})
        }
    }
    return edges
}

Conclusion

A good next step when studying graphs is to also implement a search/traversal method. You can choose between BFS (breadth first search) and DFS (depth first search). But I will leave this to you ;)