пятница, 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 (википедия)

воскресенье, 5 мая 2013 г.

Вычислительная сложность алгоритмов

Для оценки эффективности алгоритма наиболее важными показателями являются:

- время выполнения алгоритма,
- требуемый объем оперативной памяти.

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

Упрощения для оценки времени выполнения алгоритмов


В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому   А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например,  при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение, предложенное для приблизительного расчета времени выполнения алгоритмов.

Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных), 

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
\(3N^4 - N^2 + 12N \sim 3N^4\).

Далее используют О-нотацию:

вместо \(1/6N^3\) пишут "этот алгоритм имеет сложность \(O(N^3)\), вместо \(3N^4\) пишут "этот алгоритм имеет сложность \(O(N^4)\)".

Определение O-большого

Говорят, что \(f\) является "O  большим" от \(g\) при \(x \to x_0\), если существует такая константа \(C>0\), что для всех \(x\) из окрестности точки \(x_0\) имеет место неравенство \(|f(x)| \leq C|g(x)|\). Ниже приведена иллюстрация определения (ось \(x\) - размер входных данных, ось \(y\) - время выполнения алгоритма). Мы видим, что начиная с некоторой точки при стремлении размера входных данных к \( \propto\) \(f(n)\) растет медленнее, чем \(g(n)\) и вообще \(g(n)\) как бы ограничивает ее сверху.

Примеры. \(1 = O(N), N = O(N^2).\)

Наряду с оценками вида \(O(N)\) используется оценка \(\Omega(N)\) (омега большое). Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция \(f(N)=\Omega(N^2)\). Это значит, что даже в самом удачном случае будет произведено не менее \(N^2\) действий. В то время как оценка \(O(N^3)\) гарантирует, что в худшем случае будет не более чем порядка \(N^3\) действий. Также используется оценка \(\Theta(N)\) (тэта), которая является верхней и нижней асимптотической оценкой, когда \(O(N)\) и \(\Omega(N)\) совпадают. Итак, \(O(N)\) - приближенная оценка алгоритма на худших входных данных, \(\Omega(N)\) - на лучших входных данных, \(\Theta(N)\) - сокращенная запись одинаковых \(O(N)\) и \(\Omega(N)\).

Оценки времени выполнения для разных алгоритмов

Обозначим T(N) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:

1. набор инструкций, включающих только базовые операции:

statement 1;
...
statement k;

Тогда T(N) = T(statement 1) + ... + T(statement k).

Т.к. каждая инструкция включает только базовые операции, то время выполнения этого куска кода не зависит от размера входных данных (не растет с ростом размера входных данных), т.е. является константой. Этот алгоритм имеет сложность O(1).

2. if-else инструкции

if (condition) {
    sequence of statements 1
}
else {
    sequence of statements 2
}

Здесь выполнится либо sequence of statements 1, либо sequence of statements 2, поэтому, т.к. мы хотим получить оценку времени выполнения в наихудшем случае, T(N) = max(T(sequence of statements 1), T(sequence of statements 2)). Например, если время выполнения sequence of statements 1 будет  O(N), а sequence of statements - O(1), то T(N) = O(N).

3. Циклы.

for (i = 0; i < N; i++) {
    sequence of statements
}

Т.к. цикл выполнится N раз, то sequence of statements тоже выполнится N раз. Если T(sequence of statements) = O(1), то T(N) = O(N)*O(1) = O(N).

4. Вложенные циклы.

for (i = 0; i < N; i++) {
    for (j = 0; j < M; j ++){
        ...
    }
}

Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, выполняется внутренний цикл M<N раз. Если мы хотим получить оценку времени выполнения в наихудшем случае, то \(T(N)=O(M*N)=O(N^2)\), если \(M<N\).

Теперь рассмотрим такой код:


for (i = 0; i < N; i++) {
    for (j = i + 1; j < N; j ++){
        sequence of statements
    }
}


Посмотрим на изменение количества итераций внутреннего цикла в зависимости от итерации внешнего цикла.

i        цикл j (кол-во раз выполнения)
0       N
1       N-1
2       N-2
...
N-1   1

