03-data_structures.slide

Структури от данни
24.10.2018

fmi@golang.bg
http://fmi.golang.bg/
@fmi_golang

* Но преди това...

* Ретроспекция на домашното

- функции за еднократна употреба
- `defer` в `Generator` <3
- left foldedness

* Почти! Сега само малко...

* Въпрос за мъфин #1

Какво ще покаже следния код?

    func 4times4() (res int) {
        defer func() {
            res *= 4
        }
        return 4
    }
    fmt.Println(4times4())

- Синтактична грешка. `4times4` не е валидно име на функция.

* Въпрос за мъфин #2

С какво можем да сравняваме функции?

- Само с `nil`

* Въпрос за мъфин #3

Ако знаем, че `foo` е указател към `int` в масив, то как можем да вземем следващия елемент в масива?

- Не можем. Няма аритметика с указатели.

* Въпрос за мъфин #4

Кога се оценяват аргументите на `defer` функция?

- По време на оценяване на `defer` израза.


* Arrays

- По нашенски: масиви
- Последователност от еднакви по тип елементи
- С конкретна фиксирана дължина

.play code/data_structures/array.go /^func main()/,/^}/

Очевидно броим от 0


* Инициализация

    var x [5]string
    x[0] = "Баба"
    x[1] = "меца"
    x[2] = "яде"
    x[3] = "от"
    x[4] = "медеца"

или накратко:

    x := [6]float64{98, 93, 77, 82, 83}

Чакай малко! Подали сме само 5 числа.

    x[5] == 0


* Компилаторите могат да броят!

- Да, и ние бяхме изненадани

    x := [...]string{"Incredible", "isn't", "it?"}

- В този случай `x` е от тип `[3]string`

* Сравняване на масиви

Да разгледаме следния код

.play code/data_structures/array_comparison.go /dqdo/,/fmt/


* Големината на масив е част от типа му

.play code/data_structures/array_comparison_error.go /dqdo/,/fmt/


* Черва на масивите

- Те са стойности, копират се, а не се предават по стойност

    func (foo [100]uint32)

- Дори, когато правим

    a := [100]float64
    b := a

- Може да се избегне с указател към масив

    func (foo *[100]uint32)

- Няма нужда да го ползвате, ще видите защо след малко

* Полезнотии

- `len()` - връща размера като int
- `range` - ключова дума, която позволява да итерираме по индекс и стойност

    for index, value := range arr {
        ...
    }



    for index := 0; index < len(arr); index++ {
        value := arr[index]
        ...
    }

Тези два цикъла са еквивалентни

_(Заради_range_нямаме_нужда_от_foreach)_

* Това е много готино, но...

- Не могат да растат
- Или да се свиват
- Спомняте ли указателя към масив? А ако искаме да подадем масив с друга дължина?
- Какво е това!? Живеем в 2018, не може ли да се направи нещо?


* Slices

Като масивите имат дължина и могат да се индексират, но дължината им може да се променя*.

    var x []float64

Горното само създава променливата, а се инициализира по следния начин:

    x := make([]float64, 5)

Това указва на слайса да бъде с размер 5. Всеки слайс е част от масив с не по-малка дължина от слайса.

    x := make([]float64, 5, 10)

Това е същото като горното, но този слайс сочи към масив с размер 10.


* Без изрично `make(...)`

    numbers := []float64{0, 1.2, 3.4, 55.3}

- Създава slice-a "numbers" от тип []float64 и го запълва


* Слайсове в действие

    arr := [6]float64{1, 2, 3, 4, 5, 6}
    x := arr[1:5]

Създаваме слайс от втори до пети елемент включително на масива arr.

    x := arr[2:] // Взема всички без първите два елемента
    x := arr[:2] // Взема първите два елемента
    x := arr[:]  // Взема всички елементи


* Не точно масиви

- Външно се държат като такива
- Но всъщност един slice е (малка) структура, която е построена "върху" array
- Всички операции с тях са евтини
- Всяко оразмеряване прави _нов_ евтин слайс
- ... който "сочи" към същия масив в паметта


* Структура

.image assets/slice.jpg

    x := []int{2, 3, 5, 7, 11}

Създава нов slice, който сочи към нов масив от 5 елемента.

    y := x[1:3]

Създава нов slice, но не и нов масив - използва се вече съществуващия за x.

* Полезнотии


* len и cap

- `len(x)` - Взема размера на slice-а
- `cap(x)` - Взема размера на масива, към който slice-а сочи

.play code/data_structures/len_vs_cap.go /^func main()/,/^}/

* Нулева стойност

- Както всичко в Go си имат нулева стойност и това е nil

    var foo []uint32
    foo == nil // True

- `len` и `cap` връщат 0 за нулев slice

    len(foo) == cap(foo) == 0

* Резултатни slice-ове

- Ако разгледаме

    x := []uint32{0, 1, 2, 3, 4, 5, 6, 7}
    y := x[:]
    y[4] = 42
    x[4] == 42  // True

- `y` не копира съдържанието на `x`
- Kоето прави операцията много ефективна, независимо колко е голям `x`
- Подаването като аргумент на функция копира самия slice, но не стойностите на масива, към който сочи
- Създава се нов slice, който сочи към масива на оригинала

* `cap` - втори епизод

    x := []uint32{0, 1, 2, 3, 4, 5, 6, 7}
    y := x[2:4]  // [2, 3]
    y = y[:cap(y)]  // [2, 3, 4, 5, 6, 7]

