- У этого курса -- две темы (а на самом деле, всё поле между ними):
  изучение полезных возможностей python и изучение базовой теории
  программирования.

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


Массивы
=======

- Зададимся вопросом: как компьютер представляет в памяти массивы.

- Для этого нам потребуется придумать модель того, как устроена память
  компьютера. Условимся считать, что память -- это такая лента, на
  которой есть ячейки, в которые можно класть значения. (Это упрощение,
  но близкое к жизни: мы закрываем глаза на то, что на самом деле под
  одну английскую букву, одно целое число и одно число с плавающей
  точкой компьтер скорее всего будет использовать разное количество
  памяти). Ячейки памяти пронумерованы. Номер ячейки называется адресом
  в памяти.

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

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

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

- Посмотрим, какие операции мы можем выполнять с массивом, и какие с
  ними связаны расходы.

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

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

- На самом деле, время работы программы нас интересует только тогда,
  когда оно большое.

- Поэтому применяют такой подход: выбирают базовый набор операций,
  каждая из которых заведомо выполняется за одинаковое время всегда, и
  считают *приблизительно* сколько таких операций потребуется в худшем
  случае для больших входных данных. Ответ при этом выражают в виде
  O(f(n)), где f(n) -- время работы, а O(f(n)) обозначает какую-то
  (заранее нам не известную) функцию g, такую что для всех достаточно
  больших n верно, что g(n) < a * f(n) + b. Т.е. мы при этом игнорируем
  возможно требуемые подготовительные операции вначале или в конце (за
  них отвечает константа b) и тот факт, что при переводе в разные
  единицы измерения (секунды или такты одного конкретного процессора)
  нам придётся ответ домножать на разные величины.

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

- Получаем:

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

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

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

 - Для того, чтобы удалить элемент из массива, нужно: пойти по адресу,
   где лежит длина массива, взять оттуда значение, вычесть из него
   единицу, положить на место, вычислить адрес элемента, вычислить адрес
   следующего за ним элемента, положить следующий элемент в удалённый,
   потом послеследующий в следующий, потом послепослеследующий в
   послеследующий и т.п. Т.е. нам нужно сдинуть весь остаток массива по
   одному элементу за раз (других операций у нас нет). Получается
   сложность: O(3+2*(len(array) - m)), где len(array) -- длина массива, m
   -- номер элемента, который мы хотим удалить. Так как прибавление
   константы к времени нас не волнует (оно всё равно потеряется при
   представлении времени в других единицах измерения), то мы можем
   сказать, что сложность операции: O(2*(len(array) - m)). Снова,
   умножение времени на константу нас тоже не интересует. Можем упростить
   дальше: O(len(array) - m). Так как нас интересует сложность операции в
   худшем случае, то для простоты мы можем задать заведомо избыточную
   верхнюю границу: O(len(array)). В самом худшем случае нам потребуется
   сделать по скольку-то действий на каждый элемент массива.

 - Для добавления элемента массива нам придётся просить новую память
   (и её нужно будет побольше, чтобы туда влез и нынешний массив, и
   добавляемый элемент), потом копировать в неё массив и по пути в
   какой-то момент вставлять туда элемент. В качестве упражнения для
   желающих оставляю показать, что в O(len(array)) операций мы здесь
   уложиться заведомо можем. Довольно очевидно, что в меньшее число
   операций уместиться не удастся.


Односвязные списки
==================

- Попробуем сочинить другое представление. Давайте хранить пары из
  элемента и адреса следующего за ним элемента. Ещё нам потребуется
  какое-то значение, которое мы можем использовать для обозначения того,
  что за данным элементом в списке следующего нет. В питоне это значение
  None. Такое представление последовательности значений называется
  односвязным списком.

- Для такого представления данных нам имеет смысл говорить о несколько
  другом наборе операций: нам интересно уметь выкинуть из списка первые
  m элементов, дописать один элемент перед списком, дописать один
  элемент после первого элемента, узнать длину списка. (Это наиболее
  примитивные операции, которые можно делать с односвязными списками, а
  операции вроде "заменить элемент по номеру" уже являются составными.
  Нас, разумеется, интересует время наиболее примитивных операций,
  потому, что мы как правило можем модифицировать алгортм, которым мы
  решаем нашу задачу так, чтобы он этим пользовался).

 - Для того, чтобы узнать длину списка, у нас нет никакой идеи лучше,
   чем взять адрес первого элемента, посмотреть, является ли он последним
   (т.е. не указывает ли его ссылка на следующий элемент на None), если
   не является, то перейти по адресу к второму элементу, снова
   посмотреть, является ли он последним, и т.п. То есть нам придётся
   подержать в руках каждый элемент массива и сделать для него один и тот
   же фиксированный набор операций. Получается, что нам требуется время:
   O(len(list) * n).

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

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

 - Для того, чтобы удалить из списка первые m элементов, нужно m раз
   взять адрес списка, получить из него адрес указателя на следующий
   элемент, и сказать, что это теперь адрес оставшегося списка. Т.е.
   сложность O(m).

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

Полезно знать, что в питоне тип list -- это массивы.


Инициализатор класса
====================

- Нам потребуется ещё одна полезная возможность питона: когда мы
  создаём новый объект класса, питон может автоматически вызвать метод
  этого класса дабы мы сразу получили готовый объект, в котором уже
  лежат все нужные нам атрибуты.

- Это устроено так: если питон видит в классе метод под названием
  __init__, то он вызывает его на вновь созданном объекте. Кроме того,
  если какие-то аргументы передавались конструктору класса, то они
  передадутся методу __init__. Например::

    class Noun(object):
        def __init__(self, word):
            self.word = word
            self.is_plural = False
            self.case = "nominative"
    
    >>> w = Noun("boy")
    >>> print w.word, w.case
    boy, nominative


Сбалансированные скобки
=======================

- Так как у односвязных списков дешевле всего операции с первым
  элементом списка (в том числе, добавление и удаление), как правило их
  используют для тех случаев, когда добавить элемент в начало списка и
  удалить элемент из начала списка -- это единственные две нужные
  операции. Списки, для которых определены только эти две операции,
  называют стэками. Их же называют LIFO-списками: last in first out.

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

- Хороший алгоритм для решения этой задачи такой: мы идём по тексту, и
  когда видим открывающую скобку (или кавычку), добавляем её в список
  увиденного, а когда видим закрывающую скобку, проверяем, лежит ли
  последней в списке увиденного парная к найденной (например, что скобка
  не закрывается кавычкой).

- Опишем очень простой класс для стэка::

    class Node(object):
        def __init__(self, value, next):
            self.value = value
            self.next = next

    class Stack(object):
        def __init__(self):
            self.stack = None
        def push(self, value):
            self.stack = Node(value, self.stack)
        def pop(self):
            value = self.stack.value
            self.stack = self.stack.next
            return value

С таким описанием мы можем выполнять, собственно, ровно две операции:
добавить элемент в начало списка и взять элемент с начала списка.

vim: et ts=4 sw=4 sts=4