• Решаем задачи без самобалансирующихся деревьев в Python

      Многие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.

      Что касается Python, то в нём есть почти всё.

      • Динамический массив — встроенный тип list. Он же поддерживает и стековые операции: .append() и .pop().
      • Хэш-таблица — встроенные типы set и dict, а также неизменяемый брат сета frozenset.
      • Куча — list со специальными операциями вставки и удаления, реализованными в модуле heapq.
      • Двусторонняя очередь — это описанный в модуле collections тип deque.

      Но вот самобалансирующегося дерева поиска, как такового, в стандартной библиотеке нет. А жаль!

      В этой статье я разберу несколько алгоритмических задачек, подразумевающих решение с помощью двоичного дерева, и покажу, чем в разных ситуациях его можно заменить в Питоне.
      Покажите мне картинки и код!
    • Балуемся с унарными операторами в Python

        >>> +--+_+-+_++_+--_+_-_+-+-+-___++++_+-_-+++_+-+_--++--_
        'ПРИВЕТ, ХАБР!'

        Что это было? Да, вы не ошиблись — это азбука Морзе с плюсиками вместо точек прямо в синтаксисе Питона!

        Если вы не понимаете, как это работает, или просто не прочь освежить свои знания в День Советской армии (и Военно-морского флота!), добро пожаловать под кат.
        Читать дальше →
      • Руководство по созданию расширений для Jinja2

        • Tutorial
        Jinja2 — Python-библиотека для рендеринга шаблонов, являющаяся де-факто стандартом при написании веб-приложений на Flask и довольно популярной альтернативой встроенной системе шаблонов Django. Хотя и будучи сильно привязана к языку, Jinja2 позиционирует себя как инструмент для дизайнеров и верстальщиков, упрощающий вёрстку и отделяющий её от разработки, и пытающийся по мере возможностей изолировать не-разработчиков от Python. Вёрстка, впрочем, не единственное возможное её применение; например, в своей работе я использую шаблоны Jinja2 для генерации SQL-запросов.

        Jinja2 расширяема, и многие возможности (например, интернационализация и управление циклами) реализованы именно как расширения. Однако, документация по написанию расширений, как мне кажется, несколько неполна; от примера несложного (но тщательно прокомментированного) расширения она перескакивает сразу к описанию API некоторых классов Jinja2, которое довольно трудно читать подряд. В этой статье я попытаюсь исправить это упущение и создать в голове читателя полную и ясную картину того, как работает Jinja2, как устроены её расширения и как с помощью расширений модифицировать разные этапы обработки шаблонов.
        Читать дальше →
      • Пишем диалоговые Telegram-боты на Питоне

        • Tutorial
        Думаю, всем здесь в той или иной мере известен мессенджер Telegram. Создатель заявляет, что это самый безопасный мессенджер с убойным алгоритмом шифрования собственной разработки, но нас, разработчиков, конечно же, куда сильнее интересует другое. Боты!

        Тема эта, конечно, не раз поднималась на Хабре: ботов писали на Python с tornado, Node.js, Ruby со специальным гемом, Ruby on Rails, C#, C# с WCF и даже PHP; ботов писали для RSS-каналов, мониторинга сайтов, удалённого включения компьютера и, вероятно, для многого, многого другого.

        И всё же я возьму на себя смелость изъездить эту тему ещё раз и вдобавок к этому показать немного магии Питона. Мы будем писать фреймворк™ для удобного написания нетривиальных диалоговых ботов на основе пакета python-telegram-bot.
        Читать дальше →
      • Пишем изящный парсер на Питоне

        • Tutorial
        В C++17 (нет-нет, Питон скоро будет, вы правильно зашли!) появляется новый синтаксис для оператора if, позволяющий объявлять переменные прямо в заголовке блока. Это довольно удобно, поскольку конструкции вида

        Foo foo = make_foo();
        if(foo.is_nice()) {
            // do work with foo
        }
        // never use foo again
        // foo gets deleted
        

        довольно общеупотребительны. Код выше лёгким движением руки программиста (и тяжёлым движением руки комитета по стандартизации) превращается в:

        if(Foo foo = make_foo(); foo.is_nice()) {
            // do work with foo
        }  // foo gets deleted
        // never use foo again (well, you can't anyway)

        Стало чуть-чуть лучше, хотя всё ещё не выглядит идеально. В Python нет и такого, но если вы ненавидите if в Python-коде так же сильно, как я, и хотите научиться быстро писать простые парсеры, то добро пожаловать под кат. В этой статье мы попытаемся написать короткий и изящный парсер для JSON на Python 2 (без каких-либо дополнительных модулей, конечно же).
        Читать дальше →
      • Пишем сериализатор для сетевой игры на C++11

          Написать этот пост меня вдохновила замечательная статья в блоге Gaffer on Games «Reading and Writing Packets» и неуёмная тяга автоматизировать всё и вся (особенно написание кода на C++!).

          Начнём с постановки задачи. Мы пишем сетевую игру (и сразу MMORPG, конечно же!), и независимо от архитектуры у нас возникает необходимость постоянно посылать и получать данные по сети. У нас, скорее всего, возникнет необходимость посылать несколько разных типов пакетов (действия игроков, обновления игрового мира, просто-напросто аутентификация, в конце концов!), и для каждого у нас должна быть функция чтения и функция записи. Казалось бы, не вопрос сесть и написать спокойно эти две функции и не нервничать, однако у нас сразу же возникает ряд проблем.

          • Выбор формата. Если бы мы писали простенькую игру на JavaScript, нас бы устроил JSON или любой его самописный родственник. Но мы пишем серьёзную многопользовательскую игру, требовательную к трафику; мы не можем позволить себе отправлять ~16 байт на float вместо четырёх. Значит, нам нужен «сырой» двоичный формат. Однако, двоичные данные усложняют отладку; было бы здорово, если бы мы могли менять формат в любой момент, не переписывая целиком все наши функции чтения/записи.
          • Проблемы безопасности. Первое правило сетевой игры: не доверяй данным, присланным клиентом! Функция чтения должна уметь оборваться в любой момент и вернуть false, если что-то пошло не так. При этом использовать исключения считается неважной идеей, поскольку они слишком медленные. Мамкин хакер пусть и не сломает ваш сервер, но вполне может ощутимо замедлить его беспрерывными эксепшнами. Но вручную писать код, состоящий из if'ов и return'ов, неприятно и неэстетично.
          • Повторяющийся код. Функции чтения и записи похожи, да не совсем. Необходимость изменить структуру пакета приводит к необходимости поменять две функции, что рано или поздно приведёт к тому, что вы забудете поменять одну из них или поменяете их по-разному, что приведёт к трудно отлавливаемым багам. Как справедливо замечает Gaffer on Games, it is really bloody annoying to maintain separate read and write functions.

          Всех интересующихся тем, как Бендер выполнил своё обещание и при этом решил обозначенные проблемы, прошу под кат.
          Читать дальше →
        • C++11 variadic templates и длинная арифметика на этапе компиляции

          • Tutorial
          За тридцать лет, прошедших с момента его появления в недрах Bell Labs, C++ проделал долгий путь, пройдя от «усовершенствованного C» до одного из самых популярных и выразительных компилируемых языков. Особенно много, на авторский сугубо личный взгляд, дал C++ новый стандарт C++11, стремительно обретающий поддержку компиляторов. В этой статье мы постараемся «пощупать руками» одну из его мощнейших фич — шаблоны с переменным числом аргументов (variadic templates).

          Разработчики, знакомые с книжками Александреску, вероятно, помнят концепцию списка типов. В старом-добром C++03 при необходимости использовать заранее неизвестное число аргументов шаблона предлагалось создать такой список и потом хитрым хаком его использовать. Этим способом реализовывались кортежи (ныне std::tuple) и проч. и проч. А сама глава про списки типов ясно давала понять, что на шаблонах C++ можно проводить практически любые вычисления (заниматься λ-исчислением, например), лишь бы их можно было записать в функциональном стиле. Эту же концепцию можно было бы применить и к длинной арифметике: хранить длинные числа как списки intов, вводить основной класс вида
          template<int digit, class Tail> struct BigInteger { };
          
          , операции над ним и так далее. Но во славу нового стандарта мы пойдём другим путём.
          Читать дальше →