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), поскольку каждое значение вычисляется только один раз.
Это подводит к обсуждению недостатков рекурсивного подхода в сравнении с итеративным (циклы). Главные минусы рекурсии — повышенный расход памяти из-за использования стека вызовов, риск его переполнения при большой глубине, более низкая скорость из-за накладных расходов на вызов функции, а также потенциальная сложность отладки. Итеративные решения обычно более эффективны по памяти и быстродействию для задач, которые можно просто выразить через циклы. Например, вычисление факториала с помощью цикла не требует хранения цепочки вызовов в стеке.
❤1
Тем не менее, рекурсия остаётся незаменимым инструментом для задач, имеющих естественную рекурсивную структуру данных или логики. Она идеально подходит для обхода древовидных структур (каталогов файловой системы), реализации алгоритмов "разделяй и властвуй" (быстрая сортировка, бинарный поиск) и решения таких задач, как Ханойские башни. Выбор между рекурсией и итерацией часто является компромиссом между читаемостью, простотой выражения идеи алгоритма и требованиями к производительности и ресурсам.
#algorithm
#algorithm
🔥4
Алгоритмы. Стек и Очередь
Продолжаем разбираться с базовыми алгоритмами и сегодня поговорим про Стек и Очередь. Как вы можете знать стек используется даже в Solidity, поэтому важно понимать как он работает, и что можно от него ожидать.
Примеры кода на Python получились достаточно объемными, поэтому пришлось поместить их в отдельный ресурс Telegraph.
P.S. Весь код вы можете протестировать в Google Colab или Jupyter Notebook.
В программировании для организации хранение данных с определенными правилами доступа существуют две базовые структуры — стек и очередь. Они определяют четкий порядок, в котором элементы добавляются и извлекаются, что делает их незаменимыми инструментами для решения широкого спектра задач.
Стек, или Stack, работает по принципу LIFO — Last-In, First-Out, что переводится как «последним пришел — первым ушел». Это легко представить на примере стопки книг: новую книгу всегда кладут сверху, и чтобы взять нужную, также снимают сначала верхнюю. Самую нижнюю книгу можно получить, только убрав все лежащие выше. Основные операции со стеком включают push для добавления элемента на вершину, pop для его удаления, peek или top для просмотра вершины без удаления и isEmpty для проверки на пустоту. Визуально стек можно изобразить следующим образом:
После операции 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.
Продолжаем разбираться с базовыми алгоритмами и сегодня поговорим про Стек и Очередь. Как вы можете знать стек используется даже в 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
Пример 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
👍6
Начинаю бета-тест моего проекта
Если вы помните, в прошлом году я активно занимался сбором аудиторских отчетов, извлечением из них описаний уязвимостей и формированием базы данных для работы с нейронными сетями. На днях эта работа была завершена, и я перехожу к этапу закрытого бета-тестирования. В связи с этим хотел бы обратиться к вам с просьбой помочь в «прогоне» системы.
Сначала я вкратце расскажу о проекте, а в конце дам инвайты для регистрации и поясню, что именно нужно проверить.
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
Если вы помните, в прошлом году я активно занимался сбором аудиторских отчетов, извлечением из них описаний уязвимостей и формированием базы данных для работы с нейронными сетями. На днях эта работа была завершена, и я перехожу к этапу закрытого бета-тестирования. В связи с этим хотел бы обратиться к вам с просьбой помочь в «прогоне» системы.
Сначала я вкратце расскажу о проекте, а в конце дам инвайты для регистрации и поясню, что именно нужно проверить.
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
🔥15❤4
Еще инвайты
Добавил еще 10 инвайтов для теста моего проекта. Если кто хотел, но не успел - это ваш шанс!
Инвайт тот же -
Буду рад отзывам!
#hornetmcp
Добавил еще 10 инвайтов для теста моего проекта. Если кто хотел, но не успел - это ваш шанс!
Инвайт тот же -
soliditysetБуду рад отзывам!
#hornetmcp
❤2🔥2🎉2
Алгоритмы. Пузырьковая сортировка
Продолжаем наше изучение алгоритмов и сегодня начнем разбирать пузырьковой сортировки, один из наиболее наглядных методов упорядочивания данных. Идея сортировки в целом подобна приведению в порядок перепутанной колоды карт, когда требуется расположить элементы от меньшего к большему или наоборот. В программировании эта задача возникает постоянно: будь то числа, строки или другие данные, требующие определённой последовательности. Например, изначальный список
Название "пузырьковая" отражает суть процесса: более лёгкие элементы, подобно пузырькам воздуха в воде, постепенно всплывают к началу списка, в то время как тяжёлые опускаются в конец. Алгоритм построен на простом принципе: последовательно сравниваются соседние элементы, и если они расположены в неправильном порядке, происходит их обмен. Эти действия повторяются до тех пор, пока весь массив не будет упорядочен.
Для лучшего понимания разберём визуальный пример сортировки списка
Теперь перейдём к программной реализации. Код функции пузырьковой сортировки на Python выглядит следующим образом:
Разберём каждую часть. Функция
Внутренний цикл
Внутри внутреннего цикла условие
Для демонстрации работы приведём полный пример:
Продолжаем наше изучение алгоритмов и сегодня начнем разбирать пузырьковой сортировки, один из наиболее наглядных методов упорядочивания данных. Идея сортировки в целом подобна приведению в порядок перепутанной колоды карт, когда требуется расположить элементы от меньшего к большему или наоборот. В программировании эта задача возникает постоянно: будь то числа, строки или другие данные, требующие определённой последовательности. Например, изначальный список
[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. В конце функция возвращает отсортированный список.Для демонстрации работы приведём полный пример:
🐳1
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
👍3🐳1
Алгоритмы. Быстрая сортировка
Быстрая сортировка представляет собой эффективный алгоритм, основанный на стратегии «разделяй и властвуй». Представьте себе задачу упорядочить книги на полке по высоте. Вместо того чтобы последовательно сравнивать каждую книгу с каждой, что потребовало бы значительного времени, можно выбрать одну книгу среднего размера в качестве условного эталона. Все книги меньше этого эталона помещаются слева, а все больше — справа. Затем эта же процедура рекурсивно применяется к каждой из образовавшихся групп. Именно эта идея лежит в основе быстрой сортировки.
Алгоритм работает, разделяя исходный массив данных на части относительно специально выбранного элемента, который называется опорным или пивотом. Стратегия «разделяй и властвуй» подразумевает три этапа: сначала большую задачу разбивают на меньшие независимые подзадачи, затем каждую из них решают, и наконец, полученные решения объединяют в окончательный результат. Этот процесс можно представить как преобразование большого беспорядка в несколько маленьких, которые затем приводятся в порядок.
Рассмотрим работу алгоритма пошагово на примере массива
Второй шаг — разделение массива. Все элементы, меньшие опорного, помещаются в одну группу, равные ему — в другую, а большие — в третью.
Наглядно это можно изобразить так:
Третий шаг — рекурсивное применение того же алгоритма к левой и правой частям, так как группа равных опорному элементу уже считается отсортированной. Для левой части
Четвертый шаг — объединение результатов. После того как все рекурсивные вызовы завершены, отсортированные части собираются вместе. Сборка происходит снизу вверх: отсортированные подмассивы меньших размеров объединяются с опорными элементами.
Полное дерево рекурсии для данного примера выглядит следующим образом:
Сборка снизу вверх:
Реализация этого алгоритма на Python демонстрирует его лаконичность. Ключевая часть — рекурсивное разделение и объединение массивов.
Быстрая сортировка представляет собой эффективный алгоритм, основанный на стратегии «разделяй и властвуй». Представьте себе задачу упорядочить книги на полке по высоте. Вместо того чтобы последовательно сравнивать каждую книгу с каждой, что потребовало бы значительного времени, можно выбрать одну книгу среднего размера в качестве условного эталона. Все книги меньше этого эталона помещаются слева, а все больше — справа. Затем эта же процедура рекурсивно применяется к каждой из образовавшихся групп. Именно эта идея лежит в основе быстрой сортировки.
Алгоритм работает, разделяя исходный массив данных на части относительно специально выбранного элемента, который называется опорным или пивотом. Стратегия «разделяй и властвуй» подразумевает три этапа: сначала большую задачу разбивают на меньшие независимые подзадачи, затем каждую из них решают, и наконец, полученные решения объединяют в окончательный результат. Этот процесс можно представить как преобразование большого беспорядка в несколько маленьких, которые затем приводятся в порядок.
Рассмотрим работу алгоритма пошагово на примере массива
[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
👍2🐳1
Пара слов о моем проекте
Нельзя недооценивать силу ранних запусков, бета тестирования и обратной связи. В наши дни достаточно легко создать быстро проект, купить домен и выпустить его в мир, однако все нужно тратить время на его "обкатку". И я тому достаточно показательный пример.
Когда ты создаешь сайт / приложение / контракт, то явно понимаешь, как его нужно использовать, что вводить и куда нажимать (особенно, если важен порядок действий). Но все меняется когда ты даешь доступ пользователям.
Я тоже явно представлял, что нужно вводить и как делать запросы, чтобы получать результаты. Но то, что у меня в голове было логически обоснованным, оказалось совершенно не понятно с внешнего взгляда.
Прежде всего, была не достаточно ясно подчеркнута идея самого проекта. Хоть и были несколько надписей и на главной странице, и внутри сайта, что это не анализатор, а поиск по базе данных, многие упорно пытались получить результаты анализа своего проекта или контракта.
Функция чата определенно сбивала с толку. Мы все привыкли, что можно ввести какое-нибудь сообщение, chatGPT поймет намеренье и выдаст нужную (или около-нужную информацию). Тут было также. Не смотря на то, что это MCP/API сервер предназначенный для использования вместе с нейронками (чтобы они сами формировали запроси и делали анализ), многие также не доходили до установки этого сервера, заканчивая свой путь на первом запросе чата.
Кроме того, оказалось, что многие также не понимают работу семантического поиска.
В итоге оказалось, что UI/UX не приспособлен для передачи идеи проекта и его нужно менять, чем я потихоньку и занимаюсь.
Прежде всего, была обновлена главная страница, которая теперь четко говорит назначение проекта. Опять же на мой взгляд. Буду тестировать сообщение. Если будут сомнения - буду снова экспериментировать.
Также обновлена форма для чата. Вместо одного поля, теперь два: одно для запроса, другое для функций. Оба поля получили более описательные placeholder.
В планах, сделать более просто навигацию (хотя думал, что разбитие по вкладкам будет удачным решением...), а также добавить пару других режимов в чате, чтобы модель llm могла корректировать запросы пользователей, делая их более подходящими для релевантного поиска.
В общем, всем большое спасибо за обратную связь!
#hornetmcp
Нельзя недооценивать силу ранних запусков, бета тестирования и обратной связи. В наши дни достаточно легко создать быстро проект, купить домен и выпустить его в мир, однако все нужно тратить время на его "обкатку". И я тому достаточно показательный пример.
Когда ты создаешь сайт / приложение / контракт, то явно понимаешь, как его нужно использовать, что вводить и куда нажимать (особенно, если важен порядок действий). Но все меняется когда ты даешь доступ пользователям.
Я тоже явно представлял, что нужно вводить и как делать запросы, чтобы получать результаты. Но то, что у меня в голове было логически обоснованным, оказалось совершенно не понятно с внешнего взгляда.
Прежде всего, была не достаточно ясно подчеркнута идея самого проекта. Хоть и были несколько надписей и на главной странице, и внутри сайта, что это не анализатор, а поиск по базе данных, многие упорно пытались получить результаты анализа своего проекта или контракта.
Функция чата определенно сбивала с толку. Мы все привыкли, что можно ввести какое-нибудь сообщение, chatGPT поймет намеренье и выдаст нужную (или около-нужную информацию). Тут было также. Не смотря на то, что это MCP/API сервер предназначенный для использования вместе с нейронками (чтобы они сами формировали запроси и делали анализ), многие также не доходили до установки этого сервера, заканчивая свой путь на первом запросе чата.
Кроме того, оказалось, что многие также не понимают работу семантического поиска.
В итоге оказалось, что UI/UX не приспособлен для передачи идеи проекта и его нужно менять, чем я потихоньку и занимаюсь.
Прежде всего, была обновлена главная страница, которая теперь четко говорит назначение проекта. Опять же на мой взгляд. Буду тестировать сообщение. Если будут сомнения - буду снова экспериментировать.
Также обновлена форма для чата. Вместо одного поля, теперь два: одно для запроса, другое для функций. Оба поля получили более описательные placeholder.
В планах, сделать более просто навигацию (хотя думал, что разбитие по вкладкам будет удачным решением...), а также добавить пару других режимов в чате, чтобы модель llm могла корректировать запросы пользователей, делая их более подходящими для релевантного поиска.
В общем, всем большое спасибо за обратную связь!
#hornetmcp
❤3🔥3