Алгоритмы. Стек и Очередь

Продолжаем разбираться с базовыми алгоритмами и сегодня поговорим про Стек и Очередь. Как вы можете знать стек используется даже в Solidity, поэтому важно понимать как он работает, и что можно от него ожидать.

Примеры кода на Python получились достаточно объемными, поэтому пришлось поместить их в отдельный ресурс Telegraph.

P.S. Весь код вы можете протестировать в Google Colab или Jupyter Notebook.

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

Стек, или Stack, работает по принципу LIFO — Last-In, First-Out, что переводится как «последним пришел — первым ушел». Это легко представить на примере стопки книг: новую книгу всегда кладут сверху, и чтобы взять нужную, также снимают сначала верхнюю. Самую нижнюю книгу можно получить, только убрав все лежащие выше. Основные операции со стеком включают push для добавления элемента на вершину, pop для его удаления, peek или top для просмотра вершины без удаления и isEmpty для проверки на пустоту. Визуально стек можно изобразить следующим образом:

┌─────────┐
│    C    │ ← Вершина (Top) - здесь происходят операции
├─────────┤
│    B    │
├─────────┤
│    A    │
└─────────┘

После операции pop() будет удален элемент C, а после push(D) на вершине окажется D. На практике это выглядит так, как показано в примере реализации стека на Python с использованием списка.

Пример 1

Вывод программы наглядно демонстрирует порядок операций:

Пример 2

Стек находит применение во множестве реальных задач. Например, история браузера использует стек для реализации кнопки «Назад»: каждый новый URL помещается в стек, а нажатие кнопки извлекает последний. Текстовые редакторы хранят историю изменений в стеке для функции отмены действий (Ctrl+Z). Компиляторы и интерпретаторы проверяют сбалансированность скобок в коде, используя стек для отслеживания открывающих символов. Наконец, сам механизм вызова функций в программах управляется стеком вызовов, где сохраняются контексты выполнения. Практическим примером может служить функция проверки корректности расстановки скобок.

Пример 3

В отличие от стека, очередь, или Queue, работает по принципу FIFO — First-In, First-Out, то есть «первым пришел — первым ушел». Это аналогично очереди в магазине: первый вставший в очередь покупатель первым же и обслуживается, а новые люди присоединяются к концу. Основные операции — enqueue для добавления элемента в конец, dequeue для удаления из начала, front для просмотра первого элемента и isEmpty для проверки. Визуализация очереди выглядит так:

Пример 4

При dequeue() будет удален элемент A, а после enqueue(E) в конец добавится E. В Python для эффективной реализации очереди используется структура deque из модуля collections.

Пример 5

Вывод этой программы отражает принцип FIFO:

Пример 6

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

Пример 7

Сравнивая стек и очередь, можно выделить их ключевые различия. Стек следует принципу LIFO, подобно стопке книг, где добавление и удаление происходят с одного конца (вершины). Очередь же работает по принципу FIFO, как очередь в магазине, где добавление идет в конец, а удаление — из начала. В Python стек эффективно реализуется через список (list), а для очереди предпочтительнее использовать deque из модуля collections.

Интересной задачей является реализация очереди с помощью двух стеков. Классическое решение использует один стек для добавления элементов (enqueue), а другой — для удаления (dequeue). Когда требуется удалить элемент, но второй стек пуст, все элементы перекладываются из первого стека во второй, в результате чего порядок инвертируется и первый добавленный элемент оказывается на вершине второго стека, готовый к извлечению.

Пример 8

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

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

Пример 9

Функция отмены действий в редакторах также полагается на стек для хранения состояний.

Пример 10

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

Пример 11

Проверка корректности HTML-тегов — задача, где стек отслеживает вложенность открывающих и закрывающих элементов.

Пример 12

Для реализации очереди в Python оптимально использовать класс deque из модуля collections. Это двусторонняя очередь, которая обеспечивает константную сложность O(1) для операций добавления и удаления с обоих концов, в отличие от списка, где удаление из начала (pop(0)) имеет линейную сложность O(n). Полноценная реализация очереди на deque включает все основные операции.

Пример 13

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

Пример 14

