1. Две реализации очереди FIFO в Go

Для временной очереди используйте слайс. Для long-living очередей удобнее использовать динамическую структуру данных, такую как связанный список.

Используем слайс

Простой способ реализовать временную структуру данных очереди в Go – использовать слайс:

• для enqueue-запроса используйте встроенную функцию append;
• для dequeue-запроса – применяйте слайс к первому элементу.
  

        var queue []string

queue = append(queue, "Hello ") // Enqueue
queue = append(queue, "world!")

for len(queue) > 0 {
    fmt.Print(queue[0]) // First element
    queue = queue[1:]   // Dequeue
}
    

        Hello world!
    

Следим за утечками памяти Go

Возможно, вы захотите удалить первый элемент перед dequeue-запросом.

        // Dequeue
queue[0] = "" // Erase element (write zero value)
queue = queue[1:]
    

Память, выделенная под массив, никогда не «вернется». При использовании долгоживущих очередей, используйте связанные списки.

Связанный список

Пакет container/list реализует двусвязный список, который можно использовать в качестве очереди.

        queue := list.New()

queue.PushBack("Hello ") // Enqueue
queue.PushBack("world!")

for queue.Len() > 0 {
    e := queue.Front() // Первый элемент
    fmt.Print(e.Value)

    queue.Remove(e) // Dequeue
}
    

        Hello world!
    

2. Основные реализации множества в Go

Реализация множества через map

Распространенный способ реализации множества в Go – использование map.

        set := make(map[string]bool) // Новое множество
set["Foo"] = true            // Создание
for k := range set {         // Цикл
    fmt.Println(k)
}
delete(set, "Foo")    // Удаление
size := len(set)      // Размер
exists := set["Foo"] 
    

Альтернативный подход

Если память, используемая под булевы значения, создает дискомфорт, вы можете заменить их пустыми структурами. В Go пустая структура, как правило, не использует всю память.

        type void struct{}
var member void

set := make(map[string]void) // Новое пустое множество
set["Foo"] = member          // Создание
for k := range set {         // Цикл
    fmt.Println(k)
}
delete(set, "Foo")      // Удаление
size := len(set)        // Размер
_, exists := set["Foo"]
    

3. Базовая структура стека (LIFO)

В Go реализовать структуру данных стека (очередь LIFO) можно с помощью слайса и функции append:

        var stack []string

stack = append(stack, "world!") // Push
stack = append(stack, "Hello ")

for len(stack) > 0 {
    n := len(stack) - 1 // Top element
    fmt.Print(stack[n])

    stack = stack[:n] // Pop
}
    

        Hello world!
    

Ознакомьтесь с понятием амортизированным временем для лучшего понимания процесса: добавление одного элемента к слайсу занимает постоянное амортизированное время.

4. Доступ к переменным среды Go

Для чтения и записи переменных окружения используйте функции Setenv, Getenv, Unsetenv и Environ :

        fmt.Printf("%q\n", os.Getenv("SHELL")) // "/bin/bash"

os.Unsetenv("SHELL")
fmt.Printf("%q\n", os.Getenv("SHELL")) // ""

os.Setenv("SHELL", "/bin/dash")
fmt.Printf("%q\n", os.Getenv("SHELL")) // "/bin/dash"
    

        for _, s := range os.Environ() {
    kv := strings.SplitN(s, "=", 2) // распаковка "ключ=значение"
    fmt.Printf("key:%q value:%q\n", kv[0], kv[1])
}
    

        key:"SHELL" value:"/bin/bash"
key:"SESSION" value:"ubuntu"
key:"TERM" value:"xterm-256color"
key:"LANG" value:"en_US.UTF-8"
key:"XMODIFIERS" value:"@im=ibus"
…
    

5. Доступ к приватным полям с рефлексией

В этом примере мы получаем доступ к несообщаемому полю len в структуре List пакета container/list:

        package list

type List struct {
    root Element
    len  int
}
    

Этот код считывает значение len с помощью рефлексии.

        package main

import (
    "container/list"
    "fmt"
    "reflect"
)

