среда, 23 февраля 2011 г.

Python и цепная реакция и ... дескрипторы

А теперь мы научимся делать ядерную бомбу на Python ... Нет, не о том...

Хочу поделится своими мыслями по поводу одного прикольного стиля программирования классов - цепные вызовы. Для кого-то это будет не ново, кому-то, может, не нравится, но я считаю, что такому стилю можно найти применение, при этом исходник программы будет выглядеть более понятно и логично.

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

Простая задачка
Рассмотрим реализацию простого класса, назовем его "тупой охранник". Представим себе, что мы делаем компьютерную игру. У нас есть замок, а у ворот патрулирует охранник: ходит туда-сюда, больше ничего не делает. Код на Python 3.1:

class StupidGuard:
    """
    Stupid guard that moves around given route (way points).
    """
    direction = 0
    position = {'x': 0, 'y': 0}
  
    def go(self, steps):
        self.position['x'] += steps * cos(radians(self.direction))
        self.position['y'] += steps * sin(radians(self.direction))
    def rotate(self, angle):
        self.direction += angle
  
    def __repr__(self):
        return 'Guard: %s' % self.position

Код и математика очень просты и, думаю, разъяснений не требуется. Итак, охранник у нас есть, давайте заставим его патрулировать:

guard = StupidGuard()
print (guard)
guard.go(5)
guard.rotate(180)
guard.go(5)
guard.rotate(180)
print(guard)
Вот, что нам говорит Python о состоянии нашего человека в начале и конце пути:

Guard: {'y': 0, 'x': 0}
Guard: {'y': 6.123233995736766e-16, 'x': 0.0}
Итак, задачка сделана - охранник ходит. Только долго как-то ходит - 4 строчки кода. А хочется, чтобы он ходил не 4 строчки кода, а, например, одну :)

Цепные вызовы
Это в принципе и есть тот простой способ - цепные вызовы методов. Суть в том, что вышеприведенный код переписать так:
guard.go(5).rotate(180).go(5).rotate(180)
Нетрудно догадаться, что для этого нужно всего навсего сделать так, чтобы методы go и rotate возвращали self, а не None, как есть сейчас. То есть эти методы превращаются в такие:
def go(self, steps):
        self.position['x'] += steps * cos(radians(self.direction))
        self.position['y'] += steps * sin(radians(self.direction))
        return self
    def rotate(self, angle):
        self.direction += angle
        return self
Работает? Отлично работает. Но такой способ мне показался недостаточно гламурным и я решил сделать декоратор, назовем его Chained, чтобы каждый раз не возвращать self. Естественно, это код не сокращает, но выразительность такого кода гораздо выше, нежели return True. Декоратор-декоратором, а просто декоратором обойтись нельзя. Так как декоратор метода должен иметь доступ к экземпляру класса, - приходится писать дескриптор.

Пишем дескриптор и наводим марафет
Итак, дескриптор для этой задачи довольно простой и небольшой:
class Chained:
    """
        Descriptor makes method to always return its owner class instance
    """
  
    def __init__(self, method):
        self.method = method
      
    def __get__(self, instance, owner):
      
        def wrapper(*args, **kwargs):
            self.method(instance, *args, **kwargs)
            return instance
      
        return wrapper
Все, что он делает - оборачивает метод экземпляра в функцию, которая передает начальный код на исполнение, но возвращает экземляр класса, метод которого мы декорируем. Соответственно поменяется код нашего охранника:
class StupidGuard:
    """
    Stupid guard that moves around given route (way points).
    """
    direction = 0
    position = {'x': 0, 'y': 0}
  
    @Chained
    def go(self, steps):
        self.position['x'] += steps * cos(radians(self.direction))
        self.position['y'] += steps * sin(radians(self.direction))
    @Chained      
    def rotate(self, angle):
        self.direction += angle
  
    def __repr__(self):
        return 'Guard: %s' % self.position
Теперь мы с легкостью можем заставить его ходить уже двумя способами:
guard = StupidGuard()
print (guard)
guard.go(5)
guard.rotate(180)
guard.go(5)
guard.rotate(180)
print(guard)
guard.go(5).rotate(180).go(5).rotate(180)
print(guard)
Вот что интерпретатор сообщает о состоянии объекта:
Guard: {'y': 0, 'x': 0}
Guard: {'y': 6.123233995736766e-16, 'x': 0.0}
Guard: {'y': 1.224646799147353e-15, 'x': 0.0}
Ну вот и все
Ничего сложного и неочевидного, как видите, нет. Всего, чего, по-моему, можно добиться так это большей выразительности и читабельности кода. На более сложных примерах с разными рабочими процессами моделей это, пожалуй, будет выглядить более красиво.

