Read "Streaming Systems" 1&2, Streaming 101 Read "F1, a distributed SQL database that scales" Read "Zanzibar, Google’s Consistent, Global Authorization System" Read "Spanner, Google's Globally-Distributed Database" Read "Designing Data-intensive applications" 12, The Future of Data Systems IOS development with Swift Read "Designing Data-intensive applications" 10&11, Batch and Stream Processing Read "Designing Data-intensive applications" 9, Consistency and Consensus Read "Designing Data-intensive applications" 8, Distributed System Troubles Read "Designing Data-intensive applications" 7, Transactions Read "Designing Data-intensive applications" 6, Partitioning Read "Designing Data-intensive applications" 5, Replication Read "Designing Data-intensive applications" 3&4, Storage, Retrieval, Encoding Read "Designing Data-intensive applications" 1&2, Foundation of Data Systems Three cases of binary search TAMU Operating System 2 Memory Management TAMU Operating System 1 Introduction Overview in cloud computing 2 TAMU Operating System 7 Virtualization TAMU Operating System 6 File System TAMU Operating System 5 I/O and Disk Management TAMU Operating System 4 Synchronization TAMU Operating System 3 Concurrency and Threading TAMU Computer Networks 5 Data Link Layer TAMU Computer Networks 4 Network Layer TAMU Computer Networks 3 Transport Layer TAMU Computer Networks 2 Application Layer TAMU Computer Networks 1 Introduction Overview in distributed systems and cloud computing 1 A well-optimized Union-Find implementation, in Java A heap implementation supporting deletion TAMU Advanced Algorithms 3, Maximum Bandwidth Path (Dijkstra, MST, Linear) TAMU Advanced Algorithms 2, B+ tree and Segment Intersection TAMU Advanced Algorithms 1, BST, 2-3 Tree and Heap TAMU AI, Searching problems Factorization Machine and Field-aware Factorization Machine for CTR prediction TAMU Neural Network 10 Information-Theoretic Models TAMU Neural Network 9 Principal Component Analysis TAMU Neural Network 8 Neurodynamics TAMU Neural Network 7 Self-Organizing Maps TAMU Neural Network 6 Deep Learning Overview TAMU Neural Network 5 Radial-Basis Function Networks TAMU Neural Network 4 Multi-Layer Perceptrons TAMU Neural Network 3 Single-Layer Perceptrons Princeton Algorithms P1W6 Hash Tables & Symbol Table Applications Stanford ML 11 Application Example Photo OCR Stanford ML 10 Large Scale Machine Learning Stanford ML 9 Anomaly Detection and Recommender Systems Stanford ML 8 Clustering & Principal Component Analysis Princeton Algorithms P1W5 Balanced Search Trees TAMU Neural Network 2 Learning Processes TAMU Neural Network 1 Introduction Stanford ML 7 Support Vector Machine Stanford ML 6 Evaluate Algorithms Princeton Algorithms P1W4 Priority Queues and Symbol Tables Stanford ML 5 Neural Networks Learning Princeton Algorithms P1W3 Mergesort and Quicksort Stanford ML 4 Neural Networks Basics Princeton Algorithms P1W2 Stack and Queue, Basic Sorts Stanford ML 3 Classification Problems Stanford ML 2 Multivariate Regression and Normal Equation Princeton Algorithms P1W1 Union and Find Stanford ML 1 Introduction and Parameter Learning

Golang basics

2018-10-24

Basics

Packages

  • Every program is made up of packages.
  • "math/rand" package comprise files beginning with package rand
  • Use parenthesized, “factored” import statement to group multiple packages.
  • In a package, a name is exported if it begins with a capital letter, like Pi or Println.
    • When importing a package, you can refer only to its exported names. Any “unexported” names are not accessible from outside the package.
package main

import (
	"fmt"
	"math/rand"
)

func main() {
	fmt.Println(math.Pi)
}