func main() {
    l := list.New()
    l.PushFront("foo")
    l.PushFront("bar")

    fv := reflect.ValueOf(l).Elem().FieldByName("len")
    fmt.Println(fv.Int()) // 2

    fv.Set(reflect.ValueOf(3))
}
    

        panic: reflect: reflect.Value.Set using value obtained using unexported field

goroutine 1 [running]:
reflect.flag.mustBeAssignable(0x1a2, 0x285a)
	/usr/local/go/src/reflect/value.go:225 +0x280
reflect.Value.Set(0xee2c0, 0x10444254, 0x1a2, 0xee2c0, 0x1280c0, 0x82)
	/usr/local/go/src/reflect/value.go:1345 +0x40
main.main()
	../main.go:18 +0x280
    

6. Bitmasks, bitsets и флаги

Битовая маска – множество булевых значений-флагов, представленных битами, состоящих из одного или нескольких чисел.

Пример использования простой битовой маски в Go

        type Bits uint8

const (
    F0 Bits = 1 << iota
    F1
    F2
)

func Set(b, flag Bits) Bits    { return b | flag }
func Clear(b, flag Bits) Bits  { return b &^ flag }
func Toggle(b, flag Bits) Bits { return b ^ flag }
func Has(b, flag Bits) bool    { return b&flag != 0 }

func main() {
    var b Bits
    b = Set(b, F0)
    b = Toggle(b, F2)
    for i, flag := range []Bits{F0, F1, F2} {
        fmt.Println(i, Has(b, flag))
    }
}
    

        0 true
1 false
2 true
    

Большие битсеты

Для представления больших битсетов может понадобиться кастомная структура данных. Есть удобный сторонний пакет bit, предоставляющий реализацию битового массива.

Поскольку битовый массив использует параллелизм, ограничивает доступ к памяти и использует кэш данных, часто он качественно превосходит другие структуры данных. Попробуйте код bit.Set из упомянутого пакета bit и вы будете приятно удивлены.

        const n = 50
sieve := bit.New().AddRange(2, n)
sqrtN := int(math.Sqrt(n))
for p := 2; p <= sqrtN; p = sieve.Next(p) {
    for k := p * p; k < n; k += p {
        sieve.Delete(k)
    }
}
fmt.Println(sieve)
    

        {2 3 5 7 11 13 17 19 23 29 31 37 41 43 47}
    

7. Проверка на простое число

Целочисленные типы

Для целочисленных типов используйте функцию ProbablyPrime(0) из пакета math/big. Этот тест на простые числа является 100% точным примерно для 2⁶⁴ вхождений.

        const n = 1212121
if big.NewInt(n).ProbablyPrime(0) {
    fmt.Println(n, "is prime")
} else {
    fmt.Println(n, "is not prime")
}
    

        1212121 is prime
    

Большие числа

Для больших чисел, необходимо обеспечить требуемое количество тестов из ProbablyPrime(n). Для n тестов вероятность возврата true для случайно выбранного непростого числа составляет не более (1/4)ⁿ. Для примера: при n = 20 на выходе получится 0,000,000,000,001.

        z := new(big.Int)
fmt.Sscan("170141183460469231731687303715884105727", z)
if z.ProbablyPrime(20) {
    fmt.Println(z, "is probably prime")
} else {
    fmt.Println(z, "is not prime")
}
    

        170141183460469231731687303715884105727 is probably prime
    

8. Поиск строк по шаблону

Как написать базовое CLI-приложение.

Этот пример является упрощенной версией команды grep из *nix. Код ищет в файле строки, содержащие заданный шаблон, и выводит их на экран.

        func main() {
    log.SetPrefix("grep: ")
    log.SetFlags(0) // no extra info in log messages

    if len(os.Args) != 3 {
        fmt.Printf("Usage: %v PATTERN FILE\n", os.Args[0])
        return
    }

    pattern, err := regexp.Compile(os.Args[1])
    if err != nil {
        log.Fatalln(err)
    }

    file, err := os.Open(os.Args[2])
    if err != nil {
        log.Fatalln(err)
    }
    defer file.Close()

    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        line := scanner.Text()
        if pattern.MatchString(line) {
            fmt.Println(line)
        }
    }
    if err := scanner.Err(); err != nil {
        log.Println(err)
    }
}
    