понедельник, 21 февраля 2011 г.

Это Python такой тормоз или я?

Пролог
Ускоряем Python-код
Этот небольшой пост хочу посвятить оптимизации скорости выполнения кода на Python. Зачастую говорят, что Python - большой тормоз. При этом представляют куски кода, мол, вот, - попробуй такое ускорить. Да, действительно, некоторый код нельзя ускорить, потому что... потому что гладиолус. Но в огромном количестве случаев случается так, что тормоза программы вовсе не из-за языка, а... правильно, из-за разработчика. И вся проблема кроется в реализации алгоритма. Хочу показать небольшой пример оптимизации небольшой математической задачки. Итак, начнем. Задачка очень простая, взятая из projecteuler.net

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

Решение в лоб
Итак, не вдаваясь в исследование математических свойств палиндромов, выполним решение задачки в лоб. Алгоритм примерно такой:
  1. Цикл по числам от 100 до 999.
  2. Внутренний цикл по числам от 100 до 999.
  3. Если произведение переменных итерации внешнего и внутреннего цикла - палиндром и он больше предыдущего найденного - запоминаем его.
  4. Получаем резульат.
Еще раз напомню, что основная задача здесь - написать код, а потом пытаться его оптимизировать, то есть не придумывать другой более быстрый алгоритм, а оптимизировать уже реализованный.

Итак, сделаем программу (Python 3.1)
from timeit import timeit

def is_palindrome(number):
    return str(number) == str(number)[::-1]

MIN = 100
MAX = 1000

def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            if is_palindrome(i*j) and i*j > max_number:
                max_number = i*j
    return max_number

print (timeit('largest()', 'from __main__ import largest', number = 1))
print(largest())
Для приблизительного измерения скорости работы программы воспользуемся модулей timeit. Прогоним несколько раз, и получаем:


Результат906609
Самое быстрое время выполнения: 1.6514 секунд.


Оптимизация № 1: очевидная.
Итак, мы видим здесь одно очевидное улучшение, которое можно выполнить. У нас операция умножения выполняется три раза. Сделаем так, чтобы выполнялась 1 раз (дальше буду приводить только код функции largest, чтобы не засорять текст):
def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            product = i * j
            if is_palindrome(product) and product > max_number:
                max_number = product
    return max_number
Результат: 906609
Самое быстрое время выполнения: 1.5932 секунд
Прирост: 3.65%

Немного, но, тем не менее, код немножко ускорился.

Оптимизация №2: это просто интересно
Есть такой момент, что иногда очень часто вызываемые встроенные функциям удобно присваивать псевдонимы в локальном пространстве функции (спасибо semargl89). Таким образом интерпретатор не будет каждый раз при вызове функции искать указатель на нее. В данном случае, такая функция - str. Добавим следующую строчку перед функцией is_palindrom, и изменим соответственно саму функцию is_palindrom:
lstr = str
def is_palindrome(number):
    return lstr(number) == lstr(number)[::-1]
Результат906609
Самое быстрое время выполнения1.5514 секунд
Прирост (от первого варианта)6,44%

Еще немножко ускорили.

Оптимизация №3: веселые условия
Итак, смотрим дальше, что же тут можно еще сделать. Цикли мы никак не изменим. А вот количество вызовов злосчастной is_palindrom можно сократить. А это, по большому счету, сама затратная функция, ведь здесь выполняется преобразование чисел, реверсинг строки, а потом еще и сравнение. Не секрет, что Python обладает сокращенной моделью вычисления условий. То есть, если на некотором этапе условной конструкции уже можно дать ответ, остальную часть конструкции он выполнять не будет. Вот новый код:
def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number
Как видите, все, что мы сделали - поменяли местами операнды оператора and: первым теперь идет условие product > max_number. Таким образом, каждый раз, когда произведение не больше уже найденного - мы не проверяем, является ли оно палиндромом. А результаты на самом то деле поражают:

Результат906609
Самое быстрое время выполнения: 0.2731 секунд
Прирост (от первого варианта)604,69%

Это ж уже почти в семь раз! Что ж, идем дальше.

Оптимизация №4: выходит из предыдущей
Итак, в связи с таким поворотом событий, логически предположить, что чем раньше мы находим большие палиндромы, тем меньше раз вызывается is_palinfrom, что нам только на руку. Теперь есть смысл изменить циклы. Сделаем их не возрастающими, а совсем наоборот. Итак, новый код:
def largest():
    max_number = 0
    for i in range(MAX-1, MIN-1, -1):
        for j in range(MAX-1, MIN-1, -1):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number
Результат: 906609
Самое быстрое время выполнения: 0.1925 секунд
Прирост (от первого варианта): 857,87%

И еще одно существенное ускорение. Наш код уже быстрее примерно в восемь с половиной раз!

Оптимизация №5: не надо делать все по 2 раза
Просмотрев цикл, мы заметим, что все умножения выполняются по два раза, то есть, кроме i * j выполняется еще и j * i. Давайте исключать такие нехорошие вещи:
def largest():
    max_number = 0
    for i in range(MAX-1, MIN-1, -1):
        for j in range(MAX-1, i - 1, -1):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number
Итак, мы сделали внутренний цикл поменьше, при этом даже ничего не поломали.

Результат906609
Самое быстрое время выполнения0.0938 секунд
Прирост (от первого варианта)1760,55%

Ну, думаю, хватит
Итак, проведя несколько минут медитации над кодом, можно добиться ускорения примерно в 20 раз. Не так уж плохо. Мораль сей басни такова: "перед тем как грешить на Python, - тщательно проверяйте свой код".

Размышления об идеальной архитектуре приложения. Часть 2: Развеиваем мифы?

Содержание

Часть 2

Пролог
Прошло уже несколько дней с момента публикации первого поста по данной теме. Ух и наслышался я о себе за это время, ну, не так о себе, как о моей идее. К сожалению все "Фу..." не пошло в комментарии. Кто-то писал мне в скайп и джаббер, кто-то - плюнул в лицо при личной встрече. Подведя итог: все усомнились и поулыбались. Но... Многие, судя по комментариям так и не поняли, что я хочу донести, то есть неправильно поняли суть решаемой задачи, и сейчас я это хотел бы исправить. Это скорее моя ошибка, да еще терминатор подогрел.

И в конец пролога - угадайте, что же это за такой талантливый инженер изображен на фотке справа :)

Я не пытаюсь создать универсальное средство решения задач
Это коренное заблуждение, которое я увидел в комментариях к моему посту. Универсальное средство решение - есть наш мозг. Но самый занятный момент здесь в том, что он не предназначен напрямую решать задачи. Схему его работы скорее можно представить как: "научится решать" -> "решить". А в нашее время еще и создать средство для того, чтобы задачу, которую мы научились решать - решал кто-то другой. Например, арифметические операции прекрасно выполняет калькулятор.

К чему я веду?
Я веду к тому, что я хочу создать не фреймворк, который решает все задачи (то есть это не универсальная нейросеть, и никакой другой универсальный апарат решения задач), - это уже не будет фреймворк, а "кнопка" "Сделать зашибись". Я хочу создать фреймворк реализующий архитектуру (подход, методологию) приложения, которую можно применить для всех задач.
Привожу пример
практически все боьшие коммерческие компьютерные игры создаются на объектно-ориентированных языках (в основном это С++). Попытка сделать игру пользуясь только структурным подходом приведет сами понимаете к чему.
Но какой занимательный факт. Ведь имея, например, в своем распоряжении, грубо говоря, функцию main (рассмотрим вариант на С), мы можем написать любое приложение:
int main() {
// Do any task in the world
return 0;
}
То есть, по сути, вот оно! =) Отсутствие фреймворка, каких-либо архитектурных правил и ограничений и привело нас к цели. Пользуясь таким "фреймворком" можно сделать все.

Смешно, да?
Действительно, понаписывал про терминаторов, про всякую фигню и дошел до того, что фреймворки нафиг не нужны. Не совсем так.

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

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

Заключение
Дела с покорением мира обстоят немножко плохо, но, благодаря уверености Андрея Светлова в том, что задача более легкая и обозримая, как-нибудь к ней вернусь, может даже напишу о прогрессе здесь.

