Алгоритмы. Быстрая сортировка

Быстрая сортировка представляет собой эффективный алгоритм, основанный на стратегии «разделяй и властвуй». Представьте себе задачу упорядочить книги на полке по высоте. Вместо того чтобы последовательно сравнивать каждую книгу с каждой, что потребовало бы значительного времени, можно выбрать одну книгу среднего размера в качестве условного эталона. Все книги меньше этого эталона помещаются слева, а все больше — справа. Затем эта же процедура рекурсивно применяется к каждой из образовавшихся групп. Именно эта идея лежит в основе быстрой сортировки.

Алгоритм работает, разделяя исходный массив данных на части относительно специально выбранного элемента, который называется опорным или пивотом. Стратегия «разделяй и властвуй» подразумевает три этапа: сначала большую задачу разбивают на меньшие независимые подзадачи, затем каждую из них решают, и наконец, полученные решения объединяют в окончательный результат. Этот процесс можно представить как преобразование большого беспорядка в несколько маленьких, которые затем приводятся в порядок.

Рассмотрим работу алгоритма пошагово на примере массива [64, 34, 25, 12, 22, 11, 90]. Первым шагом является выбор опорного элемента. Это может быть первый, последний, средний или случайный элемент массива. В нашем примере выберем средний элемент по индексу: arr[3] = 12.

Второй шаг — разделение массива. Все элементы, меньшие опорного, помещаются в одну группу, равные ему — в другую, а большие — в третью.

Меньше 12:  [11]
Равно 12:   [12]
Больше 12:  [64, 34, 25, 22, 90]

Наглядно это можно изобразить так:

          [64, 34, 25, 12, 22, 11, 90]
                      ↓
          выбираем pivot = 12
                      ↓
    ┌─────────────────┼─────────────────┐
    ↓                 ↓                 ↓
  [11]              [12]      [64, 34, 25, 22, 90]
 (меньше)          (равно)          (больше)

Третий шаг — рекурсивное применение того же алгоритма к левой и правой частям, так как группа равных опорному элементу уже считается отсортированной. Для левой части [11], состоящей из одного элемента, рекурсия завершается. Для правой части [64, 34, 25, 22, 90] снова выбирается опорный элемент, например, средний — 25, и процесс разделения повторяется.
Четвертый шаг — объединение результатов. После того как все рекурсивные вызовы завершены, отсортированные части собираются вместе. Сборка происходит снизу вверх: отсортированные подмассивы меньших размеров объединяются с опорными элементами.

Уровень 4: [] + [64] + [90] = [64, 90]
Уровень 3: [] + [34] + [64, 90] = [34, 64, 90]
Уровень 2: [22] + [25] + [34, 64, 90] = [22, 25, 34, 64, 90]
Уровень 1: [11] + [12] + [22, 25, 34, 64, 90] = [11, 12, 22, 25, 34, 64, 90]

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

[64, 34, 25, 12, 22, 11, 90]
         pivot=12
        /    |    \
     [11]   [12]  [64, 34, 25, 22, 90]
      ↓               pivot=25
    [11]            /    |    \
                 [22]   [25]  [64, 34, 90]
                  ↓           pivot=34
                [22]         /   |   \
                           []  [34] [64, 90]
                                     pivot=64
                                    /   |   \
                                  []  [64]  [90]
                                            ↓
                                           [90]

Сборка снизу вверх:

[11] + [12] + ([22] + [25] + ([] + [34] + ([] + [64] + [90])))
= [11, 12, 22, 25, 34, 64, 90]

Реализация этого алгоритма на Python демонстрирует его лаконичность. Ключевая часть — рекурсивное разделение и объединение массивов.