9. Аргументы и флаги командной строки

Вы можете получить доступ к аргументам командной строки, включая имя программы и флаги, через os.Args variable:

        func main() {
    if len(os.Args) != 3 {
        fmt.Println("Usage:", os.Args[0], "PATTERN", "FILE")
        return
    }
    pattern := os.Args[1]
    file := os.Args[2]
    // ...
}
    

        $ go build grep.go
$ ./grep
Usage: ./grep PATTERN FILE
    

Кстати, пакет flag реализует базовый синтаксический анализ флагов командной строки.

10. Вычисление абсолютного значения int/float в Go

Целые числа

Для целых чисел соответствующую функцию легко написать самостоятельно:

        // Abs возвращает абсолютноe значение x
func Abs(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}
    

Памятка: наименьшее значение целого числа со знаком не имеет соответствующего положительного значения:

• math.MinInt64 – это -9223372036854775808;
• math.MaxInt64 – это 9223372036854775807.
  

К сожалению, в таких случаях функция Abs возвращает отрицательное значение:

        fmt.Println(Abs(math.MinInt64))

// Output: -9223372036854775808
    

Впрочем, подобным образом ведут себя библиотеки Java и C.

Float

Функция math.Abs может возвращать и абсолютные значения:

        func Abs(x float64) float64
    

Частный случай:

        Abs(±Inf) = +Inf
Abs(NaN) = NaN
    

11. Вычисление максимума из двух int/float

Напишем код для вычисления минимума и максимума целых чисел. Используем math.Min и math.Max для чисел с плавающей точкой.

Int

        // Max возвращает большее из x или y
func Max(x, y int64) int64 {
    if x < y {
        return y
    }
    return x
}

// Min возвращает меньшее из x или y
func Min(x, y int64) int64 {
    if x > y {
        return y
    }
    return x
}
    

Float

        func Max(x, y float64) float64

func Min(x, y float64) float64
    

Частный случай:

        Max(x, +Inf) = Max(+Inf, x) = +Inf
Max(x, NaN) = Max(NaN, x) = NaN
Max(+0, ±0) = Max(±0, +0) = +0
Max(-0, -0) = -0

Min(x, -Inf) = Min(-Inf, x) = -Inf
Min(x, NaN) = Min(NaN, x) = NaN
Min(-0, ±0) = Min(±0, -0) = -0
    

12. Конвертирование размеров

Функции для преобразования размера файла в байтах в удобочитаемый формат. Следующий код поддерживает и формат SI (десятичный), и IEC (двоичный).

        func ByteCountSI(b int64) string {
    const unit = 1000
    if b < unit {
        return fmt.Sprintf("%d B", b)
    }
    div, exp := int64(unit), 0
    for n := b / unit; n >= unit; n /= unit {
        div *= unit
        exp++
    }
    return fmt.Sprintf("%.1f %cB",
        float64(b)/float64(div), "kMGTPE"[exp])
}

func ByteCountIEC(b int64) string {
    const unit = 1024
    if b < unit {
        return fmt.Sprintf("%d B", b)
    }
    div, exp := int64(unit), 0
    for n := b / unit; n >= unit; n /= unit {
        div *= unit
        exp++
    }
    return fmt.Sprintf("%.1f %ciB",
        float64(b)/float64(div), "KMGTPE"[exp])
}
    

13. Обрабатываем ошибки в Go

Строковая ошибка

        // простая строковая ошибка
err1 := errors.New("math: square root of negative number")

// с форматированием
err2 := fmt.Errorf("math: square root of negative number %g", x)
    

Кастомные ошибки с данными

Для такого типа ошибок необходимо объявить error interface:

        type error interface {
    Error() string
}
    