Functions

  • Type comes after the variable name.
  • Shorten x int, y int to `x, y int.
  • A function can return any number of results.
  • Go’s return values may be named. If so, they are treated as variables defined at the top of the function.
func add(x int, y int) int {
	return x + y
}

// any number of results
func swap(x, y string) (string, string) {
	return y, x
}

func main() {
	a, b := swap("hello", "world")
	fmt.Println(a, b)
}

// named return values
func split(sum int) (x, y int) {
	x = sum * 4 / 9
    y = sum - x
    // naked return, should be avoid in long functions
	return
}

Data types

  • The expression T(v) converts the value v to the type T.
// basic
bool

string

int  int8  int16  int32  int64
uint uint8 uint16 uint32 uint64 uintptr

byte // alias for uint8

rune // alias for int32
     // represents a Unicode code point

float32 float64

complex64 complex128
g := 0.867 + 0.5i // complex128

// conversions
i := 42
f := float64(i)
u := uint(f)

Variables

  • var statement can declare a list of variables.
    • Type is the last.
  • var statement can be at package or function level.
  • var can have initializers.
    • Type can be omitted in this case.
  • := for short assignment.
  • var statement can be “factored” into blocks.
  • Variables declared without an explicit initial value are given their zero value.
    • 0 for numeric types,
    • false for boolean types,
    • "" empty string for strings
package main

import "fmt"

var c, python, java bool

func main() {
	var i int
	fmt.Println(i, c, python, java)
}

// initializer
var i, j int = 1, 2
var c, python, java = true, false, "no!"

// short assignment
k := 3
c, python, java := true, false, "no!"

// var block
var (
	ToBe   bool       = false
	MaxInt uint64     = 1<<64 - 1
	z      complex128 = cmplx.Sqrt(-5 + 12i)
)

Constants

  • Constants are declared like variables, but with the const keyword.
  • Constants can be character, string, boolean, or numeric values.
  • Constants cannot be declared using the := syntax.
  • Numeric constants are high-precision values.
  • An untyped constant takes the type needed by its context.
const Pi = 3.14

const (
	// Create a huge number by shifting a 1 bit left 100 places.
	// In other words, the binary number that is 1 followed by 100 zeroes.
	Big = 1 << 100 // works, longer than 64-bit
	// Shift it right again 99 places, so we end up with 1<<1, or 2.
	Small = Big >> 99
)

Control flows

For loops

  • No parentheses around conditions.
  • Braces {} are required.
  • for can be used as while
sum := 0
for i := 0; i < 10; i++ {
	sum += i
}

// init and inc conditions can be empty 
for ; sum < 1000; {
	sum += sum
}

// while
sum := 1
for sum < 1000 {
	sum += sum
}

If

  • if can start with a short statement to execute before the condition.
    • Variables declared here are only in scope until the end of if and related else.
if v := math.Pow(x, n); v < lim {
	return v
} else {
	fmt.Printf("continue")
}

Switch

  • Only run the selected case; thus break is not needed.
  • switch cases need not be constants or integers.
switch os := runtime.GOOS; os {
case "darwin":
	fmt.Println("OS X.")
case "linux":
	fmt.Println("Linux.")
default:
	// freebsd, openbsd,
	// plan9, windows...
	fmt.Printf("%s.", os)
}

Defer

  • A defer statement defers the execution of a function until the surrounding function returns.
    • the function containing the defer statement
  • Deferred function calls are pushed onto a stack. When a function returns, its deferred calls are executed in last-in-first-out order.
func main() {
	fmt.Println("counting")

	for i := 0; i < 10; i++ {
		defer fmt.Println(i)
	}

	fmt.Println("done")
}

Advanced types

Pointers

  • *T is a pointer to a T value.
    • Its zero value is nil.
  • No pointer arithmetic.
// declare a pointer
var p *int

// get pointer
i := 42
p = &i

// get the value
fmt.Println(*p)

// set the int value
*p = 21

Structs

  • struct is a collection of fields.
// declare
type Vertex struct {
	X int
	Y int
}

// create an instance
v := Vertex{1, 2}
v2 := Vertex{X: 1} // 1, 0
v3 := Vertex{} // 0, 0

// set a field
v.X = 4

// get the pointer
p := &v

// set the field
(*p).X = 1
// or easier
p.X = 1

Arrays and slices

  • Array cannot be resized. [n]T
  • Slice is dynamically sized, flexible view into the element in an array. []T
    • Doesn’t store any data.
    • Changing the elements of a slice modifies the corresponding elements of its underlying array.
    • Zero value is nil.
    • Can be created with make
    • Can contain any type like other slices
    • func append(s []T, vs ...T) []T
      • Append values into a slice
      • A bigger array will be allocated if needed.
// declare
var a [2]string
primes := [6]int{2, 3, 5, 7, 11, 13}

a[0] = "Hello"
a[1] = "World"
fmt.Println(a[0], a[1])

// slices, exclude the last one
var s [] int = primes[1:4] // 1, 2, 3

// create a slice
q := []int{2, 3, 5, 7, 11, 13}
a := make([]int, 5) // len(a) = 5
a := make([]int, 5, 10) // len(a) = 5, capacity is 10
board := [][]string{
	[]string{"_", "_", "_"},
	[]string{"_", "_", "_"},
	[]string{"_", "_", "_"},
}

// omit high or low bounds
var a [10]int
a[0:10]
a[:10]
a[0:]
a[:]

// slice append
var s []int
s = append(s, 2, 3, 4)

Range

  • range form of the for loop iterates over a slice or map.
    • For slice, two values for each iteration: index and element
  • Skip one value by assigning _
var pow = []int{1, 2, 4, 8, 16, 32, 64, 128}

for i, v := range pow {
	fmt.Printf("2**%d = %d\n", i, v)
}

Maps

  • A map maps keys to values.
  • Zero value is nil.
m := make(map[string]Vertex)
m["Bell Labs"] = Vertex{
	40.68433, -74.39967,
}
fmt.Println(m["Bell Labs"])

//
var m = map[string]Vertex{
	"Bell Labs": Vertex{
		40.68433, -74.39967,
	},
	"Google": Vertex{
		37.42202, -122.08408,
	},
}

var m = map[string]Vertex{
	"Bell Labs": {40.68433, -74.39967},
	"Google":    {37.42202, -122.08408},
}

m[key] = elem
elem = m[key]
delete(m, key)
// test if a key is present
// use assign symbol if needed
elem, is_exist := m[key] // is_exist: bool

Functions

  • Functions are values too. They can be passed around just like other values.
    • May be used as function arguments and return values.
  • Go functions may be closures. A closure is a function value that references variables from outside its body.
    • The function may access and assign to the referenced variables; in this sense the function is “bound” to the variables.
func compute(fn func(float64, float64) float64) float64 {
	return fn(3, 4)
}

hypot := func(x, y float64) float64 {
	return math.Sqrt(x*x + y*y)
}

// closures
func adder() func(int) int {
	sum := 0
	return func(x int) int {
		sum += x
		return sum
	}
}

func main() {
	pos, neg := adder(), adder()
	for i := 0; i < 10; i++ {
		fmt.Println(
			pos(i),
			neg(-2*i),
		)
	}
}

Methods and interfaces

Methods

  • Go does not have classes; but we can define methods on types.
  • A method is a function with a special receiver argument.
  • Can only declare a method with a receiver whose type is defined in the same package as the method.
  • Can declare methods with pointer receivers.
    • Such methods can modify the value.
    • Such methods can take either a value or pointer as the receiver.
      • But functions can only take pointer as arguments.
    • Methods with value argument can take either pointer or value.
      • Functions must take values.
  • Use a pointer receiver
    • can modify the value.
    • avoid copying the value on each call.
type Vertex struct {
	X, Y float64
}

func (v Vertex) Abs() float64 {
	return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
	v := Vertex{3, 4}
	fmt.Println(v.Abs())
	// equivalent to
	fmt.Println(Abs(v))
}

// can define a new type and add methods
type MyFloat float64

// modify value
func (v *Vertex) Scale(f float64) {
	v.X = v.X * f
	v.Y = v.Y * f
}

Interface

  • An interface type is defined as a set of method signatures.
  • A value of interface type can hold any value that implements those methods.
  • No explicit declaration is needed, just implement those methods.
  • Interface values stores the value and its concrete type.
    • describe(i)
    • Call corresponding methods of the concrete type.
  • Handle nil value in methods of a type.
  • Type switch
  • Stringer
  • Error
  • Readers
    • The io package specifies the io.Reader interface, which represents the read end of a stream of data.
    • Many implementations for different cases.
    • err == io.EOF when stream ends.
type Abser interface {
	Abs() float64
}

type Vertex struct {
	X, Y float64
}

func (v *Vertex) Abs() float64 {
	return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

type MyFloat float64

func (f MyFloat) Abs() float64 {
	if f < 0 {
		return float64(-f)
	}
	return float64(f)
}

func main() {
	var a Abser
	f := MyFloat(-math.Sqrt2)
	v := Vertex{3, 4}

	a = f  // a MyFloat implements Abser
	a = &v // a *Vertex implements Abser

	// Error in the following line, v is a Vertex (not *Vertex)
	// and does NOT implement Abser.
	a = v

	fmt.Println(a.Abs())
}

// empty interface can hold values of any type
interface{}

// type assertion, access to an interface value's underlying concrete value.
var i interface{} = "hello"

s := i.(string)
fmt.Println(s)

s, ok := i.(string)
fmt.Println(s, ok)

f, ok := i.(float64) // zero value, false
fmt.Println(f, ok)

f = i.(float64) // panic
fmt.Println(f)

// type switch
func do(i interface{}) {
	switch v := i.(type) {
	case int:
		fmt.Printf("Twice %v is %v\n", v, v*2)
	case string:
		fmt.Printf("%q is %v bytes long\n", v, len(v))
	default:
		fmt.Printf("I don't know about type %T!\n", v)
	}
}

// Stringer interface, defined in fmt, can implement it to use Print 
type Stringer interface {
    String() string
}

type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%v (%v years)", p.Name, p.Age)
}

func main() {
	a := Person{"Arthur Dent", 42}
	z := Person{"Zaphod Beeblebrox", 9001}
	fmt.Println(a, z)
}

// Error interface built in, can fmt Print it
type error interface {
    Error() string
}

type MyError struct {
	When time.Time
	What string
}

func (e *MyError) Error() string {
	return fmt.Sprintf("at %v, %s",
		e.When, e.What)
}

// Reader
func (T) Read(b []byte) (n int, err error)

func read() {
	r := strings.NewReader("Hello, Reader!")

	b := make([]byte, 8)
	for {
		n, err := r.Read(b)
		fmt.Printf("n = %v err = %v b = %v\n", n, err, b)
		fmt.Printf("b[:n] = %q\n", b[:n])
		if err == io.EOF {
			break
		}
	}
}

Concurrency

Goroutines

  • go f(x, y, z) starts a new running goroutine, a lightweight thread.
  • goroutines run in the same address space, so access to shared memory must be synchronized.
    • sync package provides useful primitives.
func say(s string) {
	for i := 0; i < 5; i++ {
		time.Sleep(100 * time.Millisecond)
		fmt.Println(s)
	}
}

func main() {
	go say("world")
	say("hello")

	go func() {
		say("hello")
	}()
}

Channels

  • Channels are a typed conduit through which you can send and receive values with the channel operator, <-.
    • The data flows in the direction of the arrow.
  • Channels must be created before use.
  • By default, sends and receives block until the other side is ready. This allows goroutines to synchronize without explicit locks or condition variables.
  • Channels can be buffered. Provide the buffer length as the second argument to make to initialize a buffered channel.
    • Sends to a buffered channel block only when the buffer is full. Receives block when the buffer is empty.
ch <- v    // Send v to channel ch.
v := <-ch  // Receive from ch, and assign value to v.

ch := make(chan int) // create a channel

// e.g.
func sum(s []int, c chan int) {
	sum := 0
	for _, v := range s {
		sum += v
	}
	c <- sum // send sum to c
}

func main() {
	s := []int{7, 2, 8, -9, 4, 0}

	c := make(chan int)
	go sum(s[:len(s)/2], c)
	go sum(s[len(s)/2:], c)
	x, y := <-c, <-c // receive from c

	fmt.Println(x, y, x+y)
}

// buffered channels
ch := make(chan int, 100)
  • A sender can close a channel to indicate that no more values will be sent. Receivers can test whether a channel has been closed by assigning a second parameter to the receive expression.
    • v, ok := <-ch
    • Only sender can close the channel, never the receiver.
  • The loop for i := range c receives values from the channel repeatedly until it is closed.
  • The default case in a select is run if no other case is ready.

Select

  • The select statement lets a goroutine wait on multiple communication operations.
  • A select blocks until one of its cases can run, then it executes that case. It chooses one at random if multiple are ready.
func fibonacci(c, quit chan int) {
	x, y := 0, 1
	for {
		select {
		case c <- x:
			x, y = y, x+y
		case <-quit:
			fmt.Println("quit")
			return
		}
	}
}

func main() {
	c := make(chan int)
	quit := make(chan int)
	go func() {
		for i := 0; i < 10; i++ {
			fmt.Println(<-c)
		}
		quit <- 0
	}()
	fibonacci(c, quit)
}

// default
func main() {
	tick := time.Tick(100 * time.Millisecond)
	boom := time.After(500 * time.Millisecond)
	for {
		select {
		case <-tick:
			fmt.Println("tick.")
		case <-boom:
			fmt.Println("BOOM!")
			return
		default:
			fmt.Println("    .")
			time.Sleep(50 * time.Millisecond)
		}
	}
}

Mutex

  • Mutual exclusion: But what if we don’t need communication? What if we just want to make sure only one goroutine can access a variable at a time to avoid conflicts?
    • sync.Mutex provides Lock and Unlock
package main

import (
	"fmt"
	"sync"
	"time"
)

// SafeCounter is safe to use concurrently.
type SafeCounter struct {
	v   map[string]int
	mux sync.Mutex
}

// Inc increments the counter for the given key.
func (c *SafeCounter) Inc(key string) {
	c.mux.Lock()
	// Lock so only one goroutine at a time can access the map c.v.
	c.v[key]++
	c.mux.Unlock()
}

// Value returns the current value of the counter for the given key.
func (c *SafeCounter) Value(key string) int {
	c.mux.Lock()
	// Lock so only one goroutine at a time can access the map c.v.
	defer c.mux.Unlock()
	return c.v[key]
}

func main() {
	c := SafeCounter{v: make(map[string]int)}
	for i := 0; i < 1000; i++ {
		go c.Inc("somekey")
	}

	time.Sleep(time.Second)
	fmt.Println(c.Value("somekey"))
}

Examples

Equivalent binary trees

package main

import "golang.org/x/tour/tree"
import "fmt"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int, ) {
	if (t == nil) {
		return
	}
	Walk(t.Left, ch)
	ch <- t.Value
	Walk(t.Right, ch)
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)
	go func() {
		Walk(t1, ch1)
		close(ch1)
	}()
	go func() {
		Walk(t2, ch2)
		close(ch2)
	}()
	for {
		v1, ok1 := <- ch1
		v2, ok2 := <- ch2
		if (ok1 != ok2) {
			return false
		}
		if (!ok1) {
			return true
		}
		if (v1 != v2) {
			return false
		}
	}
}

func main() {
	res := Same(tree.New(1), tree.New(2))
	fmt.Println(res)
}

Reference


Creative Commons License
Melon blog is created by melonskin. This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
© 2016-2019. All rights reserved by melonskin. Powered by Jekyll.