Алгоритмы. Big O.

Потихоньку начинаем разбирать алгоритмы в программировании, как я и писал ранее. Начнем с самых базовых для повторения и перейдем к более сложным и продвинутым. Я буду давать код алгоритмов на языке Python, так как более продвинутые решения удобнее писать именно на нем. На Solidity не все из них можно будет реализовать "без костылей", но вы сами вполне сможете поэкспериментировать с этим с помощью нейронок.

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

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

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

Скорость работы алгоритма напрямую зависит от количества обрабатываемых данных. Если в небольшом архиве из десяти дел поиск наугад займет всего несколько секунд, то в хранилище с миллионом документов такой подход потребует непозволительно много времени. Поэтому для оценки эффективности алгоритма используется понятие временной сложности, которая показывает, как количество необходимых операций растет с увеличением размера входных данных. Например, для поиска числа 9 в списке [3, 7, 1, 9, 5] методом последовательного перебора потребовалось четыре шага. Для списка из ста элементов в худшем случае потребуется сто операций. Эта прямая зависимость описывается линейной сложностью.

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

1. O(1) — постоянная сложность. Время выполнения не зависит от объема данных.

def get_first_letter(name):
    return name[0]

Операция получения первого символа строки всегда выполняется за одно действие, будь то имя «Аня» или «Александр».

2. O(n) — линейная сложность. Время выполнения растет прямо пропорционально размеру входных данных.

def find_element(arr, target):
    steps = 0
    for item in arr:
        steps += 1
        if item == target:
            return True
    return False

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

3. O(n²) — квадратичная сложность. Время выполнения пропорционально квадрату количества элементов, что характерно для алгоритмов с вложенными циклами.

def find_all_pairs(arr):
    pairs = []
    for i in arr:
        for j in arr:
            pairs.append((i, j))
    return pairs

Для массива из пяти элементов будет выполнено 25 итераций, а для тысячи — уже миллион.

4. O(log n) — логарифмическая сложность. Очень эффективный класс, где на каждом шаге объем обрабатываемых данных уменьшается вдвое. Яркий пример — бинарный поиск в отсортированном массиве.

def binary_search(sorted_arr, target):
    left, right = 0, len(sorted_arr) - 1
    steps = 0
    while left <= right:
        steps += 1
        mid = (left + right) // 2
        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Поиск среди 16 отсортированных элементов займет не более 4 шагов.

Помимо временной, важна и пространственная сложность, которая оценивает объем дополнительной памяти, требуемой алгоритмом. Например, алгоритм нахождения максимума в массиве использует фиксированный объем памяти O(1), тогда как создание полной копии списка потребует памяти O(n).

Практическое значение асимптотического анализа становится очевидным при сравнении алгоритмов. Рассмотрим задачу поиска дубликатов. Наивный подход с двойным циклом имеет сложность O(n²):