def quick_sort(arr):
    """Быстрая сортировка списка."""
    # Базовый случай: массив из 0 или 1 элемента уже отсортирован
    if len(arr) <= 1:
        return arr
    else:
        # Выбираем опорный элемент (средний по индексу)
        pivot = arr[len(arr) // 2]
        
        # Создаём три подмассива:
        # left - все элементы меньше опорного
        left = [x for x in arr if x < pivot]
        
        # middle - все элементы равные опорному
        middle = [x for x in arr if x == pivot]
        
        # right - все элементы больше опорного
        right = [x for x in arr if x > pivot]
        
        # Рекурсивно сортируем левую и правую части,
        # объединяем результаты
        return quick_sort(left) + middle + quick_sort(right)

Наличие группы middle в реализации принципиально важно для корректной обработки массивов с повторяющимися элементами. Без неё алгоритм может попасть в бесконечную рекурсию, пытаясь сортировать одинаковые значения.

Производительность быстрой сортировки в первую очередь зависит от выбора опорного элемента. Хороший выбор, когда пивот делит массив примерно пополам, приводит к временной сложности O(n log n) в лучшем и среднем случаях. Это происходит потому, что глубина рекурсии составляет log n уровней, и на каждом уровне выполняется порядка n операций. Однако если опорный элемент постоянно оказывается минимальным или максимальным, дерево рекурсии становится несбалансированным, что приводит к худшему случаю со сложностью O(n²). Для улучшения выбора пивота применяют такие методы, как случайный выбор или выбор медианы из трех элементов — первого, среднего и последнего. Например:

import random
pivot = arr[random.randint(0, len(arr)-1)]

Пространственная сложность представленной реализации составляет O(n), так как на каждом уровне рекурсии создаются новые списки. Однако существует оптимизированная версия алгоритма, выполняющая сортировку на месте, которая требует O(log n) дополнительной памяти для стека рекурсии.

Сравнение быстрой сортировки с сортировкой слиянием выявляет их ключевые различия. Оба алгоритма имеют среднюю сложность O(n log n), но сортировка слиянием гарантирует эту сложность даже в худшем случае, тогда как быстрая сортировка может деградировать до O(n²). С другой стороны, быстрая сортировка часто оказывается быстрее на практике из-за меньших константных множителей и может быть реализована с меньшим потреблением памяти. Сортировка слиянием является стабильной — она сохраняет относительный порядок равных элементов, что не всегда верно для классической in-place реализации быстрой сортировки.

Встроенная функция sort() в Python использует более сложный гибридный алгоритм — Timsort. Он сочетает в себе идеи сортировки слиянием и сортировки вставками. Timsort эффективно использует уже существующие упорядоченные подпоследовательности в данных, что делает его особенно быстрым для частично отсортированных массивов, где он может достигать сложности O(n). Этот алгоритм является стабильным и гарантирует производительность O(n log n) в худшем случае, что делает его отличным выбором для стандартной библиотеки Python. Пример его использования:

data = [64, 34, 25, 12, 22, 11, 90]
data.sort()
sorted_data = sorted(data, reverse=True)

Таким образом, быстрая сортировка остается важным и фундаментальным алгоритмом, наглядно демонстрирующим принцип «разделяй и властвуй». Она эффективна на практике, хотя и требует внимательного подхода к выбору опорного элемента. Для большинства повседневных задач предпочтительнее использовать оптимизированные встроенные средства языка, такие как Timsort в Python, но глубокое понимание работы быстрой сортировки необходимо для анализа алгоритмов и решения специализированных задач.

#algorithm

Пара слов о моем проекте

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

Когда ты создаешь сайт / приложение / контракт, то явно понимаешь, как его нужно использовать, что вводить и куда нажимать (особенно, если важен порядок действий). Но все меняется когда ты даешь доступ пользователям.

Я тоже явно представлял, что нужно вводить и как делать запросы, чтобы получать результаты. Но то, что у меня в голове было логически обоснованным, оказалось совершенно не понятно с внешнего взгляда.

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

Функция чата определенно сбивала с толку. Мы все привыкли, что можно ввести какое-нибудь сообщение, chatGPT поймет намеренье и выдаст нужную (или около-нужную информацию). Тут было также. Не смотря на то, что это MCP/API сервер предназначенный для использования вместе с нейронками (чтобы они сами формировали запроси и делали анализ), многие также не доходили до установки этого сервера, заканчивая свой путь на первом запросе чата.

Кроме того, оказалось, что многие также не понимают работу семантического поиска.

В итоге оказалось, что UI/UX не приспособлен для передачи идеи проекта и его нужно менять, чем я потихоньку и занимаюсь.

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

Также обновлена форма для чата. Вместо одного поля, теперь два: одно для запроса, другое для функций. Оба поля получили более описательные placeholder.

В планах, сделать более просто навигацию (хотя думал, что разбитие по вкладкам будет удачным решением...), а также добавить пару других режимов в чате, чтобы модель llm могла корректировать запросы пользователей, делая их более подходящими для релевантного поиска.

В общем, всем большое спасибо за обратную связь!

#hornetmcp

Алгоритм. Бинарный поиск

Идем дальше в нашем цикле постов про алгоритмы.

Рассмотрим эффективный алгоритм поиска, основанный на простой и элегантной идее — бинарный поиск. Чтобы понять его суть, представьте себе классическую игру, где требуется угадать число в диапазоне от 1 до 100. Неэффективный подход — перебирать числа по порядку: 1, 2, 3 и так далее. В худшем случае это потребует ста попыток. Гораздо более разумная стратегия заключается в том, чтобы каждый раз делить оставшийся диапазон пополам. Например, сначала спросить: «Число больше 50?». Получив ответ, вы сразу исключаете половину всех возможных чисел, затем повторяете эту процедуру с оставшимся интервалом. Именно этот принцип — последовательное деление области поиска пополам — и лежит в основе алгоритма бинарного поиска.

Крайне важным условием для его применения является предварительная сортировка данных. Алгоритм опирается на упорядоченность массива, чтобы делать корректные выводы о местоположении искомого элемента. Рассмотрим пошаговый процесс на примере отсортированного массива [11, 12, 22, 25, 34, 64, 90]. Предположим, нам нужно найти число 22.

На первом шаге определяются границы поиска: нижняя low (индекс 0), верхняя high (индекс 6). Вычисляется средний индекс: mid = (0 + 6) // 2 = 3. Элемент с индексом 3 равен 25. Поскольку 25 больше искомого значения 22, делается вывод, что элемент находится в левой половине массива. Таким образом, верхняя граница high смещается на позицию mid - 1, то есть на индекс 2.

Теперь область поиска сузилась до элементов с индексами от 0 до 2. Снова вычисляется середина: mid = (0 + 2) // 2 = 1. Элемент arr[1] равен 12. Так как 12 меньше 22, становится ясно, что цель находится в правой части текущего интервала. Нижняя граница low сдвигается: low = mid + 1 = 2.

На третьем шаге границы low и high совпадают (индекс 2). Средний элемент, arr[2], равен 22, что полностью соответствует искомому значению. Алгоритм завершается успешно, возвращая индекс 2.

Этот процесс можно представить в виде наглядной визуализации:

Исходный массив (7 элементов):
┌────┬────┬────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │ 25 │ 34 │ 64 │ 90 │
└────┴────┴────┴────┴────┴────┴────┘
  0    1    2    3    4    5    6

Ищем: 22

Итерация 1: Проверяем середину (индекс 3 = значение 25)
┌────┬────┬────┬────┬────┬────┬────┐
│ 11 │ 12 │ 22 │[25]│ 34 │ 64 │ 90 │
└────┴────┴────┴────┴────┴────┴────┘
             ✗ 25 > 22, ищем левее

Итерация 2: Область поиска сузилась до [11, 12, 22]
                Проверяем индекс 1 = значение 12
┌────┬────┬────┐
│ 11 │[12]│ 22 │
└────┴────┴────┘
      ✗ 12 < 22, ищем правее

Итерация 3: Область поиска = [22]
                Проверяем индекс 2 = значение 22
┌────┐
│[22]│
└────┘
  ✓ Найдено!

Реализация данного алгоритма на языке Python выглядит следующим образом:

def binary_search(arr, target):
    """Бинарный поиск элемента в отсортированном списке."""
    low = 0              # Левая граница области поиска
    high = len(arr) - 1  # Правая граница области поиска
    
    while low <= high:   # Пока область поиска не пуста
        mid = (low + high) // 2  # Находим средний индекс
                                  # // - целочисленное деление
        
        if arr[mid] == target:   # Если нашли - возвращаем индекс
            return mid
        elif arr[mid] < target:  # Если середина меньше искомого
            low = mid + 1        # Ищем в правой половине
        else:                    # Если середина больше искомого
            high = mid - 1       # Ищем в левой половине
    
    return -1  # Если элемент не найден, возвращаем -1

На каждой итерации цикла вычисляется индекс середины текущего интервала. Затем значение этого элемента сравнивается с целевым. Если они равны, поиск завершается. Если средний элемент меньше искомого, нижняя граница смещается за середину, сужая поиск до правой половины. В противном случае, если средний элемент больше, поиск продолжается в левой половине. Цикл выполняется до тех пор, пока границы не пересекутся, что будет означать отсутствие элемента в массиве.

Для закрепления рассмотрим несколько примеров. В первом случае элемент отсутствует в массиве:

sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 50
print(binary_search(sorted_data, target))  # Вывод: -1

Алгоритм выполнит следующие шаги: сначала проверит середину (25), затем, так как 25 меньше 50, перейдет к правой половине [34, 64, 90]. Проверив элемент 64, который больше 50, он перейдет к левой части этого подмассива, [34]. После сравнения 34 с 50 границы low и high пересекутся, и будет возвращено значение -1.

Поиск первого и последнего элементов также работает корректно:

sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 11
print(binary_search(sorted_data, target))  # Вывод: 0

target = 90
print(binary_search(sorted_data, target))  # Вывод: 6

Главное преимущество бинарного поиска — его исключительная эффективность. Сложность алгоритма оценивается как O(log n), что означает логарифмическую зависимость количества операций от размера данных. Это становится возможным благодаря тому, что на каждом шаге область поиска сокращается вдвое. Например, для массива из 100 элементов в худшем случае потребуется не более 7 проверок, для миллиона элементов — около 20. В сравнении с линейным поиском, который в худшем случае проверяет все элементы, выигрыш становится колоссальным, особенно на больших объемах данных.

Теперь обратимся к ключевому вопросу: почему бинарный поиск неприменим к неотсортированным данным? Вся логика алгоритма строится на предположении, что если элемент в середине меньше искомого, то все элементы слева от него тоже заведомо меньше. Это свойство гарантировано только в отсортированном массиве. В противном случае, отбросив какую-либо половину, мы можем случайно потерять искомый элемент. Проиллюстрируем это на примере массива [64, 11, 90, 22, 25, 12, 34]. При поиске числа 90 алгоритм, проверив середину (22), решит, что нужно искать справа, так как 22 меньше 90. Однако правая часть [25, 12, 34] не содержит 90, хотя само число 90 присутствует в исходном массиве слева от проверяемой середины. Таким образом, на несортированных данных бинарный поиск дает ненадежный результат.

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

def binary_search_recursive(arr, target, low, high):
    """Рекурсивная версия бинарного поиска."""
    
    # Базовый случай: область поиска пуста
    if low > high:
        return -1
    
    # Находим середину
    mid = (low + high) // 2
    
    # Проверяем средний элемент
    if arr[mid] == target:
        return mid  # Нашли!
    elif arr[mid] < target:
        # Рекурсивно ищем в правой половине
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        # Рекурсивно ищем в левой половине
        return binary_search_recursive(arr, target, low, mid - 1)


# Использование:
sorted_data = [11, 12, 22, 25, 34, 64, 90]
target = 22
result = binary_search_recursive(sorted_data, target, 0, len(sorted_data) - 1)
print(result)  # Вывод: 2

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

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

Подводя итог, можно выделить ключевые характеристики бинарного поиска. Во-первых, он применим исключительно к отсортированным массивам. Во-вторых, его временная сложность O(log n) делает его чрезвычайно быстрым для больших наборов данных. В-третьих, принцип работы основан на постоянном уменьшении области поиска вдвое. Наконец, алгоритм возвращает индекс найденного элемента или специальное значение (например, -1), если элемент отсутствует. По сравнению с линейным поиском бинарный поиск демонстрирует подавляющее преимущество в скорости на крупных массивах, что делает его одним из фундаментальных алгоритмов в информатике.

#algorithm

Мои "пять копеек" про нашумевший Clawdbot

Как многие из вас уже знают, в сети, а частности в Твиттере, уже несколько дней не утихают петь дифирамбы новому ИИ агенту под названием Clawdbot, который с позавчерашнего дня называется moltbot (смена названия произошла по просьбе / требованию / угрозах / шантажу Antropic). Всеобщее восхищение сопровождается такими же большими возгласами про безопасность бота и покупкой Apple Mac mini для его работы.

Я не буду рассказывать про то, что и так можно найти в каждом паблике посвященном ИИ, просто скажу несколько слов для тех, кто только хочет попробовать установить бота и начать им пользоваться.

В начале хочу сказать, что у меня есть некоторые предубеждения связанные с ИИ ботами и агентами, которые постоянно лезут в частную жизнь: устанавливаются в браузер, умеют управлять файлами и папками на компьютере, отвечают на почту и т.д. Я не могу точно сказать как обрабатывается эта информация на серверах ИИ, но точно не хочу, чтобы где-то светились мои пароли, API ключи и прочие данные. Поэтому, во-первых, я бы не рекомендовал устанавливать бота на свой личный / рабочий компьютер. Лучшим решением будет выделить отдельный блок (компьютер, планшет, мини-пк) для работы бота. Там не должно быть никаких ваших личных данных, которые вы не хотите чтобы попали в сети. VPS сервер также может подойти, если вы знаете как работать с ним и готовы платить за это.

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

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

В-четвертых, лучше всего будет использовать свои локальные ИИ модели. Но так как у большинства из нас вряд ли хватит достаточно мощностей для поддержки более-менее хорошей модели ИИ, то крайне рекомендую сначала попробовать использовать OpenRouter и его бесплатные модели. Это будет медленнее, но финансово безопаснее. Я заметил, что даже простые сообщения в чате с ботом, как например "Привет, ты тут?" могут занимать около 13к токенов, так как сообщение включает и промт, и другие данные, которые передает бот в модель ИИ. Это может привести к быстрой растрате ваших активов, либо к огромным счетам.

В-пятых, не бегите покупать Apple Mac Mini. Бот прекрасно работает на системах Linux или даже в Windows WSL. Я использую для тестов планшет на Windows - Chuwi hi10 max - и все прекрасно работает. Принимайте решение о покупке, когда точно будете знать, что подобный агент понадобится вам в ежедневной работе.

В-шестых, в период хайпа пользователи делятся самыми банальными проектами, которые можно сделать с более безопасными агентами. Например, проверка и ответ на почту, составление графика встреч и управление календарем, напоминания, структура тренировок или диеты, трекер привычек и т.д. Ну это как купить rtx-4090 и играть в тетрис. Думаю, стоит немного подождать и посмотреть, что действительного крутого будут делать пользователи с этим ботом.

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

Всем хорошего кода и безопасных систем!

#clawdbot #moltbot

Алгоритмы. Структуры данных. Связные списки

Переходим к новому разделу в нашем цикле, и теперь в нескольких последующих постах поговорим про структуры данных.

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

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

Массив в памяти:
[10][20][30][40][50]
 ↑   ↑   ↑   ↑   ↑
 0   1   2   3   4  ← индексы

Связный список же напоминает квест по городу, где дома с подсказками разбросаны в разных местах. Каждый дом содержит не только информацию, но и адрес следующего пункта маршрута. Чтобы добраться до сотого дома, придется последовательно посетить все предыдущие. В памяти узлы списка могут располагаться где угодно, будучи связанными лишь ссылками.

Связный список в памяти:
[10|•]---→[20|•]---→[30|•]---→[40|•]---→[50|×]
 ↑                                        ↑
head                                     tail
(начало)                                (конец)

Основным строительным блоком списка является узел. Этот контейнер включает в себя два поля: для хранения данных и для ссылки на последующий узел. Визуализировать его можно так:

┌─────────────┐
│  data: 42   │  ← наши данные
│  next: •────┼──→ следующий узел
└─────────────┘

Реализуется узел следующим образом:

class Node:
    def __init__(self, data):
        self.data = data  # Храним данные
        self.next = None  # Изначально никуда не указываем

Создание нескольких связанных узлов выглядит следующим образом:

# Создаем три отдельных узла
node1 = Node(10)  # [10|None]
node2 = Node(20)  # [20|None]
node3 = Node(30)  # [30|None]

# Связываем их вместе
node1.next = node2  # [10|•]→[20|None]
node2.next = node3  # [10|•]→[20|•]→[30|None]

# Теперь у нас есть цепочка: 10 → 20 → 30

Сам связный список — это управляющая структура, которая хранит лишь ссылку на самый первый узел, называемый головой. Изначально список пуст.

class LinkedList:
    def __init__(self):
        self.head = None  # Изначально список пустой

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

def append(self, data):
    new_node = Node(data)  # Создаем новый узел
    
    # Случай 1: Список пустой
    if not self.head:
        self.head = new_node  # Новый узел становится головой
        return
    
    # Случай 2: В списке уже есть элементы
    last_node = self.head
    # Идем по цепочке до последнего узла
    while last_node.next:
        last_node = last_node.next
    
    # Присоединяем новый узел к концу
    last_node.next = new_node

Процесс можно проследить наглядно:

Шаг 1: Пустой список
head → ×

Добавляем 10:
head → [10|×]

Добавляем 20:
head → [10|•]→[20|×]

Добавляем 30:
head → [10|•]→[20|•]→[30|×]

Более подробный пример использования:

ll = LinkedList()

# Добавляем первый элемент
ll.append(1)
# head → [1|×]

# Добавляем второй элемент
ll.append(2)
# head → [1|•]→[2|×]
#         ↑     ↑
#      last   new_node

# Добавляем третий элемент
ll.append(3)
# head → [1|•]→[2|•]→[3|×]
#                ↑     ↑
#             last   new_node

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

def display(self):
    elements = []  # Список для сбора данных
    current_node = self.head  # Начинаем с головы
    
    # Идем по цепочке, пока не дойдем до конца
    while current_node:
        elements.append(current_node.data)  # Собираем данные
        current_node = current_node.next    # Переходим к следующему
    
    return elements

Этот обход работает так:

head → [10|•]→[20|•]→[30|×]
       ↑
    current_node
    elements = []

Шаг 1:
current_node указывает на [10]
elements = [10]
current_node = current_node.next

Шаг 2:
head → [10|•]→[20|•]→[30|×]
              ↑
           current_node
elements = [10, 20]
current_node = current_node.next

Шаг 3:
head → [10|•]→[20|•]→[30|×]
                     ↑
                  current_node
elements = [10, 20, 30]
current_node = current_node.next

Шаг 4:
current_node = None (конец списка)
Выходим из цикла

Полная реализация простого связного списка с методами добавления и отображения объединяет все вышесказанное.

Пример 1

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

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head  # Новый узел указывает на старую голову
    self.head = new_node       # Новый узел становится головой

Визуализируя это:

Было:
head → [10|•]→[20|×]

Добавляем 5 в начало:
new_node = [5|×]

new_node.next = head:
[5|•]→[10|•]→[20|×]

head = new_node:
head → [5|•]→[10|•]→[20|×]

Поиск элемента по значению также осуществляется путем последовательного обхода.

def find(self, data):
    current_node = self.head
    position = 0
    
    while current_node:
        if current_node.data == data:
            return position  # Нашли!
        current_node = current_node.next
        position += 1
    
    return -1  # Не нашли

Пример поиска:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)

