Метод цепочек предполагает, что каждая ячейка массива содержит не одно значение, а связный список (или динамический массив) пар «ключ–значение». При возникновении коллизии новая пара просто добавляется в список соответствующей ячейки. Таким образом, ячейка с индексом 3 будет содержать список вида
Пример 3
Метод открытой адресации решает проблему иначе: если вычисленная ячейка занята, алгоритм ищет следующую свободную ячейку по определённому правилу, например, проверяя последовательно следующие индексы. Этот метод требует более тщательного управления размером таблицы, но может быть более эффективным с точки зрения использования памяти.
Временная сложность операций в хеш-таблице в среднем случае составляет O(1) для поиска, вставки и удаления, что делает её исключительно быстрой структурой данных. Однако в худшем случае, например, при очень неудачной хеш-функции, приводящей все ключи к одному индексу, сложность деградирует до O(n), так как поиск превращается в линейный обход длинной цепочки.
Хеш-таблицы находят применение в решении множества алгоритмических задач. Например, они позволяют эффективно найти первый неповторяющийся символ в строке, сгруппировать слова-анаграммы или проверить, является ли одна строка перестановкой другой.
Пример 4
В языке Python хеш-таблицы реализованы в виде встроенного типа данных
Эффективность хеш-таблицы напрямую зависит от качества хеш-функции. Хорошая хеш-функция должна быть детерминированной, обеспечивать равномерное распределение ключей по ячейкам, вычисляться быстро и минимизировать количество коллизий. Детерминированность означает, что один и тот же ключ всегда даёт одинаковый хеш-код. Равномерное распределение помогает избежать ситуации, когда большинство данных скапливается в нескольких ячейках, что приводит к увеличению длины цепочек и снижению производительности. Быстрота вычисления необходима, чтобы не сводить на нет преимущества быстрого доступа. Наконец, минимизация коллизий — это основная цель, так как коллизии являются главным фактором, ухудшающим производительность.
[("apple", 50), ("grape", 60)]. Поиск значения по ключу в таком случае требует вычисления индекса и последующего линейного поиска по цепочке, чтобы найти нужную пару.Пример 3
Метод открытой адресации решает проблему иначе: если вычисленная ячейка занята, алгоритм ищет следующую свободную ячейку по определённому правилу, например, проверяя последовательно следующие индексы. Этот метод требует более тщательного управления размером таблицы, но может быть более эффективным с точки зрения использования памяти.
Временная сложность операций в хеш-таблице в среднем случае составляет O(1) для поиска, вставки и удаления, что делает её исключительно быстрой структурой данных. Однако в худшем случае, например, при очень неудачной хеш-функции, приводящей все ключи к одному индексу, сложность деградирует до O(n), так как поиск превращается в линейный обход длинной цепочки.
Хеш-таблицы находят применение в решении множества алгоритмических задач. Например, они позволяют эффективно найти первый неповторяющийся символ в строке, сгруппировать слова-анаграммы или проверить, является ли одна строка перестановкой другой.
Пример 4
В языке Python хеш-таблицы реализованы в виде встроенного типа данных
dict, который предоставляет богатый интерфейс для работы.student_scores = {
"Анна": 95,
"Борис": 87,
"Вера": 92
}
# Получение значения с указанием значения по умолчанию
print(student_scores.get("Анна", 0)) # 95
print(student_scores.get("Георгий", 0)) # 0 (ключа нет)
# Получение всех ключей и значений
print(student_scores.keys()) # dict_keys(['Анна', 'Борис', 'Вера'])
print(student_scores.values()) # dict_values([95, 87, 92])
# Перебор пар ключ-значение
for name, score in student_scores.items():
print(f"{name}: {score} баллов")
# Обновление словаря
new_scores = {"Георгий": 88, "Анна": 98}
student_scores.update(new_scores)
print(student_scores)
# Вывод: {'Анна': 98, 'Борис': 87, 'Вера': 92, 'Георгий': 88}Эффективность хеш-таблицы напрямую зависит от качества хеш-функции. Хорошая хеш-функция должна быть детерминированной, обеспечивать равномерное распределение ключей по ячейкам, вычисляться быстро и минимизировать количество коллизий. Детерминированность означает, что один и тот же ключ всегда даёт одинаковый хеш-код. Равномерное распределение помогает избежать ситуации, когда большинство данных скапливается в нескольких ячейках, что приводит к увеличению длины цепочек и снижению производительности. Быстрота вычисления необходима, чтобы не сводить на нет преимущества быстрого доступа. Наконец, минимизация коллизий — это основная цель, так как коллизии являются главным фактором, ухудшающим производительность.
# Пример плохой хеш-функции, зависящей только от длины строки
def bad_hash(key, size):
return len(str(key)) % size
bad_hash("cat", 10) # → 3
bad_hash("dog", 10) # → 3 (коллизия!)
bad_hash("rat", 10) # → 3 (коллизия!)
# Пример более качественной хеш-функции
def good_hash(key, size):
return sum(ord(c) for c in str(key)) % size
good_hash("cat", 10) # → 4
good_hash("dog", 10) # → 4 (возможна коллизия, но реже)
good_hash("rat", 10) # → 7 (разные индексы!)
Метод цепочек для разрешения коллизий, как уже упоминалось, заключается в хранении в каждой ячейке массива связного списка всех пар «ключ-значение», которым соответствует данный индекс. При вставке нового элемента с ключом, чей хеш совпал с хешом уже существующего, новая пара добавляется в конец списка этой ячейки. Поиск требует вычисления хеша и последующего последовательного просмотра списка для нахождения нужного ключа. Основное преимущество метода цепочек — его простота и то, что таблица никогда не переполняется, так как список может расти динамически. Недостатком является необходимость в дополнительной памяти для хранения ссылок и потенциальное снижение производительности при длинных цепочках.
Пример 5
Использование хеш-таблиц наиболее оправдано в задачах, требующих частых операций поиска, проверки наличия элемента или подсчёта уникальных значений. Это включает подсчёт частоты элементов в коллекции, поиск дубликатов, реализацию кэшей, решение задачи о двух суммах, группировку данных по определённому признаку, представление графов в виде списков смежности, поиск анаграмм и реализацию множеств. Например, задача поиска двух чисел в массиве, дающих в сумме заданное значение, эффективно решается за один проход с использованием хеш-таблицы для хранения просмотренных элементов.
Однако существуют сценарии, где хеш-таблицы могут быть не самым лучшим выбором. Если требуется упорядоченный обход элементов по ключу, данные необходимо часто сортировать или выполнять поиск по диапазону ключей, более подходящими структурами могут оказаться сбалансированные деревья поиска. Также хеш-таблицы требуют дополнительной памяти и могут иметь неоптимальную производительность при очень высокой нагрузке и плохой хеш-функции.
В заключение можно сформулировать общее правило: если задача сводится к частым операциям поиска, проверки принадлежности или агрегации данных по ключу, хеш-таблица, вероятно, будет оптимальным решением, обеспечивающим константное время выполнения этих операций в среднем случае.
#algorithm
Пример 5
Использование хеш-таблиц наиболее оправдано в задачах, требующих частых операций поиска, проверки наличия элемента или подсчёта уникальных значений. Это включает подсчёт частоты элементов в коллекции, поиск дубликатов, реализацию кэшей, решение задачи о двух суммах, группировку данных по определённому признаку, представление графов в виде списков смежности, поиск анаграмм и реализацию множеств. Например, задача поиска двух чисел в массиве, дающих в сумме заданное значение, эффективно решается за один проход с использованием хеш-таблицы для хранения просмотренных элементов.
# Решение задачи "Две суммы" с использованием хеш-таблицы
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return None
numbers = [2, 7, 11, 15]
target = 9
print(two_sum(numbers, target)) # [0, 1] (2 + 7 = 9)
Однако существуют сценарии, где хеш-таблицы могут быть не самым лучшим выбором. Если требуется упорядоченный обход элементов по ключу, данные необходимо часто сортировать или выполнять поиск по диапазону ключей, более подходящими структурами могут оказаться сбалансированные деревья поиска. Также хеш-таблицы требуют дополнительной памяти и могут иметь неоптимальную производительность при очень высокой нагрузке и плохой хеш-функции.
В заключение можно сформулировать общее правило: если задача сводится к частым операциям поиска, проверки принадлежности или агрегации данных по ключу, хеш-таблица, вероятно, будет оптимальным решением, обеспечивающим константное время выполнения этих операций в среднем случае.
#algorithm
👍3
Алгоритмы. Структуры данных. Деревья и Двоичные деревья поиска (BST)
Деревья представляют собой иерархическую структуру данных, аналогичную генеалогическому древу, где элементы, называемые узлами, связаны отношениями родитель-потомок. Верхушку структуры занимает корневой узел, от которого отходят ветви к потомкам. Узлы, не имеющие потомков, называются листьями. Такая организация позволяет эффективно представлять данные с вложенными отношениями.
Примером может служить простое дерево:
Здесь узел со значением 10 является корнем. У него два потомка — узлы 5 и 15. Узел 5, в свою очередь, является родителем для узлов 2 и 7, которые являются листьями. Узел 15 также является листом в этой структуре.
Особым и очень полезным видом дерева является двоичное дерево поиска, или BST. «Двоичное» означает, что каждый узел может иметь не более двух потомков — левого и правого. Ключевая же особенность «дерева поиска» заключается в строгом правиле упорядочивания элементов. Для любого узла все значения в его левом поддереве должны быть меньше его собственного значения, а все значения в правом поддереве — больше. Это свойство делает структуру идеальной для эффективного поиска.
Рассмотрим проверку правила на примере:
Для узла 10: все значения слева (5, 2, 7) меньше 10, а значение справа (15) больше. Для узла 5: значение слева (2) меньше 5, а значение справа (7) больше. Это правило соблюдено для всех узлов, что подтверждает, что дерево является корректным BST.
Главное преимущество двоичного дерева поиска — скорость. Благодаря упорядоченности, алгоритм поиска, начиная с корня, может на каждом шаге отбрасывать половину оставшегося дерева, двигаясь либо влево, либо вправо. Например, чтобы найти число 7 в приведенном дереве, потребуется всего три шага: сравнить с 10 (7<10, идем влево), сравнить с 5 (7>5, идем вправо), сравнить с 7 (найдено). Это значительно быстрее, чем проверять все пять элементов подряд.
Реализация BST начинается с создания базового элемента — узла. На языке Python это выглядит следующим образом:
Этот класс создает объект-узел, который хранит значение
Для добавления новых элементов в дерево с сохранением его основного свойства используется рекурсивная функция вставки.
Алгоритм работает так: начиная с корня, значение для вставки сравнивается с текущим узлом. Если оно больше, рекурсивный вызов идет в правое поддерево, если меньше или равно — в левое. Этот процесс продолжается до тех пор, пока не будет обнаружено пустое место (значение
Одной из фундаментальных операций над деревьями является обход, то есть посещение всех узлов в определенном порядке. Симметричный обход, или inorder traversal, посещает узлы в последовательности: левое поддерево, текущий узел, правое поддерево.
Примененный к BST, такой обход возвращает все значения в отсортированном по возрастанию виде, что является прямым следствием правила упорядочивания. Для нашего примера вызов
Деревья представляют собой иерархическую структуру данных, аналогичную генеалогическому древу, где элементы, называемые узлами, связаны отношениями родитель-потомок. Верхушку структуры занимает корневой узел, от которого отходят ветви к потомкам. Узлы, не имеющие потомков, называются листьями. Такая организация позволяет эффективно представлять данные с вложенными отношениями.
Примером может служить простое дерево:
10
/ \
5 15
/ \
2 7
Здесь узел со значением 10 является корнем. У него два потомка — узлы 5 и 15. Узел 5, в свою очередь, является родителем для узлов 2 и 7, которые являются листьями. Узел 15 также является листом в этой структуре.
Особым и очень полезным видом дерева является двоичное дерево поиска, или BST. «Двоичное» означает, что каждый узел может иметь не более двух потомков — левого и правого. Ключевая же особенность «дерева поиска» заключается в строгом правиле упорядочивания элементов. Для любого узла все значения в его левом поддереве должны быть меньше его собственного значения, а все значения в правом поддереве — больше. Это свойство делает структуру идеальной для эффективного поиска.
Рассмотрим проверку правила на примере:
10
/ \
5 15
/ \
2 7
Для узла 10: все значения слева (5, 2, 7) меньше 10, а значение справа (15) больше. Для узла 5: значение слева (2) меньше 5, а значение справа (7) больше. Это правило соблюдено для всех узлов, что подтверждает, что дерево является корректным BST.
Главное преимущество двоичного дерева поиска — скорость. Благодаря упорядоченности, алгоритм поиска, начиная с корня, может на каждом шаге отбрасывать половину оставшегося дерева, двигаясь либо влево, либо вправо. Например, чтобы найти число 7 в приведенном дереве, потребуется всего три шага: сравнить с 10 (7<10, идем влево), сравнить с 5 (7>5, идем вправо), сравнить с 7 (найдено). Это значительно быстрее, чем проверять все пять элементов подряд.
Реализация BST начинается с создания базового элемента — узла. На языке Python это выглядит следующим образом:
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
Этот класс создает объект-узел, который хранит значение
key и содержит ссылки на левого и правого потомка, изначально пустые. Например, создание корневого узла root = TreeNode(10) дает структуру с одним значением и двумя пустыми указателями.Для добавления новых элементов в дерево с сохранением его основного свойства используется рекурсивная функция вставки.
def insert(root, key):
if root is None:
return TreeNode(key)
else:
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
Алгоритм работает так: начиная с корня, значение для вставки сравнивается с текущим узлом. Если оно больше, рекурсивный вызов идет в правое поддерево, если меньше или равно — в левое. Этот процесс продолжается до тех пор, пока не будет обнаружено пустое место (значение
None), куда и помещается новый узел. Визуально последовательная вставка чисел 10, 5, 15, 2, 7 формирует именно то дерево, что было представлено в примерах выше.Одной из фундаментальных операций над деревьями является обход, то есть посещение всех узлов в определенном порядке. Симметричный обход, или inorder traversal, посещает узлы в последовательности: левое поддерево, текущий узел, правое поддерево.
def inorder_traversal(root):
res = []
if root:
res = inorder_traversal(root.left)
res.append(root.val)
res = res + inorder_traversal(root.right)
return res
Примененный к BST, такой обход возвращает все значения в отсортированном по возрастанию виде, что является прямым следствием правила упорядочивания. Для нашего примера вызов
print(inorder_traversal(root)) вернет список [2, 5, 7, 10, 15].🔥2
Полная последовательность работы программы, создающей дерево и выводящей отсортированный список, демонстрирует практическую пользу структуры.
Однако у простого BST есть существенный недостаток. Если вставлять в него элементы в уже отсортированном порядке, например, 1, 2, 3, 4, 5, дерево выродится в простую цепочку, где каждый новый элемент будет становиться правым потомком предыдущего. В таком случае дерево теряет свое главное преимущество — логарифмическую сложность операций, — и поиск элемента начинает требовать линейного времени, как в обычном списке. Эта проблема иллюстрирует необходимость в более совершенных структурах.
Существуют и другие способы обхода дерева, помимо симметричного, каждый из которых имеет свое применение. Прямой обход посещает узел до его потомков, что полезно для копирования структуры дерева или создания префиксных выражений. Обратный обход посещает узел после его потомков, что применяется при удалении дерева или вычислении постфиксных выражений. Визуализация этих методов помогает понять разницу в порядке обработки данных.
Для решения проблемы вырождения существуют самобалансирующиеся деревья, такие как AVL-дерево или красно-черное дерево. Они автоматически перестраиваются при вставке и удалении элементов, поддерживая свою высоту близкой к логарифмической относительно числа узлов. Это гарантирует, что операции поиска, вставки и удаления всегда будут выполняться за время, пропорциональное логарифму числа элементов, даже в худшем случае. Например, в сбалансированном дереве из миллиона элементов поиск потребует около двадцати сравнений, в то время как в вырожденном дереве-цепочке он может дойти до миллиона операций.
Таким образом, путь развития от общей концепции дерева до самобалансирующихся структур демонстрирует эволюцию идеи: от иерархического хранения данных через введение строгих правил упорядочивания для ускорения поиска к реализации механизмов самоконтроля для гарантии эффективности.
#algorithm
root = TreeNode(10)
insert(root, 5)
insert(root, 15)
insert(root, 2)
insert(root, 7)
print(inorder_traversal(root))
Однако у простого BST есть существенный недостаток. Если вставлять в него элементы в уже отсортированном порядке, например, 1, 2, 3, 4, 5, дерево выродится в простую цепочку, где каждый новый элемент будет становиться правым потомком предыдущего. В таком случае дерево теряет свое главное преимущество — логарифмическую сложность операций, — и поиск элемента начинает требовать линейного времени, как в обычном списке. Эта проблема иллюстрирует необходимость в более совершенных структурах.
Существуют и другие способы обхода дерева, помимо симметричного, каждый из которых имеет свое применение. Прямой обход посещает узел до его потомков, что полезно для копирования структуры дерева или создания префиксных выражений. Обратный обход посещает узел после его потомков, что применяется при удалении дерева или вычислении постфиксных выражений. Визуализация этих методов помогает понять разницу в порядке обработки данных.
Для решения проблемы вырождения существуют самобалансирующиеся деревья, такие как AVL-дерево или красно-черное дерево. Они автоматически перестраиваются при вставке и удалении элементов, поддерживая свою высоту близкой к логарифмической относительно числа узлов. Это гарантирует, что операции поиска, вставки и удаления всегда будут выполняться за время, пропорциональное логарифму числа элементов, даже в худшем случае. Например, в сбалансированном дереве из миллиона элементов поиск потребует около двадцати сравнений, в то время как в вырожденном дереве-цепочке он может дойти до миллиона операций.
Таким образом, путь развития от общей концепции дерева до самобалансирующихся структур демонстрирует эволюцию идеи: от иерархического хранения данных через введение строгих правил упорядочивания для ускорения поиска к реализации механизмов самоконтроля для гарантии эффективности.
#algorithm
👍3
Как настрой?
Вижу, что канал немного устал от алгоритмов, а ведь мы прошли только треть от запланированных постов. Я понимаю, что сейчас темы немного отличаются от традиционных постов о Solidity, DeFi и Web3, но в данный момент, момент активного развития вайб кодинга и нейронных сетей, как никогда важно понимать базовые вещи программирования, чтобы не только создавать сильные проекты, но и понимать, что вообще происходит на уровне кода.
Алгоритмы, структуры данных, типы данных, работа памяти - все это минимальный базис, который должен понимать любой разработчик, даже на уровне "я только пощупать". Это то, что лежит в основе практически любого языка.
В самом начале развития канала я показывал свой путь изучения Solidity, но за кадром оставался весь опыт, который я получил ранее. А ведь это несколько лет разработки на PHP и JS. Т.е. я приступал к изучению нового языка, уже имея представление как это все работает.
Сейчас, изучая нейроные сети, я столкнулся с проблемой типичного новичка. Вместо того, чтобы начать с самых основ, я решил сразу освоить PyTorch. И это было в корне не верно, так как я не знал основ.
А основой тут является знание линейной алгебры, библиотек numpy, matplotlib, scikit-learn и еще пары других... И это все нужно понимать перед тем, как приступать к PyTorch!
Не игнорируйте основы. Программирование такая штука, что если вы пропустите какой-нибудь этап, то все равно однажды придется вернуться к нему, как продвижение дальше не будет происходить.
Продуктивной вам учебы и хороших выходных!
#offtop
Вижу, что канал немного устал от алгоритмов, а ведь мы прошли только треть от запланированных постов. Я понимаю, что сейчас темы немного отличаются от традиционных постов о Solidity, DeFi и Web3, но в данный момент, момент активного развития вайб кодинга и нейронных сетей, как никогда важно понимать базовые вещи программирования, чтобы не только создавать сильные проекты, но и понимать, что вообще происходит на уровне кода.
Алгоритмы, структуры данных, типы данных, работа памяти - все это минимальный базис, который должен понимать любой разработчик, даже на уровне "я только пощупать". Это то, что лежит в основе практически любого языка.
В самом начале развития канала я показывал свой путь изучения Solidity, но за кадром оставался весь опыт, который я получил ранее. А ведь это несколько лет разработки на PHP и JS. Т.е. я приступал к изучению нового языка, уже имея представление как это все работает.
Сейчас, изучая нейроные сети, я столкнулся с проблемой типичного новичка. Вместо того, чтобы начать с самых основ, я решил сразу освоить PyTorch. И это было в корне не верно, так как я не знал основ.
А основой тут является знание линейной алгебры, библиотек numpy, matplotlib, scikit-learn и еще пары других... И это все нужно понимать перед тем, как приступать к PyTorch!
Не игнорируйте основы. Программирование такая штука, что если вы пропустите какой-нибудь этап, то все равно однажды придется вернуться к нему, как продвижение дальше не будет происходить.
Продуктивной вам учебы и хороших выходных!
#offtop
👍14
Алгоритмы. Представление графов и обход в ширину (BFS)
Новая неделя и новый раздел в изучении алгоритмов. Мы плавно переходим к теме алгоритмов на графах и сегодня поговорим о BFS.
Для того чтобы начать изучение алгоритмов на графах, прежде всего следует понять, что такое граф. Визуально граф можно представить как схему городов, соединённых дорогами. В этой структуре города называются вершинами или узлами, а дороги между ними — рёбрами. Например, простейший граф из четырёх вершин может быть изображён так:
Здесь буквы A, B, C и D обозначают вершины, а линии между ними — рёбра, то есть связи.
Для работы с графами в программировании их необходимо каким-либо образом представить в коде. Наиболее распространённым и удобным способом является список смежности. По сути, это словарь, где каждый ключ соответствует определённой вершине, а его значение представляет собой список всех вершин, непосредственно с ней связанных. Возьмём для примера граф, изображённый выше:
Такой формат хранения делает работу с графом интуитивно понятной и эффективной для многих алгоритмов, одним из которых является обход в ширину. Алгоритм обхода в ширину, или BFS, служит для систематического посещения всех вершин графа, начиная с заданной. Его можно сравнить с волнами, расходящимися от брошенного в воду камня: сначала рассматривается начальная вершина, затем все её непосредственные соседи, потом соседи соседей и так далее, слой за слоем. Это гарантирует, что все вершины на расстоянии одного ребра будут посещены раньше, чем вершины, находящиеся на расстоянии двух рёбер.
Для реализации BFS потребуется несколько инструментов: очередь для хранения вершин, которые ожидают обработки, множество для отметки уже посещённых вершин во избежание циклов и повторного посещения, а также список, фиксирующий порядок обхода. Очередь работает по принципу «первым пришёл — первым вышел», что и обеспечивает поэтапное, послойное исследование графа.
Реализация алгоритма на языке Python выглядит следующим образом:
Рассмотрим работу алгоритма на конкретном графе:
Визуально этот граф можно представить так:
Пошаговое выполнение BFS, стартующего от вершины A, будет происходить в таком порядке:
Новая неделя и новый раздел в изучении алгоритмов. Мы плавно переходим к теме алгоритмов на графах и сегодня поговорим о BFS.
Для того чтобы начать изучение алгоритмов на графах, прежде всего следует понять, что такое граф. Визуально граф можно представить как схему городов, соединённых дорогами. В этой структуре города называются вершинами или узлами, а дороги между ними — рёбрами. Например, простейший граф из четырёх вершин может быть изображён так:
A --- B
| |
C --- D
Здесь буквы A, B, C и D обозначают вершины, а линии между ними — рёбра, то есть связи.
Для работы с графами в программировании их необходимо каким-либо образом представить в коде. Наиболее распространённым и удобным способом является список смежности. По сути, это словарь, где каждый ключ соответствует определённой вершине, а его значение представляет собой список всех вершин, непосредственно с ней связанных. Возьмём для примера граф, изображённый выше:
# Граф из примера выше
graph = {
"A": ["B", "C"], # из A можно попасть в B и C
"B": ["A", "D"], # из B можно попасть в A и D
"C": ["A", "D"], # из C можно попасть в A и D
"D": ["B", "C"] # из D можно попасть в B и C
}
Такой формат хранения делает работу с графом интуитивно понятной и эффективной для многих алгоритмов, одним из которых является обход в ширину. Алгоритм обхода в ширину, или BFS, служит для систематического посещения всех вершин графа, начиная с заданной. Его можно сравнить с волнами, расходящимися от брошенного в воду камня: сначала рассматривается начальная вершина, затем все её непосредственные соседи, потом соседи соседей и так далее, слой за слоем. Это гарантирует, что все вершины на расстоянии одного ребра будут посещены раньше, чем вершины, находящиеся на расстоянии двух рёбер.
Для реализации BFS потребуется несколько инструментов: очередь для хранения вершин, которые ожидают обработки, множество для отметки уже посещённых вершин во избежание циклов и повторного посещения, а также список, фиксирующий порядок обхода. Очередь работает по принципу «первым пришёл — первым вышел», что и обеспечивает поэтапное, послойное исследование графа.
Реализация алгоритма на языке Python выглядит следующим образом:
from collections import deque
def bfs(graph, start_node):
# 1. Создаём множество для отслеживания посещённых вершин
visited = set()
# 2. Создаём очередь и добавляем стартовую вершину
queue = deque([start_node])
# 3. Помечаем стартовую вершину как посещённую
visited.add(start_node)
# 4. Список для сохранения порядка обхода
result = []
# 5. Пока в очереди есть вершины
while queue:
# Достаём первую вершину из очереди
node = queue.popleft()
result.append(node)
# Смотрим на всех соседей этой вершины
for neighbor in graph.get(node, []):
# Если соседа ещё не посещали
if neighbor not in visited:
# Помечаем как посещённого
visited.add(neighbor)
# Добавляем в очередь для будущего посещения
queue.append(neighbor)
return result
Рассмотрим работу алгоритма на конкретном графе:
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"]
}Визуально этот граф можно представить так:
A
/ \
B C
/| |
D E F
\ /
Пошаговое выполнение BFS, стартующего от вершины A, будет происходить в таком порядке:
Шаг 0:
Очередь: [A]
Посещённые: {A}
Результат: []
Шаг 1: Обрабатываем A
Очередь: [B, C]
Посещённые: {A, B, C}
Результат: [A]
Шаг 2: Обрабатываем B
Соседи B: A (уже посещён), D, E
Очередь: [C, D, E]
Посещённые: {A, B, C, D, E}
Результат: [A, B]
Шаг 3: Обрабатываем C
Соседи C: A (уже посещён), F
Очередь: [D, E, F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C]
Шаг 4: Обрабатываем D
Соседи D: B (уже посещён)
Очередь: [E, F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D]
Шаг 5: Обрабатываем E
Соседи E: B (уже посещён), F (уже посещён)
Очередь: [F]
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D, E]
Шаг 6: Обрабатываем F
Соседи F: C (уже посещён), E (уже посещён)
Очередь: []
Посещённые: {A, B, C, D, E, F}
Результат: [A, B, C, D, E, F]
Именно использование очереди, которая следует принципу FIFO, и обеспечивает этот порядок обработки вершин слой за слоем.
Ключевым практическим применением BFS является поиск кратчайшего пути в невзвешенном графе. Так как алгоритм исследует вершины по уровням, первый найденный путь до целевой вершины гарантированно будет иметь минимальную длину в терминах количества рёбер. Для этого можно слегка модифицировать базовый алгоритм, храня в очереди не просто вершины, а целые пути:
def bfs_shortest_path(graph, start, end):
visited = set()
queue = deque([[start]]) # Храним путь, а не только вершину
visited.add(start)
while queue:
path = queue.popleft()
node = path[-1] # Последняя вершина в текущем пути
if node == end:
return path # Нашли кратчайший путь!
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
new_path = path + [neighbor]
queue.append(new_path)
return None # Пути нет
Например, для графа ниже:
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "E"],
"D": ["B", "E"],
"E": ["C", "D", "F"],
"F": ["E"]
}
print(bfs_shortest_path(graph, "A", "F"))
# Результат: ['A', 'C', 'E', 'F']Алгоритм вернёт один из кратчайших путей.
Другим полезным применением BFS является определение расстояния от начальной вершины до всех остальных, то есть их уровня. Для этого в очередь вместе с вершиной помещается и информация о её текущем уровне:
def bfs_levels(graph, start):
visited = set()
queue = deque([(start, 0)]) # (вершина, уровень)
visited.add(start)
levels = {}
while queue:
node, level = queue.popleft()
levels[node] = level
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, level + 1))
return levels
Это может быть полезно, например, для анализа социальных сетей, где вершины — это люди, а рёбра — дружеские связи. Запустив BFS от своего профиля, можно найти всех своих друзей и друзей друзей.
Часто возникает вопрос о различии между BFS и обходом в глубину. Основное отличие заключается в стратегии исследования. BFS исследует граф послойно, используя очередь, и потому находит кратчайший путь. DFS же, используя стек или рекурсию, идёт по одному пути до конца, прежде чем вернуться и исследовать другие ветви. Визуально это можно представить так: для дерева с корнем A, детьми B и C, и внуками D, E у B и F у C, BFS даст порядок A, B, C, D, E, F, а DFS может дать порядок A, B, D, E, C, F.
Сложность алгоритма BFS составляет O(V + E), где V — число вершин, а E — число рёбер, так как каждая вершина и каждое ребро обрабатываются один раз. Пространственная сложность оценивается как O(V), поскольку в худшем случае необходимо хранить все вершины в очереди и множестве посещённых.
В заключение можно сказать, что BFS является мощным и фундаментальным алгоритмом для работы с графами. Он эффективно решает задачи поиска кратчайшего пути, проверки связности графа и анализа его структуры по уровням. Важно всегда использовать множество посещённых вершин, чтобы избежать зацикливания и гарантировать корректность работы алгоритма.
#algorithm
#algorithm
👍4
Еще немного наблюдений о вайбкодинге
Буду разбавлять посты про алгоритмы более простыми "насущными" темами.
Буквально вчера до меня начала доходить мысль, что существует два вида вайбкодинга: над одним постоянно смеются, а другой используется в компаниях. И это два кардинально противоположных метода с одним названием.
Сравните два запроса:
"Создай страницу Корзина, где пользователи могут оплачивать товары."
и
"Изучи эти два файла и этот сниппет. В одном файле ты найдешь модели таблиц в базе данных и примеры запросов / ендпонитов. В другом требования к написанию кода. Требуется сделать функционал для покупки выбранных товаров на странице checkout. Твоя задача: 1/2/3/4/5. Перед выполнением задачи составь план и дождись моего подтверждения."
И там, и там по запросу нужен практически идентичный функционал, только во втором случае даны конкретные требования к самому коду, примеры и доступы. В первом случае, запрос писал пользователь без знаний языков программирования, во втором - как минимум понимающий что-то о своем коде.
Это именно то, что и отличают оба вида вайбкодинга - инструкции с примерами. Нейросеть делает не то, что вы хотите, а что вы ей говорите сделать. Она не делает различий между "говнокодом" и "сеньором". При открытой задача (как в первом варианте), она просто берет свои случайные знания из памяти и соединяет их.
Так в одном проекте у вас может быть и код на Python, Ruby, JS и вообще смесь всего. Это вполне может работать. Вопрос в том, как...
Для другого пользователя, который знает и понимает код, разбирается в структуре своего проекта и умеет давать четкие инструкции к нейросети - результаты получаются гораздо лучше.
Задумайтесь также и о том, что даже сеньор может давать четкие указания по редактированию своего кода и нейронка прекрасно справится с задачей, использую декораторы и стиль самого сеньора. Какой код получится в этом случае?
В свое время, да и порой сейчас, многие смеются над PHP языком и у разработчиков была такая шутка: "PHP, как самокат. Из-за того, что любой дурак может сесть на него и поехать, репутация у этой штуки так себе". Вот примерно тоже самое и с вайбкодингом.
Запрос написанный сеньором - приведет к коду уровня сеньор, запрос от школьника - приведет к соответствующему результату.
Поэтому в следующий раз, когда увидите плохой код или ужасную архитектуру, то спросите прежде, кто и как писал это код, а не вините нейронку.
#vibecoding
Буду разбавлять посты про алгоритмы более простыми "насущными" темами.
Буквально вчера до меня начала доходить мысль, что существует два вида вайбкодинга: над одним постоянно смеются, а другой используется в компаниях. И это два кардинально противоположных метода с одним названием.
Сравните два запроса:
"Создай страницу Корзина, где пользователи могут оплачивать товары."
и
"Изучи эти два файла и этот сниппет. В одном файле ты найдешь модели таблиц в базе данных и примеры запросов / ендпонитов. В другом требования к написанию кода. Требуется сделать функционал для покупки выбранных товаров на странице checkout. Твоя задача: 1/2/3/4/5. Перед выполнением задачи составь план и дождись моего подтверждения."
И там, и там по запросу нужен практически идентичный функционал, только во втором случае даны конкретные требования к самому коду, примеры и доступы. В первом случае, запрос писал пользователь без знаний языков программирования, во втором - как минимум понимающий что-то о своем коде.
Это именно то, что и отличают оба вида вайбкодинга - инструкции с примерами. Нейросеть делает не то, что вы хотите, а что вы ей говорите сделать. Она не делает различий между "говнокодом" и "сеньором". При открытой задача (как в первом варианте), она просто берет свои случайные знания из памяти и соединяет их.
Так в одном проекте у вас может быть и код на Python, Ruby, JS и вообще смесь всего. Это вполне может работать. Вопрос в том, как...
Для другого пользователя, который знает и понимает код, разбирается в структуре своего проекта и умеет давать четкие инструкции к нейросети - результаты получаются гораздо лучше.
Задумайтесь также и о том, что даже сеньор может давать четкие указания по редактированию своего кода и нейронка прекрасно справится с задачей, использую декораторы и стиль самого сеньора. Какой код получится в этом случае?
В свое время, да и порой сейчас, многие смеются над PHP языком и у разработчиков была такая шутка: "PHP, как самокат. Из-за того, что любой дурак может сесть на него и поехать, репутация у этой штуки так себе". Вот примерно тоже самое и с вайбкодингом.
Запрос написанный сеньором - приведет к коду уровня сеньор, запрос от школьника - приведет к соответствующему результату.
Поэтому в следующий раз, когда увидите плохой код или ужасную архитектуру, то спросите прежде, кто и как писал это код, а не вините нейронку.
#vibecoding
👍10
Анонс платформы самоучителя по Solidity
Я планировал потрать еще некоторое время, чтобы полностью доработать платформу, где будут выложены все модули курса по Solidity + модуль по Foundry + модуль с практикой аудита кода, но текущие веяния в области ограничений Телеграмма, заставляют выпускать все раньше.
Сама платформа готова на 98% - 99%, я все еще просматривая материал на предмет каких-либо недочетов, некорректного отображения, мелких багов и т.д. И, в целом, все готово к открытию.
Вчера я открыл доступ к платформе для учеников Летнего модуля 3 потока. Собираю пока обратную связь. Кстати, если вы проходили Летний и 3 модуль 2 потока, то для вас доступ будет бесплатный, как я и обещал ранее. У вас будет доступ не только к материалам на каналах Телеграм, но и на одном ресурсе все вместе, в удобном формате.
Для всех желающих до конца февраля будет специальная цена на весь курс - 5000 рублей. Позже цена будет выше, и можно будет купить модули по отдельности.
Отличия самоучителя от курса в Телеграм то, что не будет проверок домашних заданий. В любом случае вы все равно сможете задавать вопросы в чате канала и получать ответ не только от меня, но и от других опытных участников.
Если после первых тестов на платформе все будет хорошо, то общий доступ открою уже в следующую среду - 18 февраля.
Всем хорошего дня и продуктивной работы!
#solidity
Я планировал потрать еще некоторое время, чтобы полностью доработать платформу, где будут выложены все модули курса по Solidity + модуль по Foundry + модуль с практикой аудита кода, но текущие веяния в области ограничений Телеграмма, заставляют выпускать все раньше.
Сама платформа готова на 98% - 99%, я все еще просматривая материал на предмет каких-либо недочетов, некорректного отображения, мелких багов и т.д. И, в целом, все готово к открытию.
Вчера я открыл доступ к платформе для учеников Летнего модуля 3 потока. Собираю пока обратную связь. Кстати, если вы проходили Летний и 3 модуль 2 потока, то для вас доступ будет бесплатный, как я и обещал ранее. У вас будет доступ не только к материалам на каналах Телеграм, но и на одном ресурсе все вместе, в удобном формате.
Для всех желающих до конца февраля будет специальная цена на весь курс - 5000 рублей. Позже цена будет выше, и можно будет купить модули по отдельности.
Отличия самоучителя от курса в Телеграм то, что не будет проверок домашних заданий. В любом случае вы все равно сможете задавать вопросы в чате канала и получать ответ не только от меня, но и от других опытных участников.
Если после первых тестов на платформе все будет хорошо, то общий доступ открою уже в следующую среду - 18 февраля.
Всем хорошего дня и продуктивной работы!
#solidity
1🎉16❤4🔥3
Что будет с Solidity и блокчейном?
На выходных в компании друзей подняли эту тему и пришли к выводу, что будет застой до одного переломного момента...
Драйвером роста в начале 2020 годов послужило то, что это были "новые деньги", где можно было быстро заработать. Появилось множество обменников и первые DeFi приложения, которые поняли смысл торговых операций и быстро вошли в топ на фоне, того, что остальные клепали свои токены.
Затем маркетинг и NFT подлили масла в огонь, и тогда "вход" в крипту через картинки стал проще. Знаменитости и артисты продавали NFT своим подписчикам и это считалось писком моды.
Затем были мемкоины... Даже простой обыватель мог один раз кликнуть на кнопку на сайте и запустить свой мем.
И все сошло на нет на 80% - 90%. Про NFT все забыли, мемкоины остались спекулянтам, а web3 захватили институционалы и правительство разных стран.
Solidity и блокчейн никуда не денется, туда вложено слишком много денег. Но и однотипные "Uniswap" / "Aave" / "GMX" уже всем приелись: инвесторы не дают деньги на их развитие командам, а без хорошего маркетинга ни один проект не взлетит.
Так что же за переломный момент, к которому мы пришли в компании?
На зарубежных сайтах я все чаще вижу возможность оплатить криптой за какой-либо сервис или товар. Представьте на секунду, что будет если такие платежи адаптирует Steam, Amazon, Spotify и другой популярный маркетплейс! А это уже потихоньку на подходе.
И это первая часть такого момента. Дальше будет внедрение крипты в мелкие магазинчики, чтобы можно было банально "купить хлеб за биткоин". И это уже тоже есть и развивается!
Конечно, многим странам до такой адаптации еще очень долго, но кто нам запретит, скажем, покупать на Amazon товары и доставлять их к себе?
Это даст очень большой буст всей сфере. Будут появляться уже не финансовые проекты в web3, а много SaaS, агентов и т.д., которые начнут упрощать жизнь и продавцам и покупателям.
Когда это будет? Думаю, когда все успокоятся с ИИ и агентами. А там, кто его знает. Но тенденции идут.
А как вы думаете?
#web3
На выходных в компании друзей подняли эту тему и пришли к выводу, что будет застой до одного переломного момента...
Драйвером роста в начале 2020 годов послужило то, что это были "новые деньги", где можно было быстро заработать. Появилось множество обменников и первые DeFi приложения, которые поняли смысл торговых операций и быстро вошли в топ на фоне, того, что остальные клепали свои токены.
Затем маркетинг и NFT подлили масла в огонь, и тогда "вход" в крипту через картинки стал проще. Знаменитости и артисты продавали NFT своим подписчикам и это считалось писком моды.
Затем были мемкоины... Даже простой обыватель мог один раз кликнуть на кнопку на сайте и запустить свой мем.
И все сошло на нет на 80% - 90%. Про NFT все забыли, мемкоины остались спекулянтам, а web3 захватили институционалы и правительство разных стран.
Solidity и блокчейн никуда не денется, туда вложено слишком много денег. Но и однотипные "Uniswap" / "Aave" / "GMX" уже всем приелись: инвесторы не дают деньги на их развитие командам, а без хорошего маркетинга ни один проект не взлетит.
Так что же за переломный момент, к которому мы пришли в компании?
На зарубежных сайтах я все чаще вижу возможность оплатить криптой за какой-либо сервис или товар. Представьте на секунду, что будет если такие платежи адаптирует Steam, Amazon, Spotify и другой популярный маркетплейс! А это уже потихоньку на подходе.
И это первая часть такого момента. Дальше будет внедрение крипты в мелкие магазинчики, чтобы можно было банально "купить хлеб за биткоин". И это уже тоже есть и развивается!
Конечно, многим странам до такой адаптации еще очень долго, но кто нам запретит, скажем, покупать на Amazon товары и доставлять их к себе?
Это даст очень большой буст всей сфере. Будут появляться уже не финансовые проекты в web3, а много SaaS, агентов и т.д., которые начнут упрощать жизнь и продавцам и покупателям.
Когда это будет? Думаю, когда все успокоятся с ИИ и агентами. А там, кто его знает. Но тенденции идут.
А как вы думаете?
#web3
👍11🤔3