Показаны сообщения с ярлыком python. Показать все сообщения
Показаны сообщения с ярлыком python. Показать все сообщения

пятница, 10 мая 2013 г.

Различные тонкости Python


Оператор сечения

Чтобы извлечь подстроку, можно использовать оператор сечения s[i:j]. Он извлечет из строки s все символы с порядковыми номерами k в диапазоне i<=k<j. Если какой-либо из индексов опущен, то он полагается равным началу или концу строки соответственно.

Оператор повторения

print '_'*10 
>>_ _ _ _ _ _ _ _ _ _

Строковое представление списка

ls = ['aaa', 'bbb', 'ccc']
print '---'.join(ls)
>>aaa---bbb---ccc

Оператор join помогает формировать строковое представление списка, помещая между элементами списка указанные символы.

Оператор with

Синтаксически выглядит так:

with выражение:
     блок кода

Упрощает код, который раньше использовал try...finally... для гарантированного исполнения завершающего кода. Например:

with open('f.txt', 'r') as f:
     for line in f:
     print line

В данном примере не только нам не нужно писать f.close(), т.к. из-за использования with файл автоматически будет закрыт, но и если в процессе чтения или обработки данных из файла возникнет ошибка, то файл все равно будет закрыт.

Рекурсия

#пример вычисления факториала

def factorial(n):
     if n <= 1: return 1
     else: return n*factorial (n-1)

Существует ограничение на глубину рекурсии. По умолчанию предел равен 1000.

Итерация с индексами

Такой прием работает не только со списками, но и с другими последовательностями (например, строками):

my_list = ['a', 'b', 'c']
for i,char in enumerate(my_list):
     print i, char

>>0 a
>>1 b
>>2 c

Упорядоченный словарь

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

d = {2:3, 1:89, 4:5, 3:0}
od = collections.OrderedDict(sorted(d.items()))
for k,v in od.iteritems(): print k,v
>>1 89
>>2 3
...

Генераторы

Вместо единственного значения функция с помощью инструкции yield может генерировать целые последовательности результатов. Например:

def countdown(n):
    print "Обратный отсчет!"
    while n > 0:
        yield n
        n -= 1

Любая функция, которая использует инструкцию yield, называется генератором. Метод next() заставляет функцию-генератор выполняться, пока не будет достигнута следующая инструкция yield:

c = countdown(5)
print c.next()
>>"Обратный отсчет!"
>>5
print c.next()
>>4
...

Функция-генератор обычно используется в инструкции цикла for, например:

for i in countdown(5):
    print i

>>"Обратный отсчет!"
>>5
>>4
...

Генераторы списков

Генераторы списков - конструкции, которые облегчают работу со списками. Генератор списка обычно имеет вид [выражение(x) for x in некоторый_список]. В результате его использования мы получаем список, каждый элемент которого равен результату применения некоторого выражения к соответствующему элементу некоторого списка.
К примеру, функцию, которая на вход получает список положительных чисел numlist и возвращает сумму их последних цифр, можно написать так:

ls = [str(l)[-1:] for l in numlist]
ls = map(int, ls)
print sum(ls)

Отметим, что map - еще одна полезная конструкция. Она получает на вход список и применяет к каждому его элементу указанную функцию (в данном случае преобразовывает в целое число каждый элемент списка ls)

Ключевое слово лямбда

Может использоваться для создания небольших анонимных функций. Анонимными называются функции, объявляемые в месте использования и не получающие уникального идентификатора для доступа к ним. Может возникнуть вопрос: зачем вообще нужны эти анонимные функции? Если использовать ключевое слово лямбда в связке с такими функциями как map, reduce и filter, то можно сократить код (и таким образом сделать его более легким для восприятия). Ниже приведены примеры полезности лямбды.

foo = [2,18,9,22,17,24,8,12,27]

#отфильтруем список, оставив только те числа, которые без остатка делятся на 3