print(ll.find(20))  # Вывод: 1 (индекс элемента 20)
print(ll.find(99))  # Вывод: -1 (элемент не найден)

Выбор между связным списком и массивом зависит от конкретной задачи, поскольку каждая структура имеет свои сильные и слабые стороны. Преимуществом связного списка является скорость вставки и удаления элементов в начале списка, которая выполняется за O(1), так как требуется лишь изменить несколько ссылок.

# Добавить в начало связного списка
def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
# Всего 3 операции - очень быстро!

Кроме того, связный список обладает динамическим размером, расширяясь по мере необходимости, и вставка в середину, если известен предыдущий узел, также выполняется за O(1). Однако у списка есть и недостатки: доступ к элементу по индексу требует полного обхода от головы до нужной позиции, что занимает O(n) времени. Каждый узел расходует дополнительную память на хранение ссылки, а из-за разрозненного расположения узлов в памяти перебор может быть менее эффективным с точки зрения кеша процессора.

Массивы, напротив, блестяще справляются с доступом по индексу за O(1), используют память более экономно и обеспечивают быстрый последовательный перебор. Но они проигрывают при вставке или удалении элементов в начале или середине, так как это требует сдвига всех последующих элементов.

Итоговое сравнение можно представить в виде таблицы: для доступа по индексу предпочтителен массив (O(1)), тогда как для частых вставок и удалений в начале лучше подойдет связный список (O(1)).

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