Два примера:

        type SyntaxError struct {
    Line int
    Col  int
}

func (e *SyntaxError) Error() string {
    return fmt.Sprintf("%d:%d: syntax error", e.Line, e.Col)
}
    

        type InternalError struct {
    Path string
}

func (e *InternalError) Error() string {
    return fmt.Sprintf("parse %v: internal error", e.Path)
}
    

Если Foo – это функция, возвращающая SyntaxError или InternalError, их можно обработать следующим образом:

        if err := Foo(); err != nil {
    switch e := err.(type) {
    case *SyntaxError:
        // Сделать что-то интересное с e.Line and e.Col.
    case *InternalError:
        // Прервать и сообщить о проблеме.
    default:
        log.Println(e)
    }
}
    

14. Создание картинок

Для программного создания PNG-изображения обычно используются пакеты image, image/color и image/png.

        width := 200
height := 100

upLeft := image.Point{0, 0}
lowRight := image.Point{width, height}

img := image.NewRGBA(image.Rectangle{upLeft, lowRight})

// Цвета определяются значениями Red, Green, Blue, Alpha uint8.
cyan := color.RGBA{100, 200, 200, 0xff}

// Устанавливается цвет каждому пикселю.
for x := 0; x < width; x++ {
    for y := 0; y < height; y++ {
        switch {
        case x < width/2 && y < height/2: // upper left quadrant
            img.Set(x, y, cyan)
        case x >= width/2 && y >= height/2: // lower right quadrant
            img.Set(x, y, color.White)
        default:
            // Используем нулевое значение.
        }
    }
}

f, _ := os.Create("image.png")
png.Encode(f, img)
    

Вывод:

15. Генерация перестановок

Как сгенерировать все перестановки среза или строки в Go:

        func Perm(a []rune, f func([]rune)) {
    perm(a, f, 0)
}

func perm(a []rune, f func([]rune), i int) {
    if i > len(a) {
        f(a)
        return
    }
    perm(a, f, i+1)
    for j := i + 1; j < len(a); j++ {
        a[i], a[j] = a[j], a[i]
        perm(a, f, i+1)
        a[i], a[j] = a[j], a[i]
    }
}
    

Пример использования:

        Perm([]rune("abc"), func(a []rune) {
	fmt.Println(string(a))
})
    

Вывод:

        abc
acb
bac
bca
cba
cab
    

16. Хэш-суммы: MD5, SHA-1, SHA-256

Хэш строки

Чтобы вычислить хэш строки или байтового слайса, используйте функцию Sum пакетов crypto/md5, crypto/sha1 или crypto/sha256.

        s := "Foo"

md5 := md5.Sum([]byte(s))
sha1 := sha1.Sum([]byte(s))
sha256 := sha256.Sum256([]byte(s))

fmt.Printf("%x\n", md5)
fmt.Printf("%x\n", sha1)
fmt.Printf("%x\n", sha256)
    

        1356c67d7ad1638d816bfb822dd2c25d
201a6b3053cc1422d2c3670b62616221d2290929
1cbec737f863e4922cee63cc2ebbfaafcd1cff8b790d8cfd2e6a5d550b648afa
    

Хэш файла

Для вычисления хэша строки или потока:

• создайте новый hash.Hash из пакета crypto/md5, crypto/sha1 или crypto/sha256;
• добавьте данные, записав их в io.Writer;
  
• извлеките контрольную сумму функцией Sum.
  

        input := strings.NewReader("Foo")

hash := sha256.New()
if _, err := io.Copy(hash, input); err != nil {
    log.Fatal(err)
}
sum := hash.Sum(nil)

fmt.Printf("%x\n", sum)
    

        1cbec737f863e4922cee63cc2ebbfaafcd1cff8b790d8cfd2e6a5d550b648afa
    

17. Запуск HTTP-сервера

Базовый веб-сервер

        package main

import (
    "fmt"
    "net/http"
)

func main() {
    http.HandleFunc("/", HelloServer)
    http.ListenAndServe(":8080", nil)
}