print filter(lambda x: x%3 == 0, foo)
>> [18, 9, 24, 12, 27]

#преобразуем список foo, умножив каждый элемент на 2 и прибавив 10

print map(lambda x: x*2 + 10, foo)
>>[14,46,28,54,44, 58,26,34,64]

'''получим сумму всех элементов списка. Функция reduce при первом вызове делает что-то с двумя первыми элементами, потом что-то с результатом и третьим элементом, и т.д.'''

print reduce(lambda x,y: x+y, foo)
>>139

А вот еще пара примеров применения лямбды. 

#узнать длины слов в предложении

sentence = "It is raining cats and dogs"
words = sentence.split()
lengths = map(lambda word: len(word), words)

#вывести True, если число четное и False в противном случае

g = lambda x: not bool(x % 2)
print g(4)
>>True

Сопрограммы

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

def print_matches(matchtext):
     print "Поиск подстроки ", matchtext
     while True:
          line = (yield)
          if matchtext in line:
               print line

matcher = print_matches("Python")
matcher.next()
>> Поиск подстроки python
matcher.send("Hello world")
>>
matcher.send("Python is cool")
>> Python is cool

matcher.close()

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

Функции в Python

Функции в Python могут передаваться другим функциям в виде аргументов, сохраняться в структурах данных и возвращаться функциями в виде результата.

Пример 1. Передача функции в виде аргумента

def callf(func):
     return func()

def helloworld():
     print "Привет, мир!"

callf(helloworld)
>>Привет, мир!

Пример 2. Сохранение в структурах данных.

Следующий кусок кода 


def function1():
    print '1'
    
def function2():
    print '2'
    
def function3():
    print '3'

if value == 'one':
    function1()
elif value == 'two':
    function2()
elif value == 'three':
    function3()

можно переписать так:


switch = {
     'one': function1,
     'two': function2,
     'three': function3,
}

choice = raw_input('Enter one, two or three')
try:
     result = switch[choice]()  #получаем функцию и тут же вызываем ее
except KeyError:
     print "I didn\'t understand your choice"

Замыкание      

Замыкание - процедура или функция, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции и не в качестве ее параметров (а в окружающем коде). Рассмотрим следующий пример.

#файл foo.py
x = 42
def callf(func):
     return func()

#какой-то другой файл 
import foo
x= 37
def helloworld():
     return "Привет, мир!" x = %d % x

foo.callf(helloworld)
>>Привет, мир! x=37

Обратим внимание, что функция helloworld использует то значение переменной x,  которое была определено в том же окружении, что и сама функция helloworld. Когда инструкции, составляющие функцию, упаковываются вместе с окружением, в котором они выполняются, получившийся объект называют замыканием. 

Args и Kwargs

* - синтаксис для распаковки кортежа, ** - для распаковки словаря.
Рассмотрим следующий пример.

def tuple_test(x,y):
     x += 1
     y += 1
     print x, y

Если мы попробуем подать на вход этой функции кортеж, то будет ошибка:
t = (1,2)
tuple_test(t) #ошибка!

Ошибка возникнет потому, что функции нужны 2 аргумента, а кортеж будет интерпретироваться как 1 аргумент. Для того, чтобы ошибки не было, кортеж нужно распаковать:

tuple_test(*t)
>>2 3

То же самое для словаря:

d = {'x':1, 'y': 2}
tuple_test(d) #ошибка!

tuple_test(**d)
>>2 3

Ключевые слова args и kwargs используются при задании функций в случаях, когда заранее не известно количество и состав аргументов функции. Например:

def foo(*args, **kwargs):
     return args if args else kwargs

print foo(1,2)
>>(1,2)

print foo(1,2,3)
>>(1,2,3)

print foo(x=1, y=2)
>>{'x': 1, 'y': 2}

Декоратор

Декоратор - функция, основное назначение которой состоит в том, чтобы служить оберткой для другой функции или класса. Главная цель такого обертывания - изменить или расширить возможности обертываемого объекта. Например, в Django веб-приложении можно встретить такое:

from django.contrib.auth.decorators import login_required

@login_required
def my_view(request):
     ...

Функция login_required - декоратор, служит оберткой для функции my_view. login_required делает следующее:

если пользователь не залогинен, перенаправляет его на страницу авторизации,
в противном случае вызывает функцию my_view, которая формирует соответствующую html-страницу.

Вот еще пример декоратора.

enable_tracing = True

def trace(func):
    if enable_tracing:
        print "tracing..."
    else:
        return func
@trace
def square(x):
    return x*x

try:
    print square(2)
except:
    pass

>>tracing...

Информационные источники:



понедельник, 6 мая 2013 г.

ООП в Python. Часть 1

Определение класса. Пример класса.

Класс - разновидность абстрактного типа данных в объектно-ориентированном программировании. При использовании классов все элементы кода программы, такие, как переменные, константы, методы, процедуры и функции, могут принадлежать (а во многих языках обязаны принадлежать) тому или иному классу. Сам класс в итоге определяется как список своих членов, а именно полей(свойств) и методов/функций/процедур.

Пример класса в Python.

class OurClass(object):

   def __init___(self,arg1,arg2)
       self.arg1 = arg1
       self.arg2 = arg2

   def print_args(self):
       print self.arg1
       print self.arg2

Метод __init__() вызывается сразу же после создания экземпляра класса. Он напоминает конструктор класса в других языках программирования, и является первым блоком кода, который исполняется в контексте только что созданного экземпляра класса, но на момент вызова __init__() объект уже является созданным, и можно оперировать ссылкой на него - self.

Первым аргументом любого метода класса, включая __init__() всегда является ссылка на текущий экземпляр класса. Принято называть этот аргумент self. При вызове метода self указывать не надо, Python добавит его автоматически:

c = OurClass('1', '2')
c.print_args()
>>1
>>2

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

class Line(object):
     def __init__(self, p1, p2):
          self.line = (p1, p2)
     def __del__(self):
          print "Удаляется линия %s - %s" % self.line

Рассмотрим еще один пример класса. Это класс, который позволяет вести банковский счет клиента.

class Account(object):
    num_accounts = 0
    def __init__(self, name, balance):
         self.name = name
         self.balance = balance
         Account.num_accounts += 1
   def __del__(self):
        Account.num_accounts -= 1
   def deposit(self, amt):
        self.balance = self.balance + amt

Переменные класса (такие как num_accounts в данном примере) - значения, которые совместно используются всеми экземплярами класса.


Наследование

Наследование - механизм для создания новых классов, призванный настроить или изменить поведение существующего класса. Оригинальный класс называют базовым или суперклассом. Новый класс называют производным или подклассом. Наследование определяется перечислением в определении класса имен базовых классов через запятые. Наследование часто используется для переопределения поведения существующих методов  (можно переопределять любое количество методов суперкласса). Если поиск атрибута в экземпляре или классе экземпляра не увенчался успехом, то он ищется в базовых классах. Подкласс может добавлять к экземплярам новые атрибуты, определяя собственную версию метода __init__(). Например (класс Account ищи выше),

class EvilAccount(Account):
     def  __init(self, name, balance, evilfactor):
         Account.__init__(self, name, balance)
         self.evilfactor = evilfactor
         def inquiry(self):
         #переопределим функцию запроса баланса. При выполнении некоторого случайного
         #условия данный класс будет возвращать искаженное значение баланса на счете.
              if random.randint(0,4) == 1:
                   return self.balance*self.evilfactor
              else:
                   return self.balance

Когда производный класс определяет собственный метод __init__(), методы __init__() базовых классов перестают вызываться автоматически. Поэтому производный класс должен следить за выполнением инициализации базовых классов, вызывая их методы __init__(). Если базовый класс не имеет метод __init__(), этот шаг может быть пропущен. Если заранее не известно, определяется ли в базовом классе метод __init__(), для надежности можно вызвать его без аргументов, потому что всегда существует реализация по умолчанию, которая ничего не делает.