def delete_by_value(self, data):
    # Случай 1: Список пустой
    if not self.head:
        return
    
    # Случай 2: Удаляем голову
    if self.head.data == data:
        self.head = self.head.next  # Просто сдвигаем голову
        return
    
    # Случай 3: Удаляем элемент из середины/конца
    current_node = self.head
    
    # Ищем узел ПЕРЕД тем, который нужно удалить
    while current_node.next:
        if current_node.next.data == data:
            # "Перепрыгиваем" через удаляемый узел
            current_node.next = current_node.next.next
            return
        current_node = current_node.next

Наглядно этот процесс выглядит так:

Исходный список:
head → [10|•]→[20|•]→[30|•]→[40|×]

Удаляем 20:

Шаг 1: Находим узел ПЕРЕД удаляемым
head → [10|•]→[20|•]→[30|•]→[40|×]
       ↑       ↑
    current  current.next (удаляем это)

Шаг 2: "Перепрыгиваем" через 20
current.next = current.next.next

head → [10|•]─────→[30|•]→[40|×]
             \    /
              [20|•] (потерян, будет удален сборщиком мусора)

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

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.append(40)

print(ll.display())  # [10, 20, 30, 40]

ll.delete_by_value(20)
print(ll.display())  # [10, 30, 40]

ll.delete_by_value(10)  # Удаляем голову
print(ll.display())  # [30, 40]

