Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.
Читать
Архив метки: Python
Новый набор на курсы Learn Python
Асинхронное программирование
Сетевые библиотеки, например twisted, tornado, gevent, tulip — при кажущейся разнице в подходах имеют очень похожее ядро, называемое reactor, io loop, hub, event loop соответственно. Именно созданием этого ядра с нуля своими руками мы и займемся.
Цель курса: дать знания о том, как происходит работа с сетевыми подключениями (сокетами) на примере создания собственной библиотеки.
Требования к участникам: знание Python на достаточно приличном уровне. Введения в программирование не будет, с другой стороны создаваемый код не потребует чего-то сложного. Все сложности будут в работе с сетью а не в создании хитрых питоновских конструкций.
Потребуется Python 3.3. Хотя код мало зависит от версии языка, всё же в Python 3.3 появились некоторые удобные штуки которыми мы воспользуемся.
Операционная система: Linux, MacOS X или FreeBSD на выбор. Если есть сильное желание писать на Windows — тоже можно.
Коротко о чём будут занятия:
- Написание примитивного клиент-серверного кода на потоках.
- Объяснение почему производительные программы такой подход не используют. Нужно делать на epoll или kqueue, в крайнем случае select. Создание своего event loop. Сначала для обработки отложенных событий. Что это такое и какой должен быть интерфейс — расскажу по ходу дела.
- Описание того, как работает select/epoll/kqueue. Добавляем к event loop работу с TCP сокетами, основанную на обратных вызовах. Правильная обработка ошибок.
- Добавляем понятия транспорта-протокола.
- Строим поверх этого удобный интерфейс для пользовательского кода. На yeild from или greenlets — по желанию.
- Окончательный разбор результатов, ответы на возникшие вопросы.
Получившийся код в целом будет в основе следовать дизайну tulip в сильно упрощённом виде.
Курс состоит из шести занятий. Лектор: Андрей Светлов
Каждое занятие длится 2 часа.
Стоимость занятия: 300 грн.
Создание эффективных web-приложений
В 2013м году никого не удивишь веб-приложением, построенным при помощи Django, Pyramid или даже Flask. Однако куда сложнее удивить грамотным и эффективным web-приложением, способным одинаково успешно справлятся с нагрузкой реального мира и оставаться простым и легким для разработки.
Поэтому главной целью курса будет показать, как создавать высоконагруженные приложения, какие инструменты помогут в этом, при чем при здесь тестирование, профайлинг, деплоймент и изначально правильно выбранная архитектура и откуда приходят основные ошибки.
На протяжении всего курса мы будем создавать веб-приложение, ориентированное на работу на ARM микро-компьютере Raspberry PI.
Требования к участникам: опыт в создании сайтов или проектов при помощи Python и популярных фреймворков. Учить создавать сайты с нуля не буду, буду помогать перейти на новый уровень и избегать довольно популярных и тем не менее назойливых ошибок.
Краткое содержания курса:
- Архитектура высоконагруженного приложения, разделение проекта на бэкенд и фронтэнд, удаленное выполнение задач
- Оптимизация архитектуры и оптимизация кода, что идет за чем
- Тестирование как двигатель разработки, а не наоборот
- Непрерывная интеграция и непрерывный деплоймент, сравнение мест для развертки проектов
- Откуда берутся основные ошибки веб-приложений, зачем мы наступаем на одни и те же грабли
Курс состоит из шести занятий. Лектор: Игорь Давыденко
Каждое занятие длится 2 часа с перерывом в 15 минут.
Стоимость занятия: 200 грн, стоимость полного курса: 1000 грн.
Оптимизация Python кода
Чтобы делать высокоэффективный код нужно уметь пользоваться профайлером, читать байткод, выполнять алгоритмическую оптимизацию и писать Python C Extensions если алгоритмически выжать уже ничего не получается.
Всем этим мы и займемся.
Требования к участникам: уметь программировать на Python и C. Последнее очень желательно хотя бы на уровне остаточных знаний из институтского курса — половина рассматриваемого кода будет на С.
Python 3.3, операционная система любая.
Краткое со
держание курса:
- Профилирование через cProfile и timeit, анализ измеренных результатов. Рассматриваем из чего состоит функция с точки зрения Python и добираемся до байткода. Несколько простых вариантов оптимизации.
- Создаём простейший модуль Python C Extension.
- Учимся делать Python классы на C.
- Теперь пишем на Cython и радуемся как легко всё получается. В нагрузку ctypes.
- Показываю, как устроена виртуальная CPython машина изнутри. Интерпретаторы, потоки, стек. GIL. Как PyEval_EvalFrameEx исполняет байткод.
Курс состоит из пяти занятий. Лектор: Андрей Светлов.
Каждое занятие длится 2 часа.
Стоимость занятия: 300 грн.
UPD. Для тех кто ещё не понял: online версии не будет. Ни в каком виде.
Автор: Andrew Svetlov
Задача о путешествии шахматного коня
Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года).
Pythons Innards
Это — серия из нескольких статей о том, как устроен CPython изнутри.
- Интерпретатор байткода
- Что из себя представляет этот самый байткод
- Что такое стек в понятии CPython, и как оно работает
- Как устроены дескрипторы, слоты и классы на нижнем уровне
- Пространства имен (namespaces)
Для «простых программистов, работающих работу» — наверное, ничего интересного.
Тем, кто желает разобраться в Питоне «до последнего байта» — очень рекомендую.
Вдобавок очень хочу посоветовать Ely Bendersky с его Python Internals. Эта серия статей тоже посвящена «внутреннему устройству» и прекрасно сочетается с тестами Yaniv Aknin.
- Как создаётся объект (в деталях)
- Что такое class и чем отличается от type
- Как именно происходит вызов callable
- И т.д. (symbol tables, например)
На самом деле подобного рода информации очень немного. Документация хорошо описывает CPython C API но не рассказывает о деталях, о том как это всё работает.
У меня до C кода дело доходило разве до обсуждения реализации GIL насколько я помню.
Если есть еще интересные статьи по внутреннему устройству — пишите в комментариях, я добавлю сюда. Наверняка что-то запамятовал, но в целом тема раскрыта очень скудно.
Так что если хотите узнать «как оно работает на самом деле» — читайте статьи по ссылкам.
UPD.
По устройству типов данных:
Строки
Целые числа
Списки
Словари (для версий Python <3.3)Лекция Larry Hastings (release manager для Python 3.4, между прочим) с US PyCon 2012 на рассматриваемую тему.
Автор: Andrew Svetlov
Поиск первого вхождение подстроки. Решение в лоб.
Алгоритм Кнута-Морриса-Пратта (КМП)
Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.
Он относится к «правильным» подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.
Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.