Тогда sequence of statements выполнится N + N-1 + ... + 1 раз. Для быстрого подсчета подобных сумм пригодятся формулы из матанализа, в данном случае формула


Т.е. этот алгоритм будет иметь сложность \(O(N^2)\).

А вот и другие наиболее часто нужные формулы, полезные для подобных случаев:


4. Когда утверждение включает вызов метода, то оценка времени выполнения утверждения рассчитывается с учетом оценки времени выполнения метода. Например:

for (j = 0; j < N; j ++){
    g(N);
}

 Если время выполнения метода \(g(N)=O(N)\), то \(T(N) = O(N)*O(N) = O(N^2)\).

5. Двоичный(бинарный) поиск.

int l = 0;
int u = A.length - 1
int m;
while (l <= u) {
    m = l + (u - 1)/2
    if A[m] < k {
         l = m +1;
    }
    else if A[m] == k {
         return m;
    }
    else{
         u = m - 1;
   }
}
return -1;

Двоичный поиск позволяет найти индекс числа k в отсортированном массиве, если этого числа в нем нет, то возвращается -1. Сначала мы сравниваем k с числом, находящимся в середине массива. Если k меньше этого числа, то дальше мы должны искать его в левой половине массива, если больше - то в правой половине. Далее k сравнивается с числом, находящимся в середине выбранной на предыдущем шаге половины массива и т.д. С каждой итерацией пространство поиска сужается вдвое. Возникает вопрос: сколько итераций необходимо будет проделать в наихудшем случае (т.е. когда в массиве так и не будет найдено число, равное k и не останется данных для сравнения).

Мы видим, что после 1 итерации останется \(N/2\) данных для поиска индекса \(k\), после 2 итерации останется \(N/4\) данных, после 3 итерации - \(N/8\) и т.д. Мы узнаем количество итераций в наихудшем случае, если решим уравнение \(\frac{N}{2^x}=1\). Это уравнение равносильно уравнению \(2^x=N\), отсюда \(x=log_{2}(N)\) или \(x=lg(N)\) (см. определение логарифма). Поэтому оценка сложности алгоритма бинарного поиска - \(O(logN)\).

Хорошая новость заключается в том, что для характеризации времени выполнения большинства алгоритмов достаточно всего нескольких функций: \(1, logN, N, NlogN, N^2, N^3, 2^N\). На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных:


Из этого графика, в частности, видно, что если время выполнения алгоритма "логарифмическое", т.е. алгоритм имеет сложность \(O(logN)\), то это очень круто, т.к. время его выполнения очень медленно растет с увеличением размера входных данных, если время выполнения линейно зависит от размера входных данных, то это тоже неплохо, а вот алгоритмы с экспоненциальным временем работы (\(O(2^N)\)) лучше не использовать совсем или использовать только на данных очень малого размера.

классы P и NP

Вещественная неотрицательная функция \(f(m)\), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином \(P(m)\) с вещественными коэффициентами такой, что \(f(m) \leq P(m)\) для всех \(m \in N^+\).  Задачи, для которых существуют алгоритмы с "полиномиальным" временем работы принадлежат классу P (эти задачи в основном решаются быстро и без каких-либо проблем).

Формальное определение. Язык L принадлежит классу P, тогда и только тогда, когда существует детерминированная машина Тьюринга M, такая, что:

- при любых входных данных M заканчивает свою работу за полиномиальное время,
- для всех \(x \in L\) M выдает результат 1,
- для всех \(x\), не принадлежащих \(L\), M выдает результат 0.

Задачи класса NP - задачи, удовлетворяющие условию: если имеется ответ (возможное решение), то его легко верифицировать - проверить, является оно решением или нет.