Более сложной и гибкой вариацией является двусвязный список. В нем каждый узел содержит уже две ссылки: не только на следующий, но и на предыдущий узел. Это позволяет обходить список в обоих направлениях.

class DoubleNode:
    def __init__(self, data):
        self.data = data
        self.next = None  # Ссылка вперед
        self.prev = None  # Ссылка назад

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

Двусвязный список:
None ← head                    tail → None
       [×|10|•]↔️[•|20|•]↔️[•|30|×]
        ↑    ↑    ↑    ↑    ↑    ↑
       prev next prev next prev next

Реализация двусвязного списка включает поддержку ссылки не только на голову, но и на хвост.

Пример 2

Пример показывает его новые возможности:

dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)

print(dll.display_forward())   # [10, 20, 30]
print(dll.display_backward())  # [30, 20, 10]

Преимущества двусвязного списка включают возможность двустороннего обхода, более простое удаление узла, так как ссылка на предыдущий элемент уже известна, и добавление в конец за O(1) благодаря наличию ссылки на хвост. Однако за эти удобства приходится платить дополнительной памятью на хранение второй ссылки в каждом узле и усложнением логики управления связями.

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

#algorithm

Алгоритмы. Структуры данных. Хеш-таблицы

Хеш-таблица представляет собой структуру данных, которая реализует ассоциативный массив, обеспечивая возможность хранения пар «ключ–значение». Её принцип работы можно сравнить с организацией библиотеки, где каждая книга имеет уникальный инвентарный номер. Если книги просто сложены в беспорядке, поиск нужной займет много времени. Однако если они расставлены на полках в соответствии со своими номерами, нужный экземпляр находится практически мгновенно. Именно такую «умную» систему и воплощает хеш-таблица — это своего рода шкаф с ячейками, где каждый элемент данных хранится в ячейке, определяемой своим ключом.