func HelloServer(w http.ResponseWriter, r *http.Request) {
    fmt.Fprintf(w, "Hello, %s!", r.URL.Path[1:])
}
    

• Вызов http.HandleFunc сообщает пакету net.http, что обработкой всех запросов к «корню» занимается HelloServer;
• http.ListenAndServe сообщает серверу, что он должен прослушивать адрес по порту 8080. Эта функция блокируется, пока программа не завершится;
  
• http.ResponseWriter отправляет данные HTTP-клиенту;
  
• http.Request – структура данных клиентского HTTP-запроса;
  
• r.URL.Path – компонент URL-адреса. В нашем случае "/world" является компонентом ссылки "http://localhost:8080/world".
  

При обращении к http://localhost:8080/world, где работает приведенный код, вы увидите такую страницу:

18. Реализация итератора

Go имеет встроенный цикл для итерации по слайсам, массивам, строкам, картам и каналам. Для перебора других типов данных у функции итератора есть обратные вызовы.

Базовый паттерн итератора

        // Iterate calls the f function with n = 1, 2, and 3.
func Iterate(f func(n int)) {
    for i := 1; i <= 3; i++ {
        f(i)
    }
}
    

В действии:

        Iterate(func(n int) { fmt.Println(n) })
    

        1
2
3
    

Итератор с break

        // Iterate вызывает функцию f с n = 1, 2 и 3.
// Если f возвращает true, Iterate возвращает немедленно
// пропуск всех оставшихся значений.
func Iterate(f func(n int) (skip bool)) {
    for i := 1; i <= 3; i++ {
        if f(i) {
            return
        }
    }
}
    

В действии:

        Iterate(func(n int) (skip bool) {
	fmt.Println(n)
	return n == 2
})
    

        1
2
    

19. Четыре примера йота-перечислений

Йота: базовый пример

Ключевое слово iotaпозволяет создавать последовательные целочисленные константы: 0, 1, 2 и т. д. Значение iota сбрасывается к нулю, когда в исходном коде появляется слово const.

        const (
    C0 = iota
    C1 = iota
    C2 = iota
)
fmt.Println(C0, C1, C2) // "0 1 2"
    

Можно уменьшить так:

        const (
	C0 = iota
	C1
	C2
)
    

Начало с единицы

Чтобы начать список констант с 1 вместо 0, можно использовать iota в арифметическом выражении:

        const (
    C1 = iota + 1
    C2
    C3
)
fmt.Println(C1, C2, C3) // "1 2 3"
    

Пропуск значения

Для пропуска значения в списке констант можно использовать пустой идентификатор:

        const (
    C1 = iota + 1
    _
    C3
    C4
)
fmt.Println(C1, C3, C4) // 1 3 4
    

20. Максимальное значение int

Go имеет два целочисленных типа с реализацией конкретных размеров:

• uint (беззнаковое целое), 32 или 64 бита;
• int (целое) имеет такой же размер, как uint.
  

Код ниже вычисляет предельные значения нетипизированных констант:

        const UintSize = 32 << (^uint(0) >> 32 & 1) // 32 or 64

const (
    MaxInt  = 1<<(UintSize-1) - 1 // 1<<31 - 1 or 1<<63 - 1
    MinInt  = -MaxInt - 1         // -1 << 31 or -1 << 63
    MaxUint = 1<<UintSize - 1     // 1<<32 - 1 or 1<<64 - 1
)
    

Константа UintSize также доступна в пакете math/bits.

21. Округление float до n знаков после запятой

Float в string

Чтобы отобразить значение в виде строки, используйте метод fmt.Sprintf.

        s := fmt.Sprintf("%.2f", 12.3456) // s == "12.35"
    

Float во Float

Чтобы округлить до значения с плавающей запятой, используйте один из этих методов:

        x := 12.3456
fmt.Println(math.Floor(x*100)/100) // 12.34
fmt.Println(math.Round(x*100)/100) // 12.35
fmt.Println(math.Ceil(x*100)/100)  // 12.35
    

22. Юнит-тесты в Go