Надеюсь, что внес некоторую ясность в идею, изложенную в предыдущей публикации, если не запутал вас еще больше :)

пятница, 18 февраля 2011 г.

Размышления об идеальной архитектуре приложения. Часть 1: Возможно ли это?

Содержание

Часть 1

Пролог

Нет, здесь я имею в виду не язык программирования, а именно вступление к публикации. И терминатор здесь как нельзя кстати, потому что мы будем решать именно задачу построения "Терминатора", как минимум T-100, а дальше как пойдет. Ко всем уважаемым читателям есть огромная просьба выполнять следующие пункты:
  • читать пост до конца
  • если не читаете до конца - просто забейте, и не пишите комментарии.
  • если уж собрались писать, не задавайте, пожалуйста, вопросы о моем возрасте, цвете волос и прочем :)
  • я на них отвечаю тут: мне на момент написания статьи - 21 год, учусь на 5-м курсе института, цвет волос каштановый...
  • на посты типа: "это нереально", отвечаю тут же известной эмпирически созданной формулой группой ученых, пытавшихся создать контроллируемый ядерный взрыв: "энтузиазм = 1/опыт".
Так, с прологом разобрался, всех остальных милости прошу дальше...

Постановка задачи

Тем, кто во время чтения пролога забыл, в чем суть задачи, напоминаю, и переформулирую:

"Существует ли идеальная архитектура приложений, и можна ли создать фреймворк годный для решения всех-всех-всех задач программной инженерии?"

Вот это постановка вопроса! Да? Существует ли ответ на этот вопрос?
Ну, судя по наличию языков программирования, фреймворков и решений... наверное, пока нет.
Стоит ли работать над этим? То есть, стоит ли искать такое решение?
Предположим, что да. Зачем тогда я тут стучу пальцами по клавиатуре?
Являются ли все существующие решения этим самым поиском?
Осмелюсь сказать, что нет. Есть множество шаблонов проектирования, рекомендаций на все случаи жизни, архитектур, и еще много умных слов, аббревиатур, которые успешно и неуспешно используются при создании приложений.
Почему?
Каждый инженер-разработчик работает в своем кругу задач. Общее множество задач растет с каждым днем с развитием аппаратных и программных платформ, поэтому эти самые инженеры-разработчики работают с каждым днем с более узким кругом задач (если брать отношение мощности множества задач к общему множеству всех-всех-всех возникающих задач). То есть, из это следует, что на самом деле мы не приближаемся к решению, а отдаляемся от него.
Пути решения

Если попытаться приближаться к решению, мы стыкаемся с двумя принципиальными моментами:
  1. Тот, кто решает данную задачу, должен набить руку в большом круге областей задач (в идеале на всем множестве возникающих инженерных задач компьютерных наук), и должен быть знаком с лучшими (предпочтительными / идеальными) решениями этих задач. Потом найти пересечение множеств всех подходов к решению задач, и... вуаля! В чем проблема? Наверное в том, что никакой жизни не хватит такой опыт получить :)
  2. Исходя из предыдущего пункта, напрашивается вывод, что с практической стороны подход невозможен, и решать эту задачу (создавать фреймворк) нужно призывая теоретический подход. Хорошо это? Ну, как показывает практика, 100 500 подводных камней могут возникнуть, и, собственно, возникают. Как их избежать?
Выбор пути

Из вышесказанного можно предположить, что только второй путь, по крайней мере, кажется не невозможным. Что я предлагаю? Я предлагаю пойти этим путем, принимая только "аксиоматические" мысли, и отбрасывая спорные. То есть поступать примерно так, как это делают математики: "Определяем аксиомы, на их основе строим теоремы, и доказываем их".

Выводы

Идельной универсальной архитектуры приложений нет ... Пока... Почему-бы не попытаться ее создать? На Python, конечно, на чем же еще? :) "There should be one-- and preferably only one --obvious way to do it." Может, он существует, путь этот, неизбитый?

Благодарности

Особую благодарность хочется выразить моему другу Дмитрию ака semargl89, при участии которого эта злостная публикация появилась, и который со всем написанным согласен :), но требует деталей и продолжения, и участвует в дискуссиях составляя мне оппозицию.
To be continued... maybe soon... maybe later... maybe sometimes...
P.S
Минуту назад зафоловил Шварценеггера в Твиттере :)