Основными компонентами хеш-таблицы являются ключ, значение, хеш-функция и массив ячеек, часто называемый корзинами. Ключ служит уникальным идентификатором или адресом, по которому можно найти связанное с ним значение. Хеш-функция выступает в роли специального преобразователя: она принимает ключ на вход и вычисляет целочисленный индекс — номер конкретной ячейки в массиве, куда следует поместить или откуда нужно извлечь значение. Этот массив и есть физическое хранилище данных.

Работа хеш-таблицы происходит по следующему алгоритму. Допустим, имеется массив из десяти ячеек с индексами от 0 до 9. Когда требуется сохранить пару, например, "apple" : 5, хеш-функция обрабатывает ключ "apple" и возвращает число в диапазоне от 0 до 9. Предположим, результатом вычисления становится индекс 3. Тогда значение 5 будет помещено в ячейку с этим индексом. Визуально процесс можно представить так: изначально массив пуст, после операции hash("apple") → 3 в ячейке с индексом 3 оказывается значение, ассоциированное с ключом "apple".

# Пример создания и использования хеш-таблицы (словаря) в Python для хранения цен на фрукты
prices = {}

# Добавление элементов
prices["apple"] = 50      # hash("apple") → условно, ячейка 3
prices["banana"] = 30     # hash("banana") → условно, ячейка 7
prices["orange"] = 40     # hash("orange") → условно, ячейка 1

