Quote
Программирование — творчество. Его можно сравнить с написанием произведения, где ручкой является язык программирования, а листом бумаги — компьютер. Что будет написано и как, каким образом будет воспринят результат — зависит только от вас.
— Евгений Никонов
Вступление
Здравствуй, читатель. Это первый материал в 2025 году, звучит воодушевляюще (а ведь я начал вести свой блог в 2024м). Основные праздники закончились, я ступил в новый год заряженный, полный энтузиазма двигаться к своим целям дальше.
Я решил продолжить тему развития в программировании с нуля, данный материал является вторым в серии. Всего будет три, слудующий — заключительный (по крайней мере, такие планы). Также повторюсь, что это не прогрев на какой-то курс, не продажа каких-то материалов.
Надеюсь, дорогой читатель, ты потратил достаточно времени на изучение прошлого материала в серии, набил руку и настроен продолжить обучение. Данный метериал посвящён алгоритмам и структурам данных, сложность повышается.
Алгоритмы
С алгоритмами, я думаю, ты уже знаком что в теории, что на практике.
При решении задачи мы стараемся создать оптимальный алгоритм, который приведёт нас к заветному результату. Но что означает “создать оптимальный алгоритм”?
Для ответа на этот вопрос рассмотрим термин — сложность алгоритма (algorythm complexity). Важно понимать, что речь не о сложности решения или его запустанности. Сложность алгоритма обычно включает в себя временную и пространственную сложность и выражается нотацией О-большое.
Т.е. при решении задачи необходимо стремиться к лучшей временной и пространственной сложности алгоритма. Это и означает создание оптимального алгоритма для решения задачи. Я использую словосочетание “оптимальный алгоритм”, а не “лучший алгоритм”, чтобы не возводить в абсолют и быть реалистом.
Временная сложность определяет, сколько времени необходимо для выполнения алгоритма -> O time.
Пространственная сложность определяет, какое количество памяти использует алгоритм -> O space.
Существуют определенные разновидности сложностей. Ниже представляю некоторые из них в порядке убывания:
- Constant: O(1)
- Logarithmic: O(log(n))
- Linear: O(n)
- Log-linear: O(n * log(n))
- Quadratic: O(n^2)
- Cubic: O(n^3)
- Exponential: O(2^n)
- Factorial: O(n!)
Также представляю эти сложности на графике:
Сразу же на практике показываю задачу, которую можно решить, например, двумя способами. Первый способ описывает сложность алгоритма O(m * n) по времени и O(1) по памяти. Второй способ описывает сложность алгоритма O(n) по времени и O(1) по памяти.
Задача:
Даны два непустых целочисленных массива. Необходимо написать функцию, которая будет определять, является ли второй массив подмассивом первого.
Например, массив [11, 3, 7, 1] будет являться подмассивом [11, 1, 13, 21, 3, 7], а массив [11, 5, 2, 1] уже нет.
Решения:
package golang
// O(m*n) time, O(1) space
// m - длина первого среза, n - длина второго среза -> о срезах чуть позже
func isValidSubsequence1(arr, sequence []int) bool {
m := len(arr)
n := len(sequence)
for i := 0; i < n; i++ {
found := false
for j := 0; j < m; j++ {
if sequence[i] == arr[j] {
found = true
break
}
}
if !found {
return false
}
}
return true
}
// O(n) time, O(1) space
func isValidSubsequence2(arr, sequence []int) bool {
arrIdx := 0
seqIdx := 0
for arrIdx < len(arr) && seqIdx < len(sequence) {
if arr[arrIdx] == sequence[seqIdx] {
seqIdx += 1
}
arrIdx += 1
}
return seqIdx == len(sequence)
}
Структуры данных
Структура данных является неким контейнером, хранящим данные определенным образом, в определенном представлении. Структуры данных напрямую связаны с алгоритмами, многие из них появились вследствие развития эффективности тех или иных алгоритмов.
Некоторые структуры данных:
- Массивы и срезы.
- Списки.
- Стеки.
- Очереди.
- Деревья.
- Хеш-таблицы.
- Графы.
Ты мог слышать, например, о массивах — упорядоченная коллекция элементов фиксированного размера. Из массивов появились срезы (или динамические массивы), которые позволяют не зависеть от фиксации размера коллекции элементов.
Arrays -> work instantly to get a known item and set or rewrite item. Instantly means it runs in constant time O(1), side by side in memory.
Хоть срезами зачастую пользоваться удобней (по крайней мере, в Golang), они имеют некоторые особенности. Срез является структурой, которая содержит указатель на начало области памяти (массива), длины среза и объём области памяти.
Сложно? Если проще, то у среза под капотом массив. Как только этот массив переполняется, создается новый, больше другого в определенной мере. Вот так и обеспечивается независимость от фиксации размера коллекции элементов.
Однако всегда ли нам это подходит? — срезы иногда могут приводить к черезмерному выделению памяти, как бы мы ни старались оптимизировать алгоритм. Чтобы решить эту проблему, нам может помочь другая структура данных, например, список.
Список представляет из себя группу узлов, каждый из которых указывает на следующий. С данной структурой данных черезмерного выделения памяти, например, может не происходить.
Linked lists 1->2->3. Like arrays, but not side by side -> every value points to the next value in memory.
Какая бы ни была ситуация, важно знать, какие бывают структуры данных, понимать, как они работают, их преимущества и недостатки. Так ты расширяешь свой гругозор, открываешь больше возможностей для решения тех или иных задач.
Алгоритм нахождения пути
Эпик данного материала — написать алгоритм, который находит выход из лабиринта.
Имеется некоторый массив строк, описывающий лабиринт, где # — стена:
[
"##### #"
"# #"
"# #"
"# #"
"# #####"
]
Необходимо найти выход из лабиринта. Начало и конец пути мы задаём сами, например, прийти сверху справа вниз слева. Ответ можно представить разными способами, в нашем случае — получившийся путь из X и Y координат.
Пример возможного ответа с заполненным в лабиринте путем с использованием * (рекомендую попробовать реализовать самостоятельно):
[
"#####*#"
"# *#"
"# *#"
"#*****#"
"#*#####"
]
Каким образом мы подойдём к решению данной задачи? Подсказываю — мы будем использовать рекурсию. Подробное изучение рекурсии я опущу на твою совесть, читатель, и отправлюсь в бой.
Начнем с простого. Что мы можем делать в каждой точке? — мы можем пойти влево, вправо, вниз и вверх. Это верно не всегда. Например, мы не можем пойти в точку, в которой стена, или выйти за пределы карты, также нам не хочется возвращаться в уже посещенные точки, чтобы не ходить кругами.
Что же, это будут наши базовые сценарии:
- Следующая точка является стеной -> мы не можем туда пойти.
- Следующая точка ведет за пределы карты -> мы не можем туда пойти.
- Следующая точка — точка, в которой мы уже были -> мы не можем туда пойти.
- Следующая точка — конец пути -> идём туда, мы пришли.
Что же, каждый наш шаг в рекурсии становится достаточно простым — проверка каждого базового сценария.
Представляю алгоритм с разрешением базовых сценариев:
package main
// Структура, описывающая точку
type Point struct {
X int
Y int
}
// Функция walk описывает наш шаг в лабиринте
func walk(
maze []string, // Лабиринт
wall string, // Стена
curr Point, // Наша текущая позиция
end Point, // Позиция, в которую мы хотим прийти
seen [][]bool, // Двумерный срез, хранящий точки, которые мы уже видели
) bool {
// 1. Если следующая точка ведет за пределы карты
if curr.X < 0 || curr.X >= len(maze[0]) ||
curr.Y < 0 || curr.Y >= len(maze) {
return false
}
// 2. Если следующая точка - стена
if string(maze[curr.Y][curr.X]) == wall {
return false
}
// 3. Если следующая точка - точка, в которой мы уже были
if seen[curr.Y][curr.X] {
return false
}
// 4. Если следующая точка - конец
if curr.X == end.X && curr.Y == end.Y {
return true
}
return false
}
Ещё нам нужно где-то отмечать наш путь, для этого добавим срез path:
package main
func walk(
// ...
path *[]Point, // Наш путь
) bool {
// ...
}
Не забываем, что хоть срез в Golang и передается по ссылке, для добавления в него элементов нам всё равно придётся указать ему ссылку — задача учитывает и работу с памятью, да. Т.е. срез path передается по ссылке.
You can modify the slice elements within the function, and these changes will be reflected outside the function. You can also pass a slice pointer if you need to modify the slice’s structure, such as appending to it or changing its capacity.
Последним шагом будет добавление рекурсии:
package main
func walk(
maze *[]string, // Лабиринт
wall string, // Стена
curr Point, // Наша текущая позиция
end Point, // Позиция, в которую мы хотим прийти
seen [][]bool, // Двумерный слайс, хранящий точки, которые мы уже видели
path *[]Point, // Наш путь
) bool {
// ...
// Запоминаем точку
seen[curr.Y][curr.X] = true
// Добавляем точку в наш путь -> предполагаем, что туда можно пойти
*path = append(*path, curr)
// Смотрим все направления
for i := range directions {
// Узнаем направление -> либо лево, либо право, либо низ, либо верх
x := directions[i][0]
y := directions[i][1]
next := Point{ // Следующая точка
X: curr.X + x, // Сдвигаем X в выбранном направлении
Y: curr.Y + y, // Сдвигаем Y в выбранном направлении
}
// Шагаем дальше
if walk(
maze,
wall,
next,
end,
seen,
path,
) {
return true // Шаг оказался завершающим -> нашли выход
}
}
// Удаляем точку с нашего пути -> туда мы не идем
*path = (*path)[:len((*path))-1]
return false
}
Что поменялось? Теперь мы запоминаем те места, в которых уже были; добавляем предполагаемую точку в путь, делаем шаг и удаляем эту же точку, если она не подошла. Каждый шаг будто вызывает сам себя, в том и смысл рекурсии, опускаться всё ниже по “стеку” и проверять сценарии по умолчанию.
Откуда мы смотрим направления? Для направлений я завел заранее определенный массив directions — мы проходимся по всем направлениям в цикле, пробуем сделать шаг:
var directions = [4][]int{
{-1, 0}, // Лево
{1, 0}, // Право
{0, -1}, // Низ
{0, 1}, // Верх
}
// ...
// Смотрим все направления
for i := range directions {
// Узнаем направление -> либо лево, либо право, либо низ, либо верх
x := directions[i][0]
y := directions[i][1]
next := Point{ // Следующая точка
X: curr.X + x, // Сдвигаем X в выбранном направлении
Y: curr.Y + y, // Сдвигаем Y в выбранном направлении
}
// Шагаем дальше
if walk(
// ...
next,
// ...
) {
return true // Шаг оказался завершающим -> нашли выход
}
}
Ну и, конечно, полный код с запуском и тестом:
package main
import "fmt"
type Point struct {
X int
Y int
}
var directions = [4][]int{
{-1, 0}, // Лево
{1, 0}, // Право
{0, -1}, // Низ
{0, 1}, // Верх
}
func walk(
maze []string, // Лабиринт
wall string, // Стена
curr Point, // Наша текущая позиция
end Point, // Позиция, в которую мы хотим прийти
seen [][]bool, // Двумерный слайс, хранящий точки, которые мы уже видели
path *[]Point, // Наш путь
) bool {
// 1. Следующая точка ведет за пределы карты
if curr.X < 0 || curr.X >= len(maze[0]) ||
curr.Y < 0 || curr.Y >= len(maze) {
return false
}
// 2. Если следующая точка - стена
if string(maze[curr.Y][curr.X]) == wall {
return false
}
// 3. Если следующая точка - конец
if curr.X == end.X && curr.Y == end.Y {
// Добавить точку в наш путь в самом конце
*path = append(*path, curr)
return true
}
// 4. Если следующая точка - точка, в которой мы уже были
if seen[curr.Y][curr.X] {
return false
}
// Запоминаем точку
seen[curr.Y][curr.X] = true
// Добавляем точку в наш путь -> предполагаем, что туда можно пойти
*path = append(*path, curr) // *path -> смотрим, на что указывает ссылка, в нашем случае - на срез
// Смотрим все направления
for i := range directions {
// Узнаем направление -> либо лево, либо право, либо низ, либо верх
x := directions[i][0]
y := directions[i][1]
next := Point{ // Следующая точка
X: curr.X + x, // Сдвигаем X в выбранном направлении
Y: curr.Y + y, // Сдвигаем Y в выбранном направлении
}
// Шагаем дальше
if walk(
maze,
wall,
next,
end,
seen,
path,
) {
return true
}
}
// Удаляем точку с нашего пути -> туда мы не идем
*path = (*path)[:len((*path))-1]
return false
}
func solveMaze(
maze []string,
wall string,
start Point,
end Point,
) []Point {
// Заполняем все возможные увиденные места false -> мы их ещё не видели
seen := make([][]bool, len(maze))
for i := range maze {
seen[i] = make([]bool, len((maze)[i]))
}
path := make([]Point, 0)
walk(maze, wall, start, end, seen, &path)
return path
}
func main() {
// Наш лабиринт -> чуть посложнее, чем в условии задачи
maze := []string{
"xxxxxxxxxx x",
"x x x",
"x x x",
"x xxxxxxxx x",
"x x",
"x xxxxxxxxxx",
}
// Наше решение
path := solveMaze(maze, "x", Point{X: 10, Y: 0}, Point{X: 1, Y: 5})
// Проверка -> именно такие координаты должны получиться
mazeResult := []Point{
{X: 10, Y: 0},
{X: 10, Y: 1},
{X: 10, Y: 2},
{X: 10, Y: 3},
{X: 10, Y: 4},
{X: 9, Y: 4},
{X: 8, Y: 4},
{X: 7, Y: 4},
{X: 6, Y: 4},
{X: 5, Y: 4},
{X: 4, Y: 4},
{X: 3, Y: 4},
{X: 2, Y: 4},
{X: 1, Y: 4},
{X: 1, Y: 5},
}
// Проверяем, всё ли корректно
solutionCorrect := true
if len(path) != len(mazeResult) {
solutionCorrect = false
} else {
for i := range mazeResult {
if mazeResult[i].X != path[i].X || mazeResult[i].Y != path[i].Y {
solutionCorrect = false
break
}
}
}
// Вывод
if solutionCorrect {
fmt.Println("Solution is correct")
fmt.Println("Path: ", path)
} else {
fmt.Println("Solution is incorrect")
}
}
Запуск:
> go run ./maze_solver.go
Solution is correct
Path: [{10 0} {10 1} {10 2} {10 3} {10 4} {9 4} {8 4} {7 4} {6 4} {5 4} {4 4} {3 4} {2 4} {1 4} {1 5}]
Полезные материалы
Отдельно хочу уделить внимание полезным материалам, от которых ты можешь оттолкнуться при изучении (не реклама):
- Книга “Грокаем алгоритмы”, Адитья Бхаргава.
- Бесплатный курс по алгоритмам от популярного видеоблогера ThePrimeagen. Именно с этого курса была взята задача про нахождение выхода из лабиринта и переписана на Golang.
- Социальная сеть, посвященной программированию и соревнованиям по программированию — Codeforces.
- LeetCode -— платформа с алгоритмическими задачами по программированию.
Заключение
Практика, практика и ещё раз — практика. В программировании никак иначе, тебе должно это, действительно, нравиться, чтобы преуспеть.
Читатель, если я заинтересовал тебя, если публикация принесла тебе пользу, буду рад твоей компании в своих дальнейших материалах. Я считаю, что мне точно есть, чем с тобой поделиться.
У меня нет системы оповещения, есть простой канал в Telegram, в котором ты можешь отслеживать мою активность по данному проекту и помимо.
Если ты заметил какую-либо ошибку или неточность, можешь оставить об этом комментарий в канале, который я описал выше.
Также немного информации вот тут.
J4stEu — Just Eugene — Просто Евгений
Stay tuned
Связанные публикации:
Программирование для начинающих
25.11.2024