С точки зрения сложности операций, стек на основе списка Python обеспечивает O(1) для push, pop и peek, так же как и проверка на пустоту. Очередь на основе deque также гарантирует O(1) для enqueue, dequeue, front и isEmpty. Важно подчеркнуть, что использование обычного списка для очереди неэффективно из-за линейной сложности операции pop(0), что делает deque предпочтительным выбором.

В заключение, стек и очередь — это фундаментальные структуры данных, каждая со своим строгим принципом доступа: LIFO для стека, подобно стопке тарелок, и FIFO для очереди, как очередь людей. Их понимание критически важно для изучения алгоритмов и системного программирования, поскольку они лежат в основе множества механизмов — от управления памятью и планирования процессов до синтаксического анализа и работы с историей. Ключевые моменты для запоминания: стек оперирует с одним концом, очередь — с двумя; в Python для стека используется list, для очереди — deque; обе структуры обеспечивают высокую эффективность основных операций.

#algorithm

Начинаю бета-тест моего проекта

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

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

HornetMCP — это MCP/API-сервер, который реализует поиск уязвимостей, схожих с запросом пользователя. Однако, в отличие от стандартных API (таких, как Solodit), работающих на основе ключевых слов и тегов, здесь используется векторное сходство данных.

Как это работает на практике?

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

2. Запрос преобразуется в эмбеддинги — то есть переводится в векторное пространство.

3. Полученные векторы сравниваются с векторами (эмбеддингами), хранящимися в базе данных.

4. Система выбирает 5–10 наиболее похожих векторов и возвращает пользователю соответствующие отчеты, из которых эти векторы были получены.

5. В случае использования через MCP (например, с Claude) нейросеть самостоятельно проводит дальнейший анализ функции и выдает результат. При работе через API пользователь получает непосредственно отчеты. Также доступно тестовое чат-окно для разового запроса, который анализирует найденные отчеты (промт пока в доработке). Кроме того, чат использует бесплатную модель DeepSeek R1T2 Chimera - поэтому работа чуть медленнее обычного чата и немного хуже ответы, чем в Claude или ChatGPT.

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

Почему я решил создать этот проект? Было несколько причин. Во-первых, я хотел глубже погрузиться в работу с нейросетями и RAG. Во-вторых, в ходе аудита смарт-контрактов я регулярно сталкивался с вопросами вроде: «Были ли уже подобные уязвимости?», «Не упускаю ли я важный паттерн?», «Есть ли скрытые проблемы?» — иными словами, мне хотелось получать больше идей и гипотез для проверки. Solodit, например, предлагает хороший фильтр, но он работает по ключевым словам и тегам. Вставить функцию и получить релевантные отчеты на основе семантики там нельзя. А векторный поиск как раз решает эту задачу.

Сейчас я ищу участников канала, которые в своей работе используют нейросети и MCP-серверы — для разработки контрактов или для аудита. Необходимо протестировать работу проекта, его стабильность и качество векторного поиска отчетов. В идеале — если вы будете использовать проект вместе с Claude или другой LLM, поддерживающей MCP: это обеспечит максимальную эффективность.

Для регистрации потребуется подтверждение email (я параллельно тестирую сервис Resend для отправки писем). Также нужно будет сформировать APIKey для отправки запросов через MCP/API.

Сайт проекта — https://hornetmcp.com/

Инвайт — solidityset

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

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

Спасибо всем, кто примет участие в тестировании!

#hornetmcp

Еще инвайты

Добавил еще 10 инвайтов для теста моего проекта. Если кто хотел, но не успел - это ваш шанс!

Инвайт тот же - solidityset

Буду рад отзывам!

#hornetmcp

Алгоритмы. Пузырьковая сортировка

Продолжаем наше изучение алгоритмов и сегодня начнем разбирать пузырьковой сортировки, один из наиболее наглядных методов упорядочивания данных. Идея сортировки в целом подобна приведению в порядок перепутанной колоды карт, когда требуется расположить элементы от меньшего к большему или наоборот. В программировании эта задача возникает постоянно: будь то числа, строки или другие данные, требующие определённой последовательности. Например, изначальный список [64, 34, 25, 12, 22] после сортировки превращается в [12, 22, 25, 34, 64].

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

