Программирование на языке Go

Go – компилируемый, строго типизированный язык общего назначения с минималистичным синтаксисом, встроенной поддержкой конкурентности и чёткой моделью модульности. Для задач уровня ЕГЭ по информатике Go удобен тем, что дисциплинирует алгоритмическое мышление: явные типы, предсказуемые циклы, строгая работа с массивами/срезами и лаконичные средства параллелизма. Ниже представлен академический разбор, объединяющий теорию (формальные определения, модели памяти, инварианты) и практику (шаблоны, анти-ошибки, упражнения).

Формальная модель и базовые конструкции

1. Единица компиляции и область видимости
   

   Пакет (package) – минимальная единица компиляции и связывания.

   Модуль (go.mod) – набор пакетов с управлением зависимостями.

   Идентификаторы с заглавной буквы – экспортируемые из пакета; с строчной – локальные.

   Области видимости: файл → блок ({}), for/if/switch → краткая область объявления.

2. Типы и значения (нулевые значения)
   

   Булевы:        bool               (нулевое: false)

   Целые:         int, int8 … uint64 (нулевое: 0)

   Вещественные:  float32, float64   (нулевое: 0.0)

   Комплексные:   complex64, complex128

   Строка:        string             (нулевое: "")

   Указатель:     *T                 (нулевое: nil)

   Массив:        [N]T               (фикс. длина, значение – все элементы)

   Срез:          []T                (дескриптор, нулевое: nil)

   Отображение:   map[K]V            (ссылка на хеш-таблицу, нулевое: nil)

   Структура:     struct{…}

   Интерфейс:     interface{…}       (нулевое: nil)

   Канал:         chan T             (нулевое: nil)

Ключевые инварианты:

• В Go всё передаётся по значению. Для ссылочных типов (slices, maps, channels, функции, интерфейсы) «значение» – это дескриптор/указатель на общие данные.
• «Нулевые» значения корректны для чтения (кроме операций записи в nil-map/канал).

Память, создание объектов и время жизни

1. Создание
   

   new(T)         → *T        // выделение нулевого T, возвращает указатель

   make(T, args)  → T         // только для slice/map/chan; создаёт внутренние структуры

   • new не инициализирует сложные внутренние структуры коллекций; make – инициализирует.

   • Время жизни определяется анализом ускользания (escape analysis) и сборщиком мусора.

2. Модель среза (slice)
   

   slice = (ptr, len, cap)

   append может перераспределить буфер: старые ссылки на элементы остаются валидными до GC.

Правило: после append нельзя полагаться на адреса элементов прежнего массива.

Управляющие конструкции и выражения

1. Циклы и ветвления
   

   for init; cond; post { … }     // классический

   for cond { … }                 // while

   for { … }                      // бесконечный; break/return – выход

   if init; cond { … } else …

   switch x { case …: … default: … }   // есть type switch

   • range по slice/array возвращает (index, valueCopy), по map – (key, valueCopy) (порядок перебора map не определён).

   • defer откладывает вызов до выхода из функции по LIFO-правилу.

2. Ошибки, паники и восстановление
   

   func f() (T, error)           // идиома «результат + ошибка»

   if err != nil { return …, err }

   panic(x)                      // для неисправимых ситуаций

   recover()                     // перехват паники внутри defer

Правило корректности: использовать panic только для инвариантов, нарушающих контракт функции; прикладные ошибки – через error.

Функции, параметры и контракты

1. Сигнатуры и множественный возврат
   

   func name(a A, b B) (R1, R2) { … }

   func variadic(xs ...T)       // «раскрывается» в []T внутри

2. Передача параметров
   

   • Всегда по значению. Чтобы модифицировать внешний объект – передавайте указатель (*T) либо ссылочный тип ([]T, map[K]V, chan T), осознавая, что вы копируете дескриптор.

   • Для больших структур – предпочтительнее *T или []byte и т.п.

3. Контракт функции (Хоаровская форма)
   

   {P}  f(x)  {Q}

   P – предусловие (валидность аргументов, не nil и т.д.)

   Q – постусловие (неизменность инвариантов, диапазоны результатов)

Структуры, методы, интерфейсы

1. Структуры и методы
   

   type Vec struct{ X, Y float64 }

   func (v *Vec) Add(u Vec) { v.X += u.X; v.Y += u.Y }

   Метод с приемником *T может изменять объект; с T – работает с копией.

2. Интерфейсы (структурная типизация)
   

   type Writer interface{ Write(p []byte) (int, error) }

   Тип реализует интерфейс неявно, если имеет нужные методы.

Анти-ошибка: «typed nil vs. nil interface».

var w *bytes.Buffer = nil

var i io.Writer = w      // i != nil: интерфейс несёт тип+nil-значение

Проверяйте оба поля или используйте явные контракты.

Коллекции и строки: практические правила

1. Массивы и срезы
   

   a := [5]int{1,2,3}      // массив (значимый тип)

   s := a[1:3]             // срез (разделяет буфер с a)

   s = append(s, 10)       // возможно перераспределение

   Правило: не храните «утечки» буфера через «тонкие» срезы больших массивов (удержите GC). Применяйте copy в новый буфер, если храните малую часть.

2. Отображения (map)
   

   m := make(map[string]int)

   m["x"]++                 // запись; чтение несуществующего даёт ноль

   v, ok := m["k"]          // ok == false, если ключа нет

   delete(m, "k")

   Анти-ошибка: запись в var m map[K]V (nil-map) вызывает панику – всегда make.

3. Строки и руны
   

   string – неизменяемая UTF-8 последовательность байт

   for _, r := range s { … }   // итерируем по рунам (Unicode code points)

   len(s) – байты, не руны

   Правило: при индексировании s[i] получаете байт; для «символов» работайте с рунами.

Конкурентность: goroutine, channel, select, context

1. Goroutine
   

   go f(x)     // лёгкий конкурентный поток

2. Каналы
   

   ch := make(chan T)          // небуферизованный (синхронный)

   ch := make(chan T, N)       // буферизованный

   ch <- v; v := <-ch; close(ch)

   Правило связи: отправка в небуферизованный канал синхронизирует отправителя и получателя (happens-before). Для буферизированных – синхронизация на границе буфера.

3. Select и отмена
   

   select {

   case x := <-in:

       …

   case out <- y:

       …

   case <-ctx.Done():

       return

   }

   Шаблон отмены: прокидывайте context.Context по стеку вызовов; реагируйте на Done().

4. Синхронизация
   

   sync.WaitGroup   // ожидание группы горутин

   sync.Mutex       // критические секции

   sync/atomic      // атомарные счётчики/флаги

   Инвариант: защищаем все связанные данные одним и тем же примитивом.

Модули, сборка, тестирование

1. Модульность
   

   go mod init example.com/app

   go get …         // зависимости

   Имя пакета = имя каталога; точка входа – package main и func main().

2. Тестирование
   

   func TestXxx(t *testing.T) { … }

   func BenchmarkXxx(b *testing.B) { for i:=0; i<b.N; i++ { … } }

   Правило: тест – часть контракта; проверяйте пограничные случаи, ошибки, отмену контекстов.

Алгоритмические шаблоны, полезные для ЕГЭ

1. Чтение/обработка массивов
   

   func SumPos(a []int) int {

       s := 0

       for _, x := range a {

           if x > 0 { s += x }

       }

       return s

   }

   Сложность: O(n) по времени, O(1) по памяти.

2. Частоты и сортировка пар
   

   func TopFrequent(a []int) (val, freq int) {

       cnt := make(map[int]int)

       for _, x := range a { cnt[x]++ }

       bestV, bestC := 0, -1

       for v, c := range cnt {

           if c > bestC || (c==bestC && v<bestV) { bestV, bestC = v, c }

       }

       return bestV, bestC

   }

3. BFS по неориентированному графу (списки смежности)
   

   func BFS(adj [][]int, s int) []int {

       n := len(adj)

       dist := make([]int, n)

       for i := range dist { dist[i] = -1 }

       q := make([]int, 0, n)

       dist[s] = 0

       q = append(q, s)

       for h := 0; h < len(q); h++ {

           v := q[h]

           for _, u := range adj[v] {

               if dist[u] == -1 {

                   dist[u] = dist[v] + 1

                   q = append(q, u)

               }

           }

       }

       return dist

   }

4. Конвейер (pipeline) с отменой
   

   func Gen(ctx context.Context, in []int) <-chan int {

       out := make(chan int)

       go func() {

           defer close(out)

           for _, x := range in {

               select {

               case out <- x:

               case <-ctx.Done(): return

               }

           }

       }()

       return out

   }

   func Square(ctx context.Context, in <-chan int) <-chan int {

       out := make(chan int)

       go func() {

           defer close(out)

           for x := range in {

               y := x * x

               select {

               case out <- y:

               case <-ctx.Done(): return

               }

           }

       }()

       return out

   }

Правила корректности и анти-ошибки

1. Передача параметров: всегда по значению. Изменяем – либо указатель *T, либо ссылочный тип осознанно.

2. Slice after append: не держите «сырые» адреса элементов – append может переместить буфер.

3. Map запись: make(map[K]V) перед записью; чтение отсутствующего ключа даёт ноль и ok=false.

4. Строки/UTF-8: len(s) – байты, не руны; range по строке идёт по рунам.

5. Горутины и отмена: каждая долгоживущая горутина принимает context.Context и обрабатывает Done().

6. Интерфейсы: различайте nil-interface и «typed-nil» в интерфейсе.

7. Детерминизм: порядок обхода map не определён – не опирайтесь на него в логике и тестах.

8. Сложность: явно комментируйте O(·) для циклов/проходов; это повышает оценку на ЕГЭ-разборах.

Мини-шпаргалка 

Создание:

p := new(T)          // *T c нулевым T

s := make([]T, n, c) // slice len=n, cap=c

m := make(map[K]V)   // map

ch := make(chan T, N)

Инварианты:

- Передача параметров по значению.

- range по slice: (i, copyOfValue)

- map[missing] → zero, ok=false

Обработка ошибок:

v, err := f()

if err != nil { return …, err } 

Конкурентность:

go f()

x := <-ch

select { case … ; case <-ctx.Done(): return }

Сложности:

Однопроходный подсчёт → O(n)

BFS/DFS → O(V+E)

Пять упражнений (академический формат)

Упражнение 1. Контракты и передача параметров
Реализуйте функцию: func ClampSlice(a []int, lo, hi int) которая модифицирует элементы a на месте, ограничивая их в диапазоне [lo, hi].

a) Запишите контракт {P} ClampSlice {Q}, где P задаёт валидность a (не nil), границы lo≤hi.
b) Обоснуйте выбор сигнатуры (почему []int, а не *[]int).
c) Оцените сложность и докажите отсутствие перераспределений памяти.

Упражнение 2. Частоты, сортировка и стабильность
Напишите функцию, возвращающую топ-k самых частых слов в тексте: func TopK(text []string, k int) []string

a) Используйте map[string]int для подсчёта и сортируйте промежуточный срез пар.
b) Обеспечьте стабильный отбор при равных частотах (лексикографический порядок).
c) Обоснуйте сложность по времени и памяти.

Упражнение 3. Конвейер с отменой по контексту
Соберите конвейер Gen → Filter(нечётные) → Square → Sum с отменой:

func FilterOdd(ctx context.Context, in <-chan int) <-chan int

func Sum(ctx context.Context, in <-chan int) (int, error)

a) Покажите, как корректно закрывать каналы и завершая горутины при ctx.Done().
b) Объясните гарантию happens-before между отправкой в канал и чтением результата.
c) Напишите тест, искусственно отменяющий контекст на середине потока.

Упражнение 4. BFS на Go для задач ЕГЭ
Дан неориентированный граф n вершин в виде списков смежности.
a) Реализуйте BFS(adj [][]int, s int) []int (см. §9.3).
b) Выведите длину кратчайшего пути s→t и восстановите путь по parent.
c) Докажите корректность и оцените O(V+E).

Упражнение 5. Обработка строк и Юникод
Реализуйте функцию: func ReverseRunes(s string) string

a) Объясните, почему простая индексация байтов портит Юникод.
b) Используйте []rune и оцените сложность по времени/памяти.
c) Дополнительно: реализуйте без выделения промежуточного []rune для коротких ASCII-строк (ветвление по utf8.ValidString).

Заключение

Go задаёт ясную вычислительную модель: передача по значению, чёткие ссылочные дескрипторы, простые и мощные примитивы конкурентности. Эти свойства, вместе с дисциплиной типов и лаконичным синтаксисом, делают его удобным инструментом для алгоритмической подготовки: от массивов, строк, графов до конвейеров и параллельных шаблонов. Следование изложенным правилам корректности и отработка пяти упражнений обеспечат уверенное владение инструментарием, необходимым для решения задач ЕГЭ на высоком уровне.