Пусть у нас есть код, который мы хотим протестить:

        package search

// Find возвращает наименьший индекс i, при котором x <= a[i].
// Если такого индекса нет, то он возвращает len(a).
// Слайс должен быть отсортирован в порядке возрастания.
func Find(a []int, x int) int {
    switch len(a) {
    case 0:
        return 0
    case 1:
        if x <= a[0] {
            return 0
        }
        return 1
    }
    mid := len(a) / 2
    if x <= a[mid-1] {
        return Find(a[:mid], x)
    }
    return mid + Find(a[mid:], x)
}
    

• Поместим тестовый код в файл, имя которого заканчивается на _test.go;
• напишем функцию TestXXX с одним аргументом типа *testing.T;
  
• для указания на неудачный тест, вызовем функцию t.Errorf.
  

        package search

import "testing"

var tests = []struct {
    a   []int
    x   int
    exp int
}{
    {[]int{}, 1, 0},
    {[]int{1, 2, 3, 3}, 0, 0},
    {[]int{1, 2, 3, 3}, 1, 0},
    {[]int{1, 2, 3, 3}, 2, 1},
    {[]int{1, 2, 3, 3}, 3, 3}, // incorrect test case
    {[]int{1, 2, 3, 3}, 4, 4},
}

func TestFind(t *testing.T) {
    for _, e := range tests {
        res := Find(e.a, e.x)
        if res != e.exp {
            t.Errorf("Find(%v, %d) = %d, expected %d",
                e.a, e.x, res, e.exp)
        }
    }
}
    

Запустим тест с помощью go test:

        $ go test
--- FAIL: TestFind (0.00s)
    search_test.go:22: Find([1 2 3 3], 3) = 2, expected 3
FAIL
exit status 1
FAIL    .../search  0.001s
    

23. Три способа сортировки

Сортировка слайса int, float64 или строк

Используем одну из функций:

• sort.Ints
• sort.Float64s
  
• sort.Strings
  

        s := []int{4, 2, 3, 1}
sort.Ints(s)
fmt.Println(s) // [1 2 3 4]
    

Сортировка с помощью кастомного компаратора

Используйте функцию sort.Slice – она сортирует слайс с помощью функции less(i, j int). Чтобы отсортировать слайс, сохраняя исходный порядок элементов, используйте сортировку sort.SliceStable:

        family := []struct {
    Name string
    Age  int
}{
    {"Alice", 23},
    {"David", 2},
    {"Eve", 2},
    {"Bob", 25},
}

// Сортировка по возрасту, c сохранением первоначального порядка
sort.SliceStable(family, func(i, j int) bool {
    return family[i].Age < family[j].Age
})
fmt.Println(family) // [{David 2} {Eve 2} {Alice 23} {Bob 25}
    

Сортировка пользовательских структур

Используйте универсальные функции sort.Sort и sort.Stable.

        type Interface interface {
        Len() int
        Less(i, j int) bool
        Swap(i, j int)
}
    

Пример:

        type Person struct {
    Name string
    Age  int
}

// ByAge реализует sort.Interface, основанный на возрасте.
type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
    family := []Person{
        {"Alice", 23},
        {"Eve", 2},
        {"Bob", 25},
    }
    sort.Sort(ByAge(family))
    fmt.Println(family) // [{Eve 2} {Alice 23} {Bob 25}]
}
    

Сортировка map по ключу или значению

Как вы знаете, map – это неупорядоченная коллекция пар ключ-значение. Если же нужен стабильный порядок итераций, нужно использовать другую структуру данных. В этом примере кода для сортировки карты по ключам используется слайс ключей.

        m := map[string]int{"Alice": 2, "Cecil": 1, "Bob": 3}

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)

for _, k := range keys {
    fmt.Println(k, m[k])
}
// Output:
// Alice 2
// Bob 3
// Cecil 1
    

Если эти примеры были полезны, вы можете подписаться на наш телеграм-канал @goproglib – в нём мы публикуем последние статьи о языке Go и другие полезные материалы на русском и английском языках.