Для лучшего понимания разберём визуальный пример сортировки списка [5, 3, 8, 4, 2] по возрастанию. В первом проходе сравниваются 5 и 3 — поскольку 5 больше 3, они меняются местами, и список становится [3, 5, 8, 4, 2]. Далее 5 и 8 остаются на своих местах, так как 5 меньше 8. Затем 8 и 4 обмениваются, получается [3, 5, 4, 8, 2]. Наконец, 8 и 2 также меняются, и результат первого прохода — [3, 5, 4, 2, 8]. Обратите внимание, что самое большое число 8 оказалось в конце, заняв свою окончательную позицию. Второй проход перемещает 5 на предпоследнее место: после сравнений и обменов список принимает вид [3, 4, 2, 5, 8]. Третий проход ставит на место 4: [3, 2, 4, 5, 8]. Четвёртый проход завершает сортировку, обменяв 3 и 2, и итоговый результат — [2, 3, 4, 5, 8].

Теперь перейдём к программной реализации. Код функции пузырьковой сортировки на Python выглядит следующим образом:

def bubble_sort(arr):
    """Пузырьковая сортировка списка."""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

Разберём каждую часть. Функция bubble_sort принимает список arr. Переменная n хранит его длину. Внешний цикл for i in range(n) определяет количество полных проходов по списку. Внутри него устанавливается флаг swapped = False, который отслеживает, были ли совершены обмены во время текущего прохода. Это важная оптимизация: если обменов не произошло, список уже отсортирован, и дальнейшие проходы не нужны.

Внутренний цикл for j in range(0, n - i - 1) отвечает за попарное сравнение соседних элементов. Выражение n - i - 1 ограничивает диапазон, потому что после каждого прохода самый крупный элемент "всплывает" в конец, и проверять его уже не требуется. Например, для списка из пяти элементов при первом проходе (i = 0) будут сравниваться пары с индексами от 0 до 3, при втором (i = 1) — от 0 до 2, и так далее.

Внутри внутреннего цикла условие if arr[j] > arr[j + 1]: проверяет, стоит ли текущий элемент правее, чем следующий. Если да, то с помощью конструкции arr[j], arr[j + 1] = arr[j + 1], arr[j] элементы меняются местами, а флаг swapped устанавливается в True. После завершения внутреннего цикла проверяется значение флага: если он остался False, что означает отсутствие обменов, внешний цикл прерывается оператором break. В конце функция возвращает отсортированный список.

Для демонстрации работы приведём полный пример:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

# Пример 1: Обычная сортировка
data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data1.copy()))
# Результат: [11, 12, 22, 25, 34, 64, 90]

# Пример 2: Уже отсортированный список
data2 = [1, 2, 3, 4, 5]
print(bubble_sort(data2.copy()))
# Результат: [1, 2, 3, 4, 5]

# Пример 3: Обратный порядок
data3 = [5, 4, 3, 2, 1]
print(bubble_sort(data3.copy()))
# Результат: [1, 2, 3, 4, 5]

Чтобы лучше проследить за ходом алгоритма, можно использовать визуализированную версию:

def bubble_sort_visualized(arr):
    n = len(arr)
    print(f"Начальный список: {arr}")
    print()
    
    for i in range(n):
        print(f"=== Проход {i + 1} ===")
        swapped = False
        
        for j in range(0, n - i - 1):
            print(f"Сравниваем {arr[j]} и {arr[j + 1]}", end=" ")
            
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                print(f"→ Меняем! Теперь: {arr}")
            else:
                print(f"→ Оставляем")
        
        if not swapped:
            print("Обменов не было, список отсортирован!")
            break
        print()
    
    print(f"\nИтоговый список: {arr}")
    return arr

data = [5, 2, 8, 1, 9]
bubble_sort_visualized(data)

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

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

def bubble_sort_descending(arr):
    """Пузырьковая сортировка в порядке УБЫВАНИЯ."""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_descending(data1.copy()))
# Результат: [90, 64, 34, 25, 22, 12, 11]

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

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

#algorithm

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

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

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

Рассмотрим работу алгоритма пошагово на примере массива [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