def find_duplicates_slow(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

Более разумный подход с использованием хэш-множества имеет сложность O(n):

def find_duplicates_fast(arr):
    seen = set()
    duplicates = set()
    for item in arr:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return list(duplicates)

На списке из тысячи элементов второй алгоритм окажется в сотни раз быстрее первого.

Для наглядности можно представить себе сводную таблицу сложностей. O(1) обозначает мгновенное выполнение, например доступ к элементу массива по индексу. O(log n) характерна для алгоритмов типа бинарного поиска. O(n) — для линейного прохода по данным. O(n log n) — это типичная сложность эффективных алгоритмов сортировки. O(n²) часто возникает при обработке матриц или использовании вложенных циклов. O(2ⁿ) — экстремально медленная сложность, присущая некоторым задачам полного перебора.

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

#algorithm

Алгоритмы. Рекурсия

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

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

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

Рассмотрим простейшую иллюстрацию — функцию обратного отсчёта от заданного числа до единицы. Её логика наглядно демонстрирует оба принципа.

def count_down(n):
    # Базовый случай: когда достигли 0, останавливаемся
    if n == 0:
        print("Готово!")
        return
    
    # Выводим текущее число
    print(n)
    
    # Рекурсивный шаг: вызываем функцию с n-1
    count_down(n - 1)

count_down(5)

Вывод этой программы будет последовательным:

5
4
3
2
1
Готово!

Внутри этого процесса происходит следующее: вызов count_down(5) приводит к выводу числа 5 и новому вызову count_down(4). Этот процесс вкладывается, подобно матрёшкам, пока вызов count_down(0) не достигнет базового случая, выведет "Готово!" и не начнёт возвращать управление обратно по цепочке предыдущих вызовов.

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

def factorial(n):
    # Базовый случай
    if n == 0 or n == 1:
        return 1
    
    # Рекурсивный шаг
    return n * factorial(n - 1)

print(factorial(5))  # 120

# Для значения 3

factorial(3)
│
├─ factorial(2)  ← добавляется в стек
│  │
│  ├─ factorial(1)  ← добавляется в стек
│  │  └─ возвращает 1  ← снимается со стека
│  │
│  └─ возвращает 2  ← снимается со стека
│
└─ возвращает 6  ← снимается со стека

# Стек вызовов для factorial(3):

Шаг 1: [factorial(3)]
Шаг 2: [factorial(3), factorial(2)]
Шаг 3: [factorial(3), factorial(2), factorial(1)]
Шаг 4: [factorial(3), factorial(2)]  ← factorial(1) вернул результат
Шаг 5: [factorial(3)]  ← factorial(2) вернул результат
Шаг 6: []  ← factorial(3) вернул результат

Пошаговое выполнение функции для factorial(5) раскладывается в цепочку отложенных умножений: 5 * factorial(4), затем 5 * (4 * factorial(3)), и так далее, пока вычисление не дойдёт до базового случая factorial(1), который возвращает 1. После этого цепочка начинает сворачиваться, производя последовательные умножения: 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24 и, наконец, 5 * 24 = 120.

Эта же логика применима ко множеству других задач. Например, для вычисления суммы всех чисел от 1 до n.

def sum_numbers(n):
    # Базовый случай
    if n == 0:
        return 0
    
    # Рекурсивный шаг
    return n + sum_numbers(n - 1)

print(sum_numbers(5))  # 15 (5+4+3+2+1)

Аналогично работает возведение числа в натуральную степень.

def power(base, exponent):
    # Базовый случай
    if exponent == 0:
        return 1
    
    # Рекурсивный шаг
    return base * power(base, exponent - 1)

print(power(2, 3))  # 8 (2 * 2 * 2)

Или определение длины строки без использования встроенных функций.

def string_length(s):
    # Базовый случай: пустая строка
    if s == "":
        return 0
    
    # Рекурсивный шаг: убираем первый символ и считаем остаток
    return 1 + string_length(s[1:])

print(string_length("hello"))  # 5

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

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

Рассмотрим практический вопрос: как написать рекурсивную функцию для вычисления n-го числа Фибоначчи? Последовательность Фибоначчи задаётся правилами: F(0) = 0, F(1) = 1, а для n > 1 каждое число равно сумме двух предыдущих: F(n) = F(n-1) + F(n-2). Это определение напрямую ложится на рекурсивный алгоритм.

def fibonacci(n):
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Рекурсивный шаг
    return fibonacci(n - 1) + fibonacci(n - 2)

# Примеры
print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(5))   # 5
print(fibonacci(10))  # 55

# Почему так медленно?

Посмотрим на дерево вызовов для fibonacci(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
              /    \      /    \
          fib(3) fib(2) fib(2) fib(1)
          /   \   /  \   /  \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /   \
  fib(1) fib(0)

Однако у этой наивной реализации есть серьёзный недостаток — экспоненциальная временная сложность O(2^n). Это происходит из-за колоссального количества повторных вычислений одних и тех же значений, что хорошо видно на дереве вызовов для fibonacci(5), где, например, fibonacci(3) вычисляется несколько раз. Для оптимизации применяют технику мемоизации — сохранения результатов предыдущих вычислений в кеше (словаре), чтобы не считать их заново.

def fibonacci_memo(n, memo={}):
    # Если уже вычисляли, берем из кеша
    if n in memo:
        return memo[n]
    
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Вычисляем и сохраняем результат
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Работает быстро!

С мемоизацией сложность снижается до линейной O(n), поскольку каждое значение вычисляется только один раз.

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

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

#algorithm

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

Продолжаем разбираться с базовыми алгоритмами и сегодня поговорим про Стек и Очередь. Как вы можете знать стек используется даже в 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

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

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

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

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

Массив в памяти:
[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