Рассмотрим пример, когда в производном классе требуется переопределить метод, но при этом желательно вызвать оригинальную реализацию:

class MoreEvilAccount(EvilAccount):
     def deposit(self, amount):
         self.withdraw(5.00) #вычесть комиссию
         super(MoreEvilAccount,self).deposit(amount) #а теперь пополнить счет

В Python поддерживается множественное наследование.

class DepositCharge(object):
    fee = 5.00
    def deposit_fee(self):
        self.withdraw(self.fee)

class WithdrawCharge(object):
     fee = 2.50
     def withdraw_fee(self):
         self.withdraw(self.fee)

class MostEvilAccount(EvilAccount, DepositCharge, WithdrawCharge):
      def deposit(self, amt):
           self.deposit_fee()
           super(MostEvilAccount, self).deposit(amt)
      def withdraw(self, amt):
           self.withdraw_fee()
           super(MostEvilAccount, self).withdraw(amt)

Чтобы обеспечить поиск атрибутов при множественном наследовании, все базовые классы включаются в список, в порядке от более специализированных к менее специализированным. Класс EvilAccount является более специализированным, чем Account, так как он его наследует. DepositCharge более специализирован, чем WithdrawCharge, потому что стоит первее в списке базовых классов.

Полиморфизм

Полиморфизм - свойство, которое позволяет одно и то же имя использовать для решения двух или более схожих, но технически разных задач. Например, для языка Си, в котором полиморфизм поддерживается недостаточно, нахождение абсолютной величины числа требует 3 различных функций: abs(), labs() и fabs(). Эти функции подсчитывают и возвращают абсолютную величину целых, длинных целых и чисел с плавающей точкой соответственно. В C++ вместо нескольких таких функций используется функция abs().

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

class Animal(object):
     def talk(self):
          pass

class Cat(Animal):
      def talk(self):
          return 'meow'

class Dog(Animal):
      def talk(self):
           return 'bark'

Полиморфизм позволяет, например, осуществлять такие вещи:

Kitty = Cat()
Toto = Dog()
d = [Kitty, Toto]
for el in d:
    el.talk() #без разницы, экземпляром какого класса является el - полиморфизм

Инкапсуляция

Можно скрыть ненужные внутренние подробности работы объекта от окружающего мира. В Python инкапсуляция реализована лишь частично. А именно, если вы хотите, чтобы атрибут класса (т.е. переменная, свойство или метод) был скрыт от посторонних глаз, вам нужно изменить его имя, дописав сначала два подчеркивания (__):

class Simple(object):
__private_attr = 10
def __init__(self):
    self.__private_attr = 20

s = Simple()
print s.__private_attr #вызовет ошибку

Вот здесь показано, что в Python такую инкапсуляцию можно при желании легко обойти.

Композиция и агрегация

Композиция: объект может быть составным и включать в себя другие объекты. Еще композицию определяют так: механизм для создания нового класса путем объединения нескольких объектов существующих классов в одно целое. Вложенные объекты обычно объявляются закрытыми - частными внутри класса-агрегата. Возникает вопрос: чем отличается композиция от наследования? Наследование предполагает похожесть, а композиция - формирование целого из частей.

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

"Старые" и "новые" классы: отличия

Обратим внимание на инструкцию OurClass(object). Если вы не хотите определить этот класс как наследованный от какого-то другого класса, то его нужно определить как наследованный от object. Также можно наследовать встроенные классы и классы из модулей расширения. Эта особенность появилась начиная с Python 2.2, классы, наследованные от object или других классов, называются "новыми классами".

До сих пор в коде библиотек Python можно встретить и классы старого образца, которые определяются так:

class ClassName:
...

Они еще работают, но уже помечены как deprecated.


Список информационных источников

