Решил сделать небольшую задачу по книге "грокаем алгоритмы" на бинарный поиск главы 1

Решение предполагает программную реализацию и использование модуля urllib/requests/httpx/aiohttp.

Задача и её описание находятся тут:
http://176.119.156.68:8000/swagger/index.html

Это OpenAPI документация, она используется для документирования HTTP API. Сам эндпоинт, с которым надо работать из кода расположен тут:
http://176.119.156.68:8000/learnPerDay?minutesPerDay=12.5

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

Если вам зайдёт такой интерактив, то будут ещё задачи. Уже есть идеи для них)

Для тех, кто изучает data science.

Как понимать q-q plot.
https://habr.com/ru/articles/578754/

#q_q_plot

Дан неупорядоченный массив из 32 элементов. Загадан случайный элемент массива. На каждом шаге бинарного поиска выдается ответ: больше или меньше загаданное число текущего варианта из поиска. За какое количество шагов бинарный поиск гарантированно завершит свою работу и выдаст нужный элемент?

#книжный_клуб #алгоритмы

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

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

В следующей главе мы познакомимся ближе с понятиями списка, массива и сортировки. Все эти понятия крайне важны для программиста и постоянно используются. В следующую неделю мы читаем главу "2 Сортировка выбором". Опять же, читаем до следующей субботы, если есть вопросы, задаем их в чате тг (https://t.me/learnpythonforfun_chat). В конце следующей недели я сделаю небольшую выжимку по главе и подготовлю опрос.

Книжка несложная, успехов в прочтении :)

#книжный_клуб #алгоритмы

Игра по расстановке аннотаций: https://python-type-challenges.zeabur.app/

Не помню гд я это нашёл. Может и тут же. Но может быть интересно. Это миниигра, где надо расставлять аннотации типов: https://github.com/laike9m/Python-Type-Challenges?tab=readme-ov-file

Пояснение: мы имеем указатель на элемент двусвязного списка. Нам не нужно искать этот элемент внутри списка.

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

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

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

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

Книжка несложная, успехов в прочтении :)

#книжный_клуб #алгоритмы

Для тех, кто хочет глубже понять рекурсию, немного задач на подумать:
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F

Опрос по рекурсии придумать не получилось, поэтому вот вам несколько шуток про рекурсию, убедитесь, что вы их понимаете:

"Чтобы понять рекурсию, надо понять рекурсию."

"Определение рекурсии в энциклопедии: Рекурсия: см. рекурсия."

Коктейль «рекурсивный»: 30% водки, 60% коктейля «рекурсивный».

Завтра начнем следующую главу :)

#книжный_клуб #алгоритмы

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

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

разобрать_матрешку (матрешка):
    если разбирается
        внешняя_матрешка = открыть_внешнюю_матрешку()
        внутренняя_матрешка = извлечь_внутреннюю_матрешку()
        вернуть внешняя_матрешка + 
                        разобрать_матрешку (внутренняя_матрешка)
    иначе
        вернуть матрешка

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

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

#книжный_клуб #алгоритмы

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

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

В следующей главе "4. Хеш-таблицы" мы познакомимся поближе с понятиям...кхм...хеш-таблиц. Оно является значимым для понимания работы со словарями и их ограничений. Ну а словари в программировании используются повсеместно.

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

Книжка несложная, успехов в прочтении :)

#книжный_клуб #алгоритмы

Немного продвинутого материала для тех, кто хочет понять, как работает хэш-таблица в python (в интерпретаторе cpython). Собственно, ссылка на комментарий в коде:
https://github.com/python/cpython/blob/main/Objects/dictobject.c#L261

#hash

Немного про книжный клуб. Мы почти дошли до середины книги. Следующая неделя - для догоняющих. Через неделю начнем новую главу про графы.

#книжный_клуб #алгоритмы

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

В предыдущей главе мы познакомились с хэш-функциями. Они позволяют за константное время находить адрес ячейки, соответствующей определенному значение. Иными словами, любое значение трансформируется хэш-функцией в почти уникальный ключ.
Пусть есть хэш-фунция h(x), тогда могут иметь место следующие равенства:
h("cat") = 2
h("dog") = 4
h("mouse") = 1
И каждый раз, когда мы будем вызывать h к данным словам, мы будем получать те же значения. Хорошие хэш-функции должны генерировать уникальные значения. Если же хэш-функция выдает значение, которое уже встречалось, к примеру, h("bird") = 4, то такая ситуация называется коллизией. Хэш-функции широко применяются в программировании, в python на них построены словари.

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

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

Книжка несложная, успехов в прочтении :)

#книжный_клуб #алгоритмы