Рассмотрим пример задачи из класса NP. Пусть дано множество целых чисел, например, {-7,-3, -2, 5, 8}. Требуется узнать, есть ли среди этих чисел 3 числа, которые в сумме дают 0. В данном случае ответ "да" (например, такой тройкой являются числа {-3,-2,5}. При возрастании размера множеств целых чисел количество подмножеств, состоящих из 3 элементов, экспоненциально возрастает. Между тем, если нам дают одно такое подмножество (его еще называют сертификатом), то мы легко можем проверить, равна ли 0 сумма его элементов.


Формальное определение:

Язык L принадлежит классу NP, тогда и только тогда, когда существуют такие полиномы \(p\) и \(q\) и детерминированная машина Тьюринга M, такие, что:

- для любых \(x,y\) машина M на входных данных \((x,y)\) выполняется за время \(p(|x|)\),
- для любого \(x \in L\) существует строка \(y\) длины \(q(|x|)\), такая что \(M(x,y)=1\),
- для любого \(x\) не из \(L\) и всех строк длины \(q(|x|)\) \(M(x,y)=0\).

Полиномиальная сводимость или сводимость по Карпу. Функция \(f_1\) сводится к функции \(f_2\), если существует функция \(f \in P\), такая, что для любого \(x\)  \(f_{1}(x)=f_{2}(f(x))\).

Задача T называется NP-полной, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и  скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула приняла значение "истина".

Задача T называется NP-трудной, если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи \(R_1\) к \(R_2\) по Куку - это полиномиальный по времени алгоритм, решающий задачу \(R_1\) при условии, что функция, находящая решение задачи \(R_2\), ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.

Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP):




Вот еще 2 примера NP-полных задач.

Задача о рюкзаке. Даны объемы \(w_1, ..., w_n \in N\) и стоимости \(v_1, ..., v_n \in N\) набора из \(N\) предметов. Также даны общий объем \(W\) и число \(g\). Необходимо найти множество предметов из набора, общий объем которых не превышает \(W\), а общая стоимость не превышает \(g\).

Задача о коммивояжере. Дано \(n\) вершин с номерами \(1,...,n\) и все \(n(n-1)/2\) попарных расстояний между ними, а также число \(b\). Найти цикл, проходящий через все вершины ровно по одному разу и имеющий длину не более \(b\), или же сообщить, что такого цикла нет. Другими словами, необходимо найти перестановку \(\tau(1), ..., \tau(n)\) вершин такую, что \(d_{\tau(1)} + ... + d_{\tau(n)} \leq b \).

Для нахождения решений NP-трудных задач в худшем случае требуется осуществить полный перебор всех вариантов, при этом часто нужно генерировать все возможные перестановки и проверять их на удовлетворение некоторого свойства.
Время выполнения задач, решение которых связано с перестановками, быстро выходит из-под контроля потому, что число всех возможных перестановок сильно растет с возрастанием количества элементов перестановки. Например, для множества из 5 элементов можно сгенерировать 5!=5*4*3*2*1=120 перестановок, а для множества из 6 элементов перестановок сгенерируется уже в 6 раз больше, и т.д.

Во многих случаях для решения таких задач используются эвристические подходы, которые гарантируют не оптимальное, но рациональное решение.

Информационные источники:
O большое и o малое (википедия)Complexity and Big-O notations notesAlgorithmic ComplexityОб использовании символов o и OЛогарифм (википедия)Coursera course on Algorithms and Data structures, Part1 (презентация)Algolist. Оценки времени выполненияфорум RSDNАлгоритмы для NP-трудных задач (презентация)P_(complexity) (wikipedia)NP_(complexity) (wikipedia)Полиномиальная сводимостьЗадача выполнимости булевых формул (википедия)Сведение по Куку (википедия)Доклад "Переборные задачи"форум ixbtАбрамов. Лекции о сложности алгоритмов

среда, 1 мая 2013 г.

Основы интернет-технологий

Это шпаргалка для тех, кто "много знает, но ничего не помнит":



Введение

WWW - коллекция HTML-документов (была изобретена в 1990-х гг.). HTTP - основной протокол, используемый в интернете. Протоколы - стандарты (правила), которые определяют, каким образом будут обмениваться данными различные программы. Серверы - компьютеры, которые владеют файлами, из которых и состоит интернет. Интернет - самая большая в мире компьютерная сеть. Браузер - программа, выполняющаяся на компьютере пользователя и позволяющая отображать файлы, найденные в сети. 

Большинство веб-страниц создаются при помощи языка HTML. Инструкции HTML включают:
- текст (plain text),
- разметка (с помощью тегов),
- ссылки на другие документы, рисунки, видео, веб-страницы.

Запрос к серверу и ответ сервера

URL (Uniform Resource Locator).

Как удаленный компьютер может достучаться до конкретной программы на вашем компьютере? Ведь программ много, а IP-адресов мало. Для этого и придумали порты. Порт - набор цифр. Программа может "открыть" порт - т.е. заявить во всеуслышание что-то типа "если придет информация на порт 5190 - знайте, это для меня". "Закрыть" порт - значит взять свои слова обратно. 

Каждое HTTP-сообщение состоит из 3 частей:
- стартовая строка,
- заголовок,
- тело сообщения. 

Стартовая строка запроса выглядит так: Метод URI HTTP/Версия. Например:
GET /wiki/HTTP HTTP/1.0

Наиболее распространенные методы: GET и POST. URI определяет путь к запрашиваемому документу. 

Заголовки имеют следующий формат: имя: значение. Наиболее популярные заголовки: 

Host: www.example.com
User-Agent: chrome

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

Стартовая строка ответа сервера имеет следующий формат: HTTP/Версия КодСостояния Пояснение. Например: HTTP/1.1 200 OK. Наиболее популярные коды состояний: 

2xx - все отработало хорошо, 
3xx - нужно еще кое-что сделать, 
4xx - ошибка со стороны браузера, 
5xx - ошибка со стороны сервера.

Наиболее частыми заголовками HTTP-ответов являются следующие (см. пример ниже):

HTTP/1.1 200 OK
Date: Tue Mar 2012 04:33:33 GMT
Server: Apache /2.2.3
Content-type: text/html
Content-length: 1539 

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

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

Об устройстве Интернета

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


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

Маршрутизатор (или роутер) - сетевое устройство, пересылающее пакеты данных между различными сегментами сети, принимающий решения о пересылке на основе информации о топологии сети и определенных правил, заданных администратором. Обычно маршрутизатор использует адрес получателя, указанный в данных, и определяет по таблице маршрутизации путь, по которому следует передать данные. Если в таблице маршрутизации для адреса нет описания маршрута, данные отбрасываются. Таблица маршрутизации - файл или база данных, которая обычно включает адрес сети получателя, адрес следующего узла, куда нужно отправить данные, метрику - числовой показатель, задающий предпочтительность маршрута. Таблица маршрутизации может составляться двумя способами: 1) статическая маршрутизация - записи в таблице вводятся и изменяются вручную, 2) динамическая - записи обновляются автоматически с помощью одного или нескольких протоколов маршрутизации.

Модель OSI

Модель OSI - модель взаимодействия сетевых протоколов (7 уровней, верхний - прикладной, нижний - физический). Как работают протоколы согласно этой модели? Данные попадают на прикладной уровень, к ним добавляется еще один заголовок. На следующем уровне добавляется еще один заголовок и т.д. (также данные могут дробиться на более мелкие куски) и так до физического уровня. Получившаяся совокупность данных отправляется в сеть. Другая машина, получив кусок этих данных, начинает убирать заголовки. На каких-то уровнях может быть ожидание и сбор из нескольких кусков данных одного куска. Также данные могут отвергаться (например, если MAC-адрес устройства / IP-адрес не соответствует требуемому, или вычисленная контрольная сумма полученных данных не соответствует заявленному значению). Получившиеся данные без служебной информации добираются до прикладного уровня. Отметим, что передача данных не обязательно должна начинаться и заканчиваться 7 уровнем, например, компьютер использует все 7 уровней, а маршрутизатор только 3 нижних уровня. Уровни с прикладного по канальный (LLC) реализованы на уровне программ, уровни канального (MAC) и физического - на уровне железа.

Вкратце пробежимся по уровням OSI. 

7. Прикладной уровень. Осуществляет связь пользовательских приложений с сетью: просмотр веб-страниц (HTTP), передача и прием почты (SMTP, POP3), прием и получение файлов (FTP) и т.д.

6. Уровень представления. Преобразует файлы в биты. Этот файл работает со стандартами изображений (JPEG, GIF и т.д.), кодировок, музыки и видео (MPEG) и т.д.

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

4. Транспортный уровень обеспечивает надежность передачи данных от отправителя к получателю. Если вы общаетесь с помощью веб-камеры со своим другом, то здесь надежная доставка каждого бита переданного изображения не нужна. Если потеряется несколько бит из потокового видео, вы даже этого не заметите. Надежная доставка нужна при закачке архива, отправке пароля на сервер, чтении текста с веб-страницы. 2 протокола:  UDP и TCP. UDP протокол передает данные без установления соединения, не подтверждает доставку данных и не делает повторы. TCP протокол делает все наоборот и поэтому гарантирует целостность и правильность загруженных данных. Данные: сегменты

3. Сетевой уровень определяет путь, по которому данные будут переданы. Данные: пакеты. На этом уровне работают маршрутизаторы и IP-протокол. IP адреса называются логическими.

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

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

2. Канальный уровень - нужен для взаимодействия сетей на физическом уровне. Устройства канального уровня: коммутаторы, концентраторы. Делится на 2 подуровня: LLC - взаимодействие с верхним уровнем, MAC - взаимодействие с нижним уровнем. Пример: в компьютере имеется сетевая карта (или какой-то другой адаптер). Для взаимодействия с ней существует драйвер Драйвер - верхний подуровень канального уровня, через который можно связаться с нижними уровнями, а точнее с микропроцессором (железо) - нижний подуровень. Пример протокола: PPP (Point-to-Point) - протокол для связи двух компьютеров напрямую. Данные: кадры.

1. Физический уровень. Протоколы: Bluetooth, Wi-Fi, медные провода и т.д. Здесь биты преобразуются в импульсы и наоборот. 

От сетевой модели OSI модель TCP/IP отличается количеством уровней. Сетевая модель TCP/IP была разработана значительно ранее модели OSI. Модель TCP/IP сформировывалась уже на существующих протоколах, а вот OSI - наоборот, сначала была создана модель, а потом протоколы под нее. Вкратце, уровни 7-4 OSI соответствуют "уровню приложений" модели TCP-IP, уровни 2-1 OSI соответствуют "уровню доступа к сети".

DNS

Служба доменных имен (DNS) относится к прикладному уровню модели TCP-IP. Переводит IP-адреса в более удобочитаемый формат, а также обеспечивает независимость от физического IP-адреса хоста (если владелец сайта сменит хост, вы этого даже не заметите). Доменом называют множество хостов, объединенных в логическую группу. Когда приложение, запущенное на машине клиента, хочет обратиться к хосту по имени, то это имя передается распознавателю, который запущен на клиентской машине. Распознаватель обращается с запросом к одному из локальных DNS серверов. Если DNS сервер не имеет информации о запрашиваемом домене, он посылает сообщение с запросом серверу домена более высокого уровня. Для повышения эффективности обработки запросов DNS-серверы часто кэшируют информацию.

Прочее

Front-end отвечает за получение ввода (входной информации) в любых формах от пользователя и обработку полученной информации в ту форму, которую back-end способен использовать. Front-end — это интерфейс между пользователем и back-end’ом. Примеры языков и библиотек front-end: HTML, CSS,Javascript, jQuery. Примеры языков и библиотек back-end: python, фреймворк Django, SQLite.

При загрузке веб-страницы браузер загружает картинки, стили и другие файлы параллельно.  Но количество одновременных "потоков" для одного хоста ограничено. То есть,  если у вас на странице 50 объектов,  то браузер начнет грузить сначала первые 5, потом следующие 5 и так пока все не загрузит. Поэтому если положить картинки сайта на другой домен - то веб-страницы сайта будут загружаться быстрее, т.к. вырастет число хостов, соответственно и вырастет количество одновременных соединений.