четверг, 3 февраля 2011 г.

Переходим на Python 3. Где же ты, reduce?

Это мой второй пост об освоении Python 3. Начался он с того, что захотелось мне использовать всем известную встроенную функцию reduce, а я вместо рабочего кода получил NameError. Оказывается в Python 3 она уже не встроенная, а находится в module functools, в который, начиная с версии Python 2.5, всунули несолько полезностей для работы с объектами-функциями. То есть теперь функцию reduce нужно импортировать.
from functools import reduce
Стоит заметить, что спецификация функции не поменялась, работает она точно также как и во втором питоне. Постал вопрос: "Зачем?". (Более подробно о reduce читаем в документации).

С чего все началось?
А началось все с Гвидо ван Россума, сделавшего следующее высказывание, когда Python 3k только начинали делать. Вот вольный перевод:
Около 12 лет назад в Python появились lambda, reduce(), filter() и map(); появились они с соизволения (мне кажется) Lisp-хакера, которому не хватало их в Python, и который предоставил работающие патчи. Но, невзирая ни на что, я думаю, что эти вещи нужно вырезать из Python 3000.
Также известно, что Гвидо считает эти вещи ненужными, так как есть так называемые "list comprehensions", то есть конструкции типа:
>>> [i * 2 for i in my_list if i > 0]
Вот мнение "великодушного диктатора" о reduce:
Теперь о reduce(). На самом деле это то, что я ненавижу больше всего, потому что кроме нескольких примеров с + или *, почти всегда, когда я вижу вызов reduce() с нетривиальной функцией, мне нужно брать ручку и бумагу, чтобы нарисовать диаграму того, что же действительно передается в функцию перед тем, как понимаю, для чего на самом деле здесь использовалась reduce(). Так что, по-моему, reduce() - практически ограничена ассоциативными операторами, и во всех других случаях лучше сделать явный кумулятивный цикл.
Нужна ли reduce вообще?
Просмотрев свой код и вижу, что за 3 с лишним года работы с Python я использовал reduce, в отличие от map, filter и lambda, очень редко. Задумываясь о различных способах реализации того или иного блока кода, можно увидеть массу случаев, где нужно применить reduce и в большинстве из них находятся альтернативные решения, которые делают код более понятным и читабельным. Рассмотрим несколько примеров на простом списке:
>>> v = [0,1,2,3,4]
Суммирование:
>>> r = reduce(lambda x, y: x + y, v)
>>> print(r)
10
Ествественно, такое никому не нужно, когда есть sum:
>>> sum(v)
>>> 10

Рассмотрим умножение:
>>> v = [1, 2, 3, 4]

>>> reduce(lambda x, y: x * y, v)
>>> 24

>>> r = 1
>>> for i in v:
>>> r *= i
>>> 24
Здесь вариант с reduce выглядит более чем привлекательным.

Соединение списков:
>>> reduce(list.__add__, [[1, 2, 3], [4, 5], [6, 7, 8]], [])
[1, 2, 3, 4, 5, 6, 7, 8]

>>> from itertools import chain
>>> list(chain([1, 2, 3], [4, 5], [6, 7, 8]))
[1, 2, 3, 4, 5, 6, 7, 8]
По-моему, вариант с itertools является более понятным и, что гораздо интереснее, возвращает не список, а ... догадайтесь сами. Для других задач зачастую находятся более красивые, или более читабельные решения, например, для логических - использование функций any и all.

reduce для меня и заключение
Иногда с использованием reduce замечаю, что через некоторое время код воспринимается тяжелее, особенно, если это не тривиальное использование оператора, а reduce помешанная с множественными вложенными вызовами функций, поэтому стараюсь применять reduce там, где это действительно упрощает код и делает его красивее, а такие ситуации, по-моему, возникают очень редко и должны быть видны сразу: если уже задумываешся, значит что-то не так, что-то некрасиво.

Вообще-то я поддерживаю решение вынести reduce из разряда встроенных функций в модуль functools, теперь, перед тем как нагадить в коде дважды подумаю, ну для этого ж нужно еще один дополнительный импорт! :)

Всем спасибо за внимание, кастую холиварщиков в комменты...
В этом гаджете обнаружена ошибка