func Main ( ) { }

Friday, March 15, 2019

Big O Notation (Beginner's Guide)

Big O notation is used to represent of the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

Hopefully this article will help you gain an understanding of the basics of Big O and Logarithms.

O(1) - Constant time complexity

O(1) describes an algorithm that will always execute in the same time regardless of the size of the input data set.

bool isFirstNumberEqualToOne(List<Integer> numbers) {

  return numbers.get(0) == 1;

O(n) - Linear time complexity

O(n) describes the complexity of an algorithm that increases linearly and in direct proportion to the number of inputs. This is a good example of how Big O Notation describes the worst case scenario as the function could return the true after reading the first element or false after reading all n elements.

bool ContainsValue(List<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

O(n²) - Quadratic time complexity
O(n²) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. Adding more nested iterations through the input will increase the complexity which could then represent O(n³) with 3 total iterations and O(n⁴) with 4 total iterations.

bool ContainsDuplicates(List<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O(2ⁿ)
O(2ⁿ) represents a function whose performance doubles for every element in the input. This example is the recursive calculation of Fibonacci numbers. The function falls under O(2ⁿ) as the function recursively calls itself twice for each input number until the number is less than or equal to one.

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

O(log n) - Logarithmic time complexity

O(log n) represents a function whose complexity increases logarithmic-ally as the input size increases. This makes O(log n) functions scale very well so that the handling of larger inputs is much less likely to cause performance problems.

The example O(log n), Binary Search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.

The example below uses a binary search to check if the input list contains a certain number. In simple terms, it splits the list in two on each iteration until the number is found or the last element is read. This method has the same functionality as the O(n) example — although the implementation is completely different and more difficult to understand. But, this is rewarded with a much better performance with larger inputs (as seen in the table). The downside of this sort of implementation is that a Binary Search relies on the elements to already be in the correct order. This adds a bit of overhead performance wise if the elements need to be ordered before traversing through them.
There is much more to cover about Big O Notation but hopefully you now have a basic idea of what Big O Notation means and how that can translate into the code that you write.

bool containsNumber(List<Integer> numbers, int comparisonNumber) {

  int low = 0;

  int high = numbers.size() - 1;

  while (low <= high) {

    int middle = low + (high - low) / 2;

    if (comparisonNumber < numbers.get(middle)) {

      high = middle - 1;

    } else if (comparisonNumber > numbers.get(middle)) {

      low = middle + 1;

    } else {

      return true;

  return false;

Graph showing how the number of operations

increases with complexity

Wednesday, February 13, 2019

Go Interfaces Tutorial

Typically, if you see a function or a method that expects an empty interface, then you can typically pass anything into this function/method.

Let's see first example main.go below:

package main

import (
 "fmt"
)

func myFunc(x interface{}) {
 fmt.Println(x)
}

func main() {
 var my_number int
 my_number = 50
 
 myFunc(my_number)
}

If we then go to run this then we should see that it runs successfully and prints out our integer value:

$ go run main.go
50

Interface is very useful, by defining a function that takes in an interface{}, we essentially give ourselves the flexibility to pass in anything we want.
If we define a type based off this interface then we are forced to implement all of the functions or methods defined within that interface type.

Let's see second example main.go below:

package main

import "fmt"

type Sport interface {
 TypeSport()
}

type ChessSport struct {
 Name string
}

type FootballSport struct {
 Name string
}

func (b ChessSport ) TypeSport() {
 fmt.Printf("%s goes sport\n", b.Name)
}

func (b FootballSport ) TypeSport() {
 fmt.Printf("%s goes Football Sport\n", b.Name)
}

func main() {
 var athletes1 ChessSport
 athletes1.Name = "Joko"
 athletes1.TypeSport()

 var athletes2  FootballSport 
 athletes2.Name = "Budi"
 athletes2.TypeSport()
}

Should we wish, we could then create an array of type Sport which could store both our ChessSport and FootballSport objects.

var athletes []Sport
athletes = append(athletes , athletes1)
athletes = append(athletes , athletes2)

Hopefully, this article useful. Thank you

Other Topics:

Tuesday, February 12, 2019

Emscripten and SDL2 Tutorial --- WebAssembly C++

I believe that most C/C++ programmers are very interested with WebAssembly. Emscripten provides a number of ways to solve the first problem of making files on the server accessible to C/C++ programs.

SDL (Simple DirectMedia Layer) is a cross-platform development library designed to provide low level access to audio, keyboard, mouse, joystick, and graphics hardware via OpenGL and Direct3D.

This is just to show on how SDL can be implemented into WebAssembly by displaying an image.

I hope you like it and let's get started

Environment Specification
I am using Ubuntu 16.04 LTS with standard build tools for C/C++.

If you need HelloWorld Tutorial, you can find here.

Writing Code

$ touch hello.cpp

#include <stdio.h>
#include <SDL2/SDL.h>
#include <SDL2/SDL_image.h>
#include <emscripten.h>
#include <unistd.h>
#include <stdlib.h>

int testImage(SDL_Renderer* renderer, const char* fileName)
{
SDL_Surface *image = IMG_Load(fileName);
if (!image)
{
     printf("IMG_Load: %s\n", IMG_GetError());
     return 0;
}
int result = image->w;

SDL_Rect dest = {.x = 200, .y = 100, .w = 200, .h = 200};

SDL_Texture *tex = SDL_CreateTextureFromSurface(renderer, image);

SDL_RenderCopy (renderer, tex, NULL, &dest);

SDL_DestroyTexture (tex);

SDL_FreeSurface (image);

return result;
}

int main()
{
SDL_Init(SDL_INIT_VIDEO);

SDL_Window *window;
SDL_Renderer *renderer;

SDL_CreateWindowAndRenderer(600, 400, 0, &window, &renderer);

int result = 0;

SDL_SetRenderDrawColor(renderer, 255, 255, 255, 255);
SDL_RenderClear(renderer);

result |= testImage(renderer, "golang.png");

SDL_RenderPresent(renderer);

printf("you should see an image.\n");

return 0;
}

Compile It
$ emcc hello.c -O2 -s USE_SDL=2 -s USE_SDL_IMAGE=2 -s SDL2_IMAGE_FORMATS='["png"]'     --preload-file assets -o hello.html

Run It
$ emrun hello.html

Resut

Thank you

Other Topics:

Thursday, January 24, 2019

Compiling C/C++ to WebAssembly (Hello World Guide)

I believe that most C/C++ programmers have heard about web assembly but most of them had trouble on how to getting started. This is a simple guide on how to compile C/C++ into WebAssembly. As usual in programming example, I will start with 'Hello World'.

I hope you like it and let's get started

Environment Specification
I am using Ubuntu 16.04 LTS with standard build tools for C/C++.

$ sudo apt-get install build-essential cmake python git

Compiling the Tools
We need to install toolchain for the firstime for C/C++ language.

$ git clone https://github.com/juj/emsdk.git

$ cd emsdk
$ ./emsdk install --build=Release sdk-incoming-64bit binaryen-master-64bit
$ ./emsdk activate --build=Release sdk-incoming-64bit binaryen-master-64bit
$ source ./emsdk_env.sh --build=Release
$ echo "source $(pwd)/emsdk_env.sh --build=Release > /dev/null" >> ~/.bashrc

This processes require disk space and take a while for compiling process.

compiling result

Compiling 'Hello World'
Let's start to write code in C/C++ language.(in my case, I will use C++)

$ touch hello.cpp

#include<iostream>

int main() {
  std::cout << "Hello World" << std::endl;
  return 0;
}

Compile it

$ em++ hello.cpp -s WASM=1 -o hello.html

After compiling, it will result hello.html, hello.js and hello.wasm files.
For hello.wasm will contain the compiled code.

Run it

$ emrun hello.html --port 8080

This will start and open browser to see the result

result Hello World

Thank you

Other Topics:

Tuesday, August 7, 2018

Implementing Selection Sort in Golang

What Is Selection Sort?
Selection sort is sorting algorithm specifically an in-place comparison sort. The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right..

Time Complexity
The time complexity for this algorithm is O(N^2) and making it inefficient on large lists.

Implementation
package main

import (
    "fmt"
    "math/rand"
    "time"x
)

func main() {
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    selectionsort(slice)
    fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}

// Generates random numbers
func generateSlice(size int) []int {

    slice := make([]int, size, size)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < size; i++ {
        slice[i] = rand.Intn(999) - rand.Intn(999)
    }
    return slice
}

func selectionsort(items []int) {
    var n = len(items)
    for i := 0; i < n; i++ {
        var minIdx = i
        for j := i; j < n; j++ {
            if items[j] < items[minIdx] {
                minIdx = j
            }
        }
        items[i], items[minIdx] = items[minIdx], items[i]
    }
}
Result:

Monday, June 25, 2018

Implementing Insertion Sort in Golang

What Is Insertion Sort?
Insertion sort similar to card ordering. Imagine that you are playing a card game. You're holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you're holding are still sorted. In selection sort, each element that you add to the sorted subarray is no smaller than the elements already in the sorted subarray. But in our card example, the new card could be smaller than some of the cards you're already holding, and so you go down the line, comparing the new card against each card in your hand, until you find the place to put it. You insert the new card in the right place, and once again, your hand holds fully sorted cards. Then the dealer gives you another card, and you repeat the same procedure. Then another card, and another card, and so on, until the dealer stops giving you cards.

Time Complexity
The time complexity for this algorithm is O(N^2) and Best case time complexity is O(n) when the list is already sorted.

Implementation
package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    slice := generateSlice(20)
    fmt.Println("\n--- Unsorted --- \n\n", slice)
    insertionSort(slice)
    fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}

// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {

    slice := make([]int, size, size)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < size; i++ {
        slice[i] = rand.Intn(999) - rand.Intn(999)
    }
    return slice
}

func insertionSort(items []int) {
    var n = len(items)
    for i := 1; i < n; i++ {
        j := i
        for j > 0 {
            if items[j-1] > items[j] {
                items[j-1], items[j] = items[j], items[j-1]
            }
            j = j - 1
        }
    }
}

Result:

Tuesday, March 13, 2018

Calling C functions from Go

Sometimes we need to call C function from Go to get more performance and to reuse existing C/C++ libraries in Go application by automatically generating c-go bindings for a given set of C headers and the manifest file.

Let's try to create an example on how to call C function from Go by using static go libraries.

This sample has been tested on Ubuntu 16.04 LTS.

create folder call_c_doubler and create file as below

filename:Makefile
.PHONY: clean all

all:c_static_lib go_executable

c_static_lib:
    gcc -c doubler/*.c
    ar rs doubler.a *.o
    rm -rf *.o

go_executable:
    go build -o call_c_doubler

clean:
    rm -rf *.o *.a call_c_doubler


filename: main.go
package main

import "fmt"

// #cgo CFLAGS: -I${SRCDIR}/doubler
// #cgo LDFLAGS: ${SRCDIR}/doubler.an
// #include <stdlib.h>
// #inclue <libdoubler.h>
import "C"

func main() {
    fmt.Printf("Enter Go...\n")
    fmt.Printf("Double : %d\n", C.double_it(2))
    fmt.Printf("Exit Go...\n")
}

In folder call_c_doubler/doubler and create file as below
filename:libdoubler.c
#include "libdoubler.h"
#include <stdio.h>

int double_it(int x) {
    printf("Calling C function");
    return 2 * x;
}

filename:libdoubler.h
#ifndef DOUBLER_H
#define DOUBLER_H

int double_it(int x);

#endif

Then just run command make in your terminal to compile the program

Wednesday, February 28, 2018

GUI for Delve Debugger Gdlv

What is Gdlv?
Gdlv is a graphical interface to Delve for Linux, Windows and macOS. Previously, I posted Delve debugger in console mode Debugging Go programs with Delve
and now, I would like to introduce the graphical delve debugger.

Implementation
First make sure you have the latest version of delve installed:
go get -u github.com/derekparker/delve/cmd/dlv

then install gdlv:
go get -u github.com/aarzilli/gdlv

To start gdlv can be done by opening command prompt (cmd) then type command
gdlv debug main.go
and it will show GUI of delve debugger as shown as below

You can open other new window by clicking drop down box for example Globals window, Sources window, etc

Now, let us add break-point at line 7 by using command break main.go:7 shown as picture below. You can add break-point too by right click the line code and Set breakpoint.
To clear break-point, can be done by right click and select Clear breakpoint.

By opening new window sources then find your file source code by typing the filename. In my case, the filename is main.go and double click to open the file. You will see the break-point at line 6 and 7.

Type command continue and debugger will stop at line 6

By giving command next, it will go to next break point.
Command in Gdlv is the same command with Dlv.

Thank you

Debugging Go programs with Delve

What is Delve?
Delve aims to be a very simple and powerful tool, but can be confusing if you are not used to using a source level debugger in a compiled language. Tracking down bugs in your code can be a very frustrating experience. This is even more true of highly parallel code. Having a good debugger at your disposal can make all the difference when it comes to tracking down a difficult, or hand to reproduce bug in your code.

Implementation
I am using go version go1.8 windows/amd64. (Delve debugger can run in Linux, Windows and macOS.

Let's create a simple code in golang to demonstrate Delve debugger. The code shown as below:

filename: main.go
package main

import "fmt"

func main() {
    fmt.Println("Hello World")
    fmt.Println("Hello World")
    fmt.Println("Hello World")
}

Open your windows command prompt to perform Delve debugger by pressing Windows Key + R and type cmd then press enter. In command prompt, type command
dlv debug main.go

Then you will enter to dlv debug mode

to check delve command you can type help and it will shown all command that can be used for debugging

Let's add break-point at line 6 by using command
break main.go:6

add break-point at line 7 by using command
break main.go:7

Then you can start debug by using command
continue
and it will stop at break-point line 6

if you want to continue to the next break point, just using command
next
and it will go to the next break-point line 7

You can see the break-point with simbol => (blue color) it's in yellow box
command is in red box and output is in green box, shown as picture below

I think that's all. Thank you

Other topics: