github.com/alivewel/sber-tasks @main

Подробный разбор задач

Задача №1 (concurrency)

Что выведет программа?

func main() {
    for _, val := range []int{1, 2, 3} {
        go println(val)
    }
}

Отсутствие вывода

Программа не выводит ничего на экран. Это происходит потому, что основная горутина main завершается раньше, чем горутины успевают выполнить println. В результате, программа завершает работу, не дождавшись завершения всех запущенных горутин.

Использование WaitGroup

Чтобы гарантировать, что все горутины завершат выполнение, прежде чем программа выйдет, необходимо использовать примитив синхронизации sync.WaitGroup. Этот механизм позволяет основной горутине main ожидать завершения всех запущенных горутин.

Захват переменной в замыкании

В зависимости от версии Go, необходимость добавления новой переменной для захвата значения в замыкании может изменяться. Начиная с версии 1.22, дополнительная переменная не обязательна, так как компилятор Go сам обрабатывает захват переменных в контексте горутин.

Решение

func main() {
    wg := sync.WaitGroup{}
    for _, val := range []int{1, 2, 3} {
        wg.Add(1)
        go func(num int) {
            defer wg.Done()
            println(num)
        }(val)
    }
    wg.Wait()
}

Задача №2 (concurrency)

Что выведет программа?

func main() {
    ch := make(chan string)
    close(ch)
    go func() {
        text := <-ch
        println("Hello, ", text)
    }()
    runtime.GC()
}

Вывод программы

Программа выведет: Hello,. Это происходит из-за того, что из закрытого канала читается zero value (пустая строка для типа string), которая и будет выведена.

Что происходит в программе?

1. Создание канала: Программа создает канал для строк: ch := make(chan string).

2. Закрытие канала: На следующей строке канал закрывается с помощью close(ch). Закрытие канала предотвращает запись в него, но чтение все еще возможно.

3. Горутина: Запускается горутина, которая читает из канала. Поскольку канал закрыт, операция чтения возвращает zero value для типа string — пустую строку. Это значение используется в println, формируя вывод Hello,.

4. Использование runtime.GC(): Вызывается сборщик мусора runtime.GC(), который служит для того, чтобы дать время горутине завершить выполнение.

Задача №3 (string)

Что выведет программа?

func main() {
    println(f())
}

func f() string {
    s := "Test"
    s[0] = 'R'
    return s
}

Вывод программы

Попытка изменить строку s с помощью s[0] = 'R' вызовет ошибку компиляции. Это связано с тем, что строки в Go являются неизменяемым (immutable) типом данных. Прямое изменение символов строки недопустимо.

Доработка программы

Чтобы программа корректно работала необходимо изменить подход к изменению строки. Поскольку строки в Go являются неизменяемыми (immutable), требуется преобразовать строку в массив байтов, внести необходимые изменения, а затем преобразовать массив обратно в строку.

Решение

func main() {
    println(f())
}

func f() string {
    s := "Test"
    b := []rune(s) // Преобразуем строку в срез рун
    b[0] = 'R'     // Изменяем первый элемент
    return string(b) // Преобразуем обратно в строку
}

Задача №4 (string)

Как посчитать количество символов в строке?

func main() {
    str := "Привет!"
    charCount := 0
    // посчитать кол-во символов в строке
    if charCount == 7 {
        println("Success!")
    }
}

Подсчет символов №1

Самый простой способ подсчитать количество символов в строке — это пройтись по ней в цикле и инкрементировать счетчик с каждой итерацией. Это позволяет корректно учитывать символы, которые занимают более одного байта.

Решение №1

func main() {
    str := "Привет!"
    charCount := 0

    // Посчитать количество символов в строке
    for range str {
        charCount++
    }

    if charCount == 7 {
        println("Success!")
    }
}

Подсчет символов №2

Преобразовав строку в срез рун с помощью []rune(str), мы можем работать с каждым символом как с отдельной Unicode-кодовой точкой, и функция len() затем возвращает количество рун, что соответствует количеству символов в строке.

Решение №2

func main() {
    str := "Привет!"
    charCount := 0

    // Посчитать количество символов в строке
    charCount = len([]rune(str)) // Преобразуем строку в срез рун и берем его длину

    if charCount == 7 {
        println("Success!")
    }
}

Почему нельзя использовать len(str)?

Если использовать len(str), то вы получите количество байт в строке, а не количество символов. В данном случае строка "Привет!" содержит русские символы, которые занимают 2 байта каждый. Поэтому len(str) вернет 13, а не 7.

Что такое руна? Какой размер она имеет?

• Руна (rune) — это тип данных в Go, представляющий собой Unicode-кодовую точку. По сути, руна — это просто int32, который используется для обозначения символов Unicode.
• Размер руны: Руна в Go имеет размер 4 байта (32 бита). Это позволяет ей хранить любую Unicode-кодовую точку, так как диапазон Unicode охватывает значения от 0 до 0x10FFFF, что помещается в 32-битное целое число.

Задача №5 (string)

Что выведет программа?

func main() {
    str := "Привет"
    for i := range str {
        println(i)
    }
}

Вывод программы

Программа выведет следующие индексы:

0
2
4
6
8
10

Эти индексы появляются потому, что русские буквы в кодировке UTF-8 кодируются двумя байтами. В цикле for i := range str, переменная i представляет собой байтовый индекс каждого символа в строке.

Задача №6 (slice)

Что такое слайс? Почему он так называется?

Слайс - динамически расширяемый массив, который может расширятся с помощью функции append.

Структура слайса

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

• Pointer: *array — базовый массив.
• Ссылка указывает на первый элемент массива.

• Последний используемый элемент определяется с помощью Length.

• Length: int

• Это количество элементов, которые мы "отщипываем" от базового массива.

• Capacity: int

• Это количество элементов, которые могут поместиться в базовый массив, учитывая, что первый элемент слайса не обязательно совпадает с первым элементом массива.
• Например, если размер массива 10, но мы начинаем использовать его с 5-го элемента, то capacity будет 5.

Как работает функция append?

1. Для слайсов до 256 элементов:

2. Емкость увеличивается в два раза. Это позволяет эффективно управлять памятью и минимизировать количество операций по перераспределению памяти.

3. Для слайсов более 256 элементов:

4. Емкость увеличивается по формуле:
5. Здесь константа равна 256. Этот подход позволяет более плавно увеличивать емкость, что особенно важно для больших слайсов, чтобы избежать резкого увеличения использования памяти.

Что выведет программа?

func main() {
    slice := make([]int, 0, 1000)
    slice = append(slice, 1, 2, 3)
    fmt.Println(slice)     // ???
    process(slice)
    fmt.Println(slice)     // ???
    fmt.Println(slice[:6]) // ???
}

func process(slice []int) {
    for index := range slice {
        slice[index] = 0
    }
}

Вывод программы

1. Первый вывод: fmt.Println(slice)
2. Вывод: [1 2 3]

3. Изначально в слайс добавляются элементы 1, 2 и 3.

4. Второй вывод: fmt.Println(slice) после process(slice)

5. Вывод: [0 0 0]

6. Функция process(slice) заменяет каждый элемент слайса на 0, изменяя его на месте.

7. Третий вывод: fmt.Println(slice[:6])

8. Вывод: [0 0 0 0 0 0]
9. Слайс изначально создан с длиной 0 и емкостью 1000, поэтому slice[:6] имеет доступ к первым шести элементам подлежащего массива. Так как process(slice) изменяет только первые три элемента, остальные элементы остаются нулевыми, и выводится [0 0 0 0 0 0].

Задача №7 (slice)

Что выведет программа?

func main() {
    slice := make([]int, 0, 1000)
    slice = append(slice, 1, 2, 3)
    fmt.Println(slice)     // ???
    process(slice)
    fmt.Println(slice)     // ???
    fmt.Println(slice[:6]) // ???
}

func process(slice []int) {
    slice = append(slice, 4, 5, 6)
}

Вывод программы

1. Первый вывод: fmt.Println(slice)
2. Вывод: [1 2 3]

3. Изначально в слайс добавляются элементы 1, 2 и 3.

4. Второй вывод: fmt.Println(slice) после process(slice)

5. Вывод: [1 2 3]

6. В функции process(slice) создается новый слайс с добавлением элементов 4, 5 и 6. Однако это изменение не влияет на оригинальный слайс в main, так как слайсы передаются по значению, где копируются длина и емкость, но базовый массив передается по указателю. Поэтому при выходе из функции process длина оригинального слайса остается прежней.

7. Третий вывод: fmt.Println(slice[:6])

8. Вывод: [1 2 3 4 5 6]
9. Функция process(slice) изменяет оригинальный слайс, добавленные элементы 4, 5 и 6 все же записываются в подлежащий массив, так как у слайса достаточно емкости (1000). Указав явно длину slice[:6] мы можем включить эти элементы в вывод.

Задача №8 (map)

Что такое мапа в го?

Мапа - это структура данных, которая содержит в себе пару ключ и значение. Под капотом в ней хеш-таблица, которая позволяет нам обращаться по ключу за константное время.

Изначально создается мапа с 8 бакетами. Бакет - структура данных, в которой хранится ключи и значения в мапе. Данные внутри бакета хранятся в виде массива, в одном бакете может быть до 8 элементов. Если все аллоцированые бакеты в среднем заполнены на 6,5, то начинается эвакуация данных. Важное свойство для ключа - он должен быть comparable (сравнимый). Нельзя взять указатель на элемент мапы как раз по причине эвакуации данных. Бакеты нужно для равномерного распределения данных.

Структура map

1) count - размер мапы 2) B - log_2 (логарифм) количества бакетов. Для 8 бакетов B=3, для 16 B=4 и так далее. 3) hash0 uint32 // seed для хэш-функции, генерируется при создании мапы. нужен для рандомизации хэш-функции 4) buckets unsafe.Pointer // ссылка на массив из 2^B бакетов; nil, если count==0 5) oldbuckets unsafe.Pointer // ссылка на массив предыдущих бакетов. в процессе роста мапы здесь будет массив старых бакетов, откуда потихоньку будут переноситься значения в новые бакеты.

Переполнение бакета.

При переполнении бакета создается новый бакет и ссылка не него сохраняется в старом бакете. Ситуация переполнения бакета очень нежелательна. Цифра 6.5 взято не случайно - это "идеальное" сочетание между переполнением и необходимым выделением памяти. Похоже при этом эвакуация данных не происходит, просто создается еще один новый бакет. Этот процесс не быстрый, память выделяется, но она не инициализируется сразу. Если бы мы переносили данные сразу, после того, как выделили память, то некоторые операции внезапно начали бы работать медленно. Поэтому операции переноса выполняются в те моменты, когда мы выполняем операции сохранения или удаления ключей из мапы, это выполняется инкрементально. В ходе этого процесса данные равномерно распределяются по новым бакетам. Мы избежали пауз в выполнении операций, но теперь эти операции будут работать медленнее, потому что в момент эвакуации нужно будет смотреть в старые и в новые бакеты. Единственный способ избежать этих проблем выделять память для мапы под нужный размер заранее.

Эвакуация

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

Эвакуация данных из бакета Создается новый список бакетов, который будет в 2 раза больше чем предыдущий. И данные из старых бакетов будут скопированы в новые.

Эвакуация - процесс реорганизации и перераспределения элементов из старых корзин в новые корзины при расширении хеш-таблицы. Она происходит, когда количество элементов в map превышает определенный порог, происходит увеличение числа корзин, чтобы уменьшить вероятность коллизий и сохранить эффективность операций вставки, удаления и поиска. При увеличении Эвакуация происходит не сразу, только при чтении или записи к ним. Эвакуация происходит через воркеры.

Записывать значения в неинициализированную мапу нельзя, будет паника. Читать значения из неинициализированную мапу можно, получим zero-value.

У нас есть хеш-функция, которая возвращает нам какой-то хеш. Хеш представляет из себя значение числа int64. Бакетов у нас меньше? Как вычислить в какой бакет положить пару ключ-значение?

Мы берем остаток от деления от количества бакетов.

Что выведет программа?

func main() {
    var m map[string]struct{}
    for k := range m {
        println(k)
    }
    println("end!")
}

Поскольку карта пуста и не содержит элементов для итерации, единственным выводом будет "end!".

Задача №9 (map)

У нас есть 2 функции для вычисления хеша. Нужно вставить в мапу всего лишь 10 элементов.

Какая функция для вычисления хеша больше подходит для этой цели? Какие плюсы и минусы каждой функции?

func hash1() int {
    return randomInt(100)
}

func hash2() int {
    return 1
}

Функция hash1 каждый раз возвращает случайный хеш. Это обеспечивает равномерное распредление по бакетам при вставке элементов в мапу. Только при чтении мы уже не сможем обратиться в тот бакет, в который положили наше значение, потому что хэш-функция вернет другое значение. Здесь происходит нарушение детерменированности и предскауемости хэш-функции.

Функция hash2 всегда возвращает единицу. Это значит, что в мапе у нас будет 10 элементов, которые будут иметь од