- Опит да го увеличим над оригиналната големина на масива води до runtime panic

* append

Built-in функция, която добавя елементи към края на slice:

    sliceA := []int{1, 2, 3}
    sliceB := append(sliceA, 4, 5) // [1 2 3 4 5]

Може да добавя и един slice към друг:

    sliceC := append(sliceA, sliceB...)

Ако в резултатния slice има достатъчно място, той се използва непроменен. Ако няма, автоматично се заделя по-голям slice:

    sliceD := make([]int, 0, 3)   // len = 0, cap = 3
    sliceD = append(sliceD, 1, 2) // len = 2, cap = 3
    sliceD = append(sliceD, 2, 4) // len = 4, cap = 6

* Трик с append

Изтриване на n-ия елемент от слайс

	x := []int{1, 2, 3, 4, 5}
	x = append(x[:n], x[n+1:]...)

Ако n = 2:

	[]int{1, 2, 4, 5}


* copy(dst, src)

- Копира елементи от един слайс в друг
- Връща броя копирани елементи
- Source и destination може да се припокриват

* copy(dst, src) - примери

    var l int
    slice1 := []int{1, 2, 3, 4}
    slice2 := []int{7, 6, 5}

Копираме трите елемента от `slice2` в `slice1`

    l = copy(slice1, slice2) // slice1 = [7 6 5 4], l = 3

Копираме края на slice1 в началото му

    l = copy(slice1, slice1[2:]) // slice1 = [3 4 3 4], l = 2

Копираме slice1 в slice2

    l = copy(slice2, slice1) // slice2 = [1 2 3], l = 3
    // Копират се само първите 3 елемента, защото len(slice2) = 3


* slice "gotchas"

1. Опит за писане в неинициализиран слайс води до паника.

2. Масивите, в които се съхраняват данните на слайсовете, не се чистят от garbage collector-a, докато има референции (слайсове) към тях.

    // WARNING: shitty code, don't do this at home. We are professionals!
    func GetFileHeader(filename string) []byte {
        b, _ := ioutil.ReadFile(filename)
        return b[:10]
    }

Цялото съдържание на файла няма да бъде изчистено от паметта, докато първите 10 байта се ползват някъде.

Решение: copy() в нов слайс

* Maps

Неподредена колекция от двойки ключове и стойности

    var x map[string]int // Ключовете в x са низове, а стойностите числа


За да го инициализраме, ползваме `make`:

    x := make(map[string]int)

Подобно на слайсовете, писането в неинициализиран map води до паника.

Ползваме го почти както масиви и слайсове. Добавяне на стойност:

    x["key"] = 10

За да вземем стойност по ключ:

    value, ok := x["key"]

`ok` е `true`, ако съществува двойка с такъв ключ. В противен случай, `value` е нулевата стойност на типа (`""` за `string`) и `ok` е false.


* Полезнотии

- Бързо инициализиране:

    wordcount := map[string]int{"word1": 10, "word2": 5}

- Изтриването на стойност става с `delete`:

    x := make(map[string]int)
    delete(x, "key") // Изтрива двойката с ключ е "key". Ако няма такава, нищо не се случва.

- Проверка дали даден ключ съществува:

    if _, ok := x["key"]; ok {
        fmt.Println("key exists")
    }

- Итерирането става с `range`:

    for key, value := range m {
        fmt.Println("Key:", key, "Value:", value)
    }

* Ключове

- Трябва да а от "сравняем" тип

* Сравняване?

.link https://golang.org/ref/spec#Comparison_operators
- Накратко (и непълно): bool, numeric, string, channel, interface са сравними
- Масиви са сравними ако стойностите им са сравними и са равни когато всичките им стойности са равни
- Указатели са сравними и са равни когато сочат към една и съща променлива
- Структури са сравними, когато всичките им полета са сравними
- Има несравними неща, има и такива, които ще доведат до runtime panic ако ги сравнявате
- Прочетете поне веднъж спецификацията, където всичко е изброено пълно - кратка е

* Конкурентен достъп

- За конкурентност ще говорим по - нататък, но за сега запомнете следните неща
- Ако се чете и пише едновременно в array, slice или map, поведенито е недефинирано
- a.k.a. не са thread-safe
- Често се случва паника

* Конкурентен достъп (2)

Но има [[https://golang.org/pkg/sync/#Map][sync.Map]] в стандартната библиотека, който позволява конкурентен достъп.

* Structs

- Добре познатите C структури
- Контейнер, който съдържа полета от други типове

    type Person struct {
        name string
        age uint
    }

    var chochko Person
    chochko.name = "Чочко"
    chochko.age = 27

Други начини за инициализиране:

    chochko := Person{name: "Чочко", age: 27}
    chochko := Person{"Чочко", 27}


* new()

- Алокира памет, която да използваме за дадения тип
- Връща указател към нулирана, но не инициализирана памет

    chochko := new(Person)
    chochko.name = "Чочко"
    chochko.age = 27

- chochko е *Person, но се използва по същия начин ('cause -> is so 80s)

* new() vs. make()

new само заделя и нулира памет, а make инициализира, т.е.:

.play code/data_structures/new_vs_make.go

- Демек `make` се ползва само върху `slice` и `map`

* Следващия път

- Типове и интерфейси