Архив метки: Python

Алгоритм Бойера — Мура

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

Новый набор на курсы Learn Python

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

Асинхронное программирование

Сетевые библиотеки, например 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

Перечитываю снова Pythons Innards (Yaniv Aknin).

Это — серия из нескольких статей о том, как устроен 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 г.

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

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

Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

Читать