Класс (Википедия), Погружение в Python 3 (викитека), Полиморфизм в python younglinux, Программирование на python. Часть 6 ibm, Композиция в python younglinux, Д.Бизли. Python. Подробный справочник, introduction to OOP with python, ООП Python (википедия)

среда, 3 апреля 2013 г.

Для прокачивания навыка решения алгоритмических задач зарегистрировалась на spoj. Этот сайт удобен тем, что на нем выложено много задачек, в том числе и "классических". После удачного решения очередной задачи рейтинг пользователя повышается, что очень круто, хочется решать еще и еще(кажется, такой прием стимулирования пользователей называется геймификацией).

На сайте spoj можно решать задачки на разных языках программирования. Я пробовала решить задачу бинарного поиска. Но, к сожалению, обычный способ не подходит - выдается time limit error, а с оптимизацией - выдается wrong answer. Некоторое время пыталась найти ошибку в алгоритме с оптимизацией, но не смогла. Организовала дискуссию по этому вопросу, но никто ничего внятного не ответил, так что забила на эту задачу. Пробовала делать другую задачу (нахождение квадратного корня). Даже нашла итерационный алгоритм быстрого нахождения корня. Его реализация отрабатывала очень быстро. Но потом почитала комментарии к задаче и увидела, что автор задачи отключил прием решений на Python после жалоб про time limit exceeded. Общее впечатление осталось такое: если хочется без проблем прокачать навыки на этом сайте, то это лучше всего делать на каком-нибудь C++. А с Python все будет намного сложнее. 

Потом мы с Дмитрием пробовали участвовать в одном из чемпионатов Codechef. Задачка была такова: для заданного целого N > 0 найти количество палиндромов из букв английского алфавита, длины не превосходящей N.  Загвоздка была в том, что N могло быть очень большим, поэтому ответ нужно было вывести как остаток от деления (результат / 10^9 + 7). Были и другие задачки, но захотелось начать с чего-то полегче. На все про все давалось 3 часа. Сначала получился такой код:

def get_PNum(N):
    if (N==1):
        return 26
    elif (N % 2 == 0):
        return get_PNum(N-1) + pow(26,N/2)
    else:
        return get_PNum(N-1) + pow(26,N/2)*26

(26 - потому что 26 букв в алфавите, N/2 - потому что уникальность палиндрома определяется сочетанием букв из его половины).

При попытке отправить решение выдавалась time limit error. Тогда я видоизменила код так:


def get_PNum(N):
    if (N == 1): 
        return 26
    result = 26.0
    for i in range(2, N+1):
        if (i % 2 == 0):
            result = result + pow(26,i/2)
        else:
            result = result + pow(26,int(i/2))*26
    return result

Опять time limit error. Тогда я увидела, что можно еще свернуть формулу, использовав формулы для суммы членов и количеств членов геометрических прогрессий (тут как бы получаются две прогрессии, с одинаковым множителем, просто первый член разный, ну и количество членов разное):


def get_PNum(N):
    if (N == 1): 
        return 26
    n = 0.0
    m = 0.0
    if (N % 2 == 0):
        n = (N-2)/2 + 1
    else:
        n = (N-1)/2 + 1
    m = N - n    
    return 26*(pow(26,n) - 1)/25 + 26*(pow(26,m)-1)/25

Опять time limit error! Но тут пришла догадка, что нужно попробовать решить задачу для числа N = 1000000000. Eclipse просто стал вываливаться на этом числе. Оказалось, что функция возведения в степень просто сходит с ума на таких больших числах. Нашелся алгоритм "быстрого возведения в степень", но как раз к этому моменту, к сожалению, 3 часа соревнования подошли к концу. А еще, оказывается (это уже просмотр удачных решений других пользователей) надо было сразу делить (как только можется) оперируемые числа на 10^7 (а не делить после того, как функция вернет результат).
Ну в общем, можно сказать, что опыт был успешный, мозги в процессе поупражнялись :)