print(prices)
# Вывод: {'apple': 50, 'banana': 30, 'orange': 40}

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

Индекс:  [0]    [1]         [2]  [3]        [4]  [5]  [6]  [7]          [8]  [9]
         пусто  orange→40  пусто apple→50  пусто пусто пусто banana→30  пусто пусто

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

Пример 1

Другая классическая задача — подсчёт частоты встречаемости слов в тексте. Хеш-таблица здесь используется для хранения слов в качестве ключей и соответствующих им счётчиков в качестве значений.

# Подсчет количества слов в тексте
text = "apple banana apple orange apple banana apple"
words = text.split()

word_count = {}

for word in words:
    if word in word_count:
        word_count[word] += 1  # Увеличиваем счетчик
    else:
        word_count[word] = 1   # Первая встреча слова

print(word_count)
# Вывод: {'apple': 4, 'banana': 2, 'orange': 1}

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

Пример 2

Одной из фундаментальных проблем в работе хеш-таблиц являются коллизии — ситуации, когда разные ключи в результате работы хеш-функции получают один и тот же индекс ячейки. Это аналогично тому, как двум разным людям выдали ключи от одной и той же квартиры. Например, может оказаться, что hash("apple") → 3 и hash("grape") → 3. Для разрешения коллизий существует несколько методов, наиболее распространёнными из которых являются метод цепочек и метод открытой адресации.

Метод цепочек предполагает, что каждая ячейка массива содержит не одно значение, а связный список (или динамический массив) пар «ключ–значение». При возникновении коллизии новая пара просто добавляется в список соответствующей ячейки. Таким образом, ячейка с индексом 3 будет содержать список вида [("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

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

# Решение задачи "Две суммы" с использованием хеш-таблицы
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

Алгоритмы. Структуры данных. Деревья и Двоичные деревья поиска (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].

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

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

Как настрой?

Вижу, что канал немного устал от алгоритмов, а ведь мы прошли только треть от запланированных постов. Я понимаю, что сейчас темы немного отличаются от традиционных постов о Solidity, DeFi и Web3, но в данный момент, момент активного развития вайб кодинга и нейронных сетей, как никогда важно понимать базовые вещи программирования, чтобы не только создавать сильные проекты, но и понимать, что вообще происходит на уровне кода.

Алгоритмы, структуры данных, типы данных, работа памяти - все это минимальный базис, который должен понимать любой разработчик, даже на уровне "я только пощупать". Это то, что лежит в основе практически любого языка.

В самом начале развития канала я показывал свой путь изучения Solidity, но за кадром оставался весь опыт, который я получил ранее. А ведь это несколько лет разработки на PHP и JS. Т.е. я приступал к изучению нового языка, уже имея представление как это все работает.

Сейчас, изучая нейроные сети, я столкнулся с проблемой типичного новичка. Вместо того, чтобы начать с самых основ, я решил сразу освоить PyTorch. И это было в корне не верно, так как я не знал основ.

А основой тут является знание линейной алгебры, библиотек numpy, matplotlib, scikit-learn и еще пары других... И это все нужно понимать перед тем, как приступать к PyTorch!

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

Продуктивной вам учебы и хороших выходных!

#offtop

Алгоритмы. Представление графов и обход в ширину (BFS)

Новая неделя и новый раздел в изучении алгоритмов. Мы плавно переходим к теме алгоритмов на графах и сегодня поговорим о 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

Еще немного наблюдений о вайбкодинге

Буду разбавлять посты про алгоритмы более простыми "насущными" темами.

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

Сравните два запроса:

"Создай страницу Корзина, где пользователи могут оплачивать товары."

и

"Изучи эти два файла и этот сниппет. В одном файле ты найдешь модели таблиц в базе данных и примеры запросов / ендпонитов. В другом требования к написанию кода. Требуется сделать функционал для покупки выбранных товаров на странице checkout. Твоя задача: 1/2/3/4/5. Перед выполнением задачи составь план и дождись моего подтверждения."

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

Это именно то, что и отличают оба вида вайбкодинга - инструкции с примерами. Нейросеть делает не то, что вы хотите, а что вы ей говорите сделать. Она не делает различий между "говнокодом" и "сеньором". При открытой задача (как в первом варианте), она просто берет свои случайные знания из памяти и соединяет их.

Так в одном проекте у вас может быть и код на Python, Ruby, JS и вообще смесь всего. Это вполне может работать. Вопрос в том, как...

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

Задумайтесь также и о том, что даже сеньор может давать четкие указания по редактированию своего кода и нейронка прекрасно справится с задачей, использую декораторы и стиль самого сеньора. Какой код получится в этом случае?

В свое время, да и порой сейчас, многие смеются над PHP языком и у разработчиков была такая шутка: "PHP, как самокат. Из-за того, что любой дурак может сесть на него и поехать, репутация у этой штуки так себе". Вот примерно тоже самое и с вайбкодингом.

Запрос написанный сеньором - приведет к коду уровня сеньор, запрос от школьника - приведет к соответствующему результату.

Поэтому в следующий раз, когда увидите плохой код или ужасную архитектуру, то спросите прежде, кто и как писал это код, а не вините нейронку.

#vibecoding

Анонс платформы самоучителя по Solidity

Я планировал потрать еще некоторое время, чтобы полностью доработать платформу, где будут выложены все модули курса по Solidity + модуль по Foundry + модуль с практикой аудита кода, но текущие веяния в области ограничений Телеграмма, заставляют выпускать все раньше.

Сама платформа готова на 98% - 99%, я все еще просматривая материал на предмет каких-либо недочетов, некорректного отображения, мелких багов и т.д. И, в целом, все готово к открытию.

Вчера я открыл доступ к платформе для учеников Летнего модуля 3 потока. Собираю пока обратную связь. Кстати, если вы проходили Летний и 3 модуль 2 потока, то для вас доступ будет бесплатный, как я и обещал ранее. У вас будет доступ не только к материалам на каналах Телеграм, но и на одном ресурсе все вместе, в удобном формате.

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

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

Если после первых тестов на платформе все будет хорошо, то общий доступ открою уже в следующую среду - 18 февраля.

Всем хорошего дня и продуктивной работы!

#solidity