GitHub Python Bar Review

Контейнеры 1

1. О контейнерах

Контейнер — объект, который содержит внутри себя другие объекты. Технически все контейнеры наследуют от Collections.abc.Container метод __contains__. С этим методом работает оператор in.

Контейнеры представлены разными структурами данных. На этих структурах можно построить всевозможные абстрактые типы данных.

NB! Не надо путать типы данных со структурами данных и абстрактными типами данных.

Тип данных — характеристика кусочка данных, которая определяет способ его интерпретации. Например, b1100001 может быть как число 97 (целый тип), а может быть как символ a из ASCII (символ).

Структура данных — набор из примитивов данных и операций над ними, огранизованные для эффективного решения задачи. Например, массив) или связный список.

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

Проблема копирования контейнеров

В Python присваивание = копирует только ссылки объектов. И опреацию вида name = obj можно интерпретировать как присваивание объекту obj имени name. Как в таком случае скопировать объект?

Для примера, давайте попробуем скопировать список списков.

# Пример списка списков
a = [1,2,3]
b = [4,5,6]
c = [a,b] # содержит ссылки на a и b

Если мы список c присвоим списку d, то по факту у списка [a,b] просто будет два имение c и d.

# Навешиваем новое имя списку с (у обеъектов даолжны быть одинаковые id)
d = c
id(c), id(d)

(4508213760, 4508213760)

Можно скопировать список, создав явно новый с содержимым старого. При этом происходит поверхностное копирование списка. Элементы указывают на элементы старого списка.

# Поверхностное копирование списка (списки разные, но внутренние объекты нет)
d = list(c)
id(c), id(d), id(c[0]), id(d[0])

(4508213760, 4508896768, 4507249728, 4507249728)

Различают два типа копирования:

• Поверхностное (англ. shallow)
• Глубокое (англ. deep)

В отличии от поверхностного копирования, глубокое обходит объект рекурсивно и копирует все подобъекты.

# Глубокое копирование списка
from copy import deepcopy
d = deepcopy(c)
id(c), id(d), id(c[0]), id(d[0])

(4508213760, 4507242880, 4507249728, 4508854144)

2. Built-in контейнеры

Встроенные в Python-контейнеры можно разделить на две категории:

• неизменяемые (англ. immutable) string, tuple, range, frozenset, bytes
• изменяемые (англ. mutable) list, dict, set, bytearray

# Встроенные контейнеры:
c_str = "Еду в магазин в городе Санкт-Петербурге"
c_tpl = (1, 1.2, "я")
c_rng = range(10)
c_fst = frozenset({1,2,3}) # readonly set
c_bts = bytes((3,1,4,5,1,5))
c_lst = [1,2,3]
c_dct = {1: "Sex", 2: "Drugs", 3: "Rock-and-Roll"}
c_set = {1,2,3}
c_bar = bytearray((3,1,4,5,1,5)) # writable bytes

О сложности операций над популярными контейнерами

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

Контейнер	List		Tuple		Dictionary		Set
Пустой контейнер	[]	$O(1)$	()	$O(1)$	{}	$O(1)$	Set() или {()}	$O(1)$
Прочитать элемент	l[i]	$O(1)$	t[i]	$O(1)$	d[key]	$O(1)$	undefined	undefined
Добавить элемент	l.append(5)	$O(1)$	undefined	undefined	d[key]=5	$O(1)$	s.add(5)	$O(1)$
Удалить элемент	del l[i]	$O(N)$	undefined	undefined	del d[key]	$O(1)$	s.discard(5)	$O(1)$

О хэшируемости

Объекты в Python могут быть хэшиуруемые — таким объектам сопоставляется некоторое число (хэш), которое не меняется в течении существования объекта. Хэши используются для сравнения ключей в словарях и множествах. Технически, у хэшируемых объектов реализован метод __hash__().

NB! Если контейнер и его элементы неизменяемые, то он хэшируемый.

# Хэшируемый кортеж
hash((1,3,()))

7764519317587398582

# Нехэшируемый кортеж (должна быть ошибка)
hash((1,3,[]))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-cbf3b29f821f> in <module>
      1 # Нехэшируемый кортеж (должна быть ошибка)
----> 2 hash((1,3,[]))

TypeError: unhashable type: 'list'

3. Крутые контейнеры

Ниже приведены некоторые контейнеры из стандартной библиотеки со специальным назначением.

namedtuple — когда нужен «сишный struct»

# Пример именованного кортежа
from collections import namedtuple 
Point = namedtuple('Point', ['x', 'y'])
p = Point(1,2)

# К полям namedtuple можно обращаться через точку.
p.x

1

# Также можно читать как обычный кортеж.
p[0]

1

# Итерирование по именованному кортежу
for x in p:
    print(x)

1
2

# Именованный кортеж — неизменяемый объект (должна быть ошибка)
p.x = 4

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-12-4ffc5fe135f6> in <module>
      1 # Именованный кортеж — неизменяемый объект (должна быть ошибка)
----> 2 p.x = 4

AttributeError: can't set attribute

NB! namedtuple удобно использовать для возврата данных из функций.

OrderedDict — когда важен порядок в словаре

Update: В Python 3.7 уже не актуально. Стандартный dict гарантирует порядок.

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

# Операция реверса на словаре бесмысленна — порядка нет (должна быть ошибка)
dict_std = {"a": 1, "b": 2, "c": 3}
[k for k in reversed(dict_std)]

['c', 'b', 'a']

# Рабочий workaround в Python 3.7+
dict_std = {"a": 1, "b": 2, "c": 3}
[k for k in reversed(list(dict_std.keys()))]

['c', 'b', 'a']

# OrderedDict предполагает наличие порядка, можно перевернуть
from collections import OrderedDict 
dict_odr = OrderedDict({"a": 1, "b": 2, "c": 3})
[k for k in reversed(dict_odr)]

['c', 'b', 'a']

defaultdict — когда лень инициализировать ключи

Если обратиться к ключу словаря, которого нет, то будет ошибка.

# Обычный словарь ругается на поля, которых нет (должна быть ошибка)
d = {}
d["4"]

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-16-c9aa461dd7f1> in <module>
      1 # Обычный словарь ругается на поля, которых нет (должна быть ошибка)
      2 d = {}
----> 3 d["4"]

KeyError: '4'

Если надо какое-то поведение по-умолчанию, то для этого удобно использовать defaultdict.

# Пример с defaultdict, ключу по-умолчанию присвается 0.
from collections import defaultdict

s = 'я заливаю глаза керосином'
d = defaultdict(int)

for k in s:
    d[k] += 1 # без defaultdict здесь надо было  бы инициализировать ключи явно

sorted(d.items(), key=lambda x: x[1], reverse=True)

[('а', 4),
 (' ', 3),
 ('з', 2),
 ('л', 2),
 ('и', 2),
 ('о', 2),
 ('я', 1),
 ('в', 1),
 ('ю', 1),
 ('г', 1),
 ('к', 1),
 ('е', 1),
 ('р', 1),
 ('с', 1),
 ('н', 1),
 ('м', 1)]

ChainMap — когда нужно несколько словарей представить как один

ChainMap хранит ссылки на другие словари. Контейнер позволяет работать с внутренними словарями как с одним целым словарем.

У ChainMap есть два традиционных приложения:

• Возвращать значения по-умполчанию из словаря, если ключа нет.
• Поиск по нескольких словарям.

# Пример с ChainMap: поиск по двум словарям
from collections import ChainMap

group1 = {"a": 1, "b": 2}
group2 = {"c": 3, "d": 4}
groups = ChainMap(group1, group2)
groups["d"], groups["b"]

(4, 2)

Здесь group1 может быть словарём параметров, а group2 — словарём значений параметров по-умолчанию. Если значения нет в group1, то вернётся значение из group2.

MappingProxyType — когда нужен словарь только для чтения

# Пример словаря, в который нельзя писать
from types import MappingProxyType

d = {"a": 1, "b": 2} # Обычный словарь
d_ro = MappingProxyType(d) # MappingProxyType (Read Only)

d_ro["a"]

1

# Записать в MappingProxyType нельзя (должна быть ошибка)
d_ro["a"] = 1

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-20-819d3d450b91> in <module>
      1 # Записать в MappingProxyType нельзя (должна быть ошибка)
----> 2 d_ro["a"] = 1

TypeError: 'mappingproxy' object does not support item assignment

Counter — когда надо мультимножество

Мультимножество — множество, элементы в котором могут повторяться.

# Пример построения мультимножества по итерируемому объекту (строке)
from collections import Counter

s = 'я заливаю глаза керосином'
c = Counter(s)
c

Counter({'я': 1,
         ' ': 3,
         'з': 2,
         'а': 4,
         'л': 2,
         'и': 2,
         'в': 1,
         'ю': 1,
         'г': 1,
         'к': 1,
         'е': 1,
         'р': 1,
         'о': 2,
         'с': 1,
         'н': 1,
         'м': 1})

# sum — количество элементов в множестве, 
# len - количество уникальных элементов в множестве
sum(c.values()), len(c.values())

(25, 16)

deque — когда нужен двусторонний доступ

И очередь и стек можно реализовать на list. Но list реализован на динамическом массиве, а deque на связном списке.

# Пример двусторонней очереди
from collections import deque
d = deque()
d.append("я")
d.append("иду")
d.append("брать")
d.append("лут")
d.popleft(), d.pop()

('я', 'лут')

heapq — когда нужна очередь с приоритетом

# Пример
from heapq import heappush, heappop

q = []
heappush(q, (3, "Продакшен"))
heappush(q, (1, "Чпок"))
heappush(q, (2, "Чпок"))

heappop(q),heappop(q),heappop(q)

((1, 'Чпок'), (2, 'Чпок'), (3, 'Продакшен'))

dataclasses — когда от класса надо только хранение данных

Когда нужен изменяемый namedtuple, то подходит dataclasses.

# Пример с собственным dataclass
from dataclasses import dataclass

@dataclass
class Structure:
    name: str
    value: float

    @property
    def square(self) -> float:
        return self.value * self.value
    
s = Structure("я", 2)
s.square

4

По-умолчанию dataclass генерирует 3 дандер-метода (метод с двойным подчеркиванием):

• init,
• repr,
• eq.

Через опции декоратора можно сделать dataclass immutable (frozen), mutable-хэшируемым (unsafe_hash) и сравниваемым (order).

%load_ext watermark
%watermark -d -u -v -iv

last updated: 2019-10-21 

CPython 3.8.0
IPython 7.8.0