Введение в Python и обработку данных

Спецкурс кафедры Теоретической информатики мехмата МГУ

Подробная информация по курсу: http://rmbk.me/mm_python/

Лекция 6: контейнеры данных и функции

Хеширование (вики)

Хеш-функция позволяет от объекта произвольного размера получить объект фиксированного размера, чаще всего — число.

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

По умолчанию в CPython хешом берётся каким-то образом зарандомизированный адрес в памяти.

In [ ]:
# help(hash)

print(hash(1))
print(hash(1000000))
print(hash(1000000000000000000000))
print(hash(1.5))
In [ ]:
a = (1, 2, 3)
print(hash(a))
a = 'Hello'
print(hash(a))

Словарь / Dict

Словари позволяют хранить данные в формате ключ-значение (key-value). Доступ к значению по ключу осуществляется за константное время, то есть не зависит от размера словаря. Это достигается с помощью хеширования.

https://docs.python.org/3/tutorial/datastructures.html#dictionaries

In [ ]:
# help(dict)

# Две эквивалентные записи для создания пустого словаря
a = dict()
a = {}

# Можно создавать сразу заполненный словарь
a = {
    'I': 1,
    'V': 5,
    'X': 10,
}

# Доступ происходит как к элементам списка, но по ключу
a['L'] = 50
print(a['L'])

# Если обратиться к отсутствующему ключу, то будет KeyError
# Можно проверять наличие ключа оператором `in`
print('L' in a)

# А можно использовать .get, который не вызывает ошибки
print(a.get('C'))  # Вернет None, т.к. не найдет такого ключа
print(a.get('C', 0))  # Вернет 0 как дефолтное значение
In [ ]:
# Можно удалять из словаря ключи
a['C'] = 100
del a['C']

# Или делать .pop, который еще и вернет значение перед удалением
a['C'] = 100
print(a.pop('C'))
In [ ]:
# Добавлять значения можно и через другой словарь
b = {
    'C': 100,
}
a.update(b)

print(a)
In [ ]:
# Как и другие контейнеры словарь поддерживает протокол итерации
print('Итерация по ключам словаря:')
for key in a:
    print(key, end=' ')

print('\n')
print('Итерация по значениям словаря:')
for value in a.values():
    print(value, end=' ')
    
print('\n')
print('Итерация по ключам и значениям словаря:')
for key, value in a.items():
    print(key, value)
In [ ]:
# Задачка! Вывести 5 самых часто встречающихся символов и слов из текста:
zen = """The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!
"""

# Пиши код здесь:
from operator import itemgetter

d = {}
for symbol in zen:
    if not symbol in d:
        d[symbol] = 0
    d[symbol] += 1

print(sorted(d.items(), key=itemgetter(1), reverse=True)[:5])

d = {}
for word in zen.split():
    word = word.strip('*,.!-').lower()
    if not word in d:
        d[word] = 0
    d[word] += 1
    
print(sorted(d.items(), key=itemgetter(1), reverse=True)[:5])

Множество / Set

Множество в Python это неупорядоченный набор уникальных элементов. Чаще всего используются для удаления дубликатов и проверок на вхождение.

https://docs.python.org/3/tutorial/datastructures.html#sets

In [ ]:
# help(set)

# Создание пустого множества, сокращения для пустого нет
a = set()

# Создание заполненного множества, краткая запись похожа на словарь, но без двоеточий
a = set([1, 2, 3])
a = {1, 2, 3}

# Проверка на вхождение, O(1)
print(1 in a)

# Добавление в множество
a.add(4)

# Удаление из множества
a.remove(4)

# Удаление и взятие одного из элементов, когда не важно какой
print(a.pop())
In [ ]:
# По множествам можно итерироваться
for i in a:
    print(i)
In [ ]:
# Множества в Python поддерживают стандартные операции над множествами
a = {1, 2, 3}
b = {3, 4, 5}

print('Union:', a | b)  # Другая запись: a.union(b)
print('Intersection:', a & b)  # Другая запись: a.intersection(b)
print('Difference:', a - b)  # Другая запись: a.difference(b)
print('Symmetric difference:', a ^ b)  # Другая запись: a.symmetric_difference(b)
In [ ]:
# Задачка! Через сколько итераций random.randint(1, 100) даст повтор?
import random

# Пиши код здесь:
a = set()
while True:
    number = random.randint(1, 100)
    if number in a:
        break
    a.add(number)

print(f'Повтор случился через {len(a)} итераций')

Модуль collections

Модуль collections содержит дополнительные удобные контейнеры:

  • defaultdict — dict subclass that calls a factory function to supply missing values
  • Counter — dict subclass for counting hashable objects
  • namedtuple — factory function for creating tuple subclasses with named fields
  • deque — list-like container with fast appends and pops on either end
  • ChainMap — dict-like class for creating a single view of multiple mappings
  • OrderedDict — dict subclass that remembers the order entries were added

https://docs.python.org/3/library/collections.html

https://pythonworld.ru/moduli/modul-collections.html

Collections: defaultdict

Класс defaultdict это словарь, но с заданным дефолтным "конструктором" — factory. https://docs.python.org/3/library/collections.html#collections.defaultdict

In [ ]:
from collections import defaultdict

d = defaultdict(int)  # Если ключ отсутствует, то значением автоматически станет дефолт: int(), т.е. 0
for symbol in zen:
    d[symbol] += 1
    
print(d)
In [ ]:
# Задачка! Посчитать какая длина слова встречается чаще всего в zen и вывести слова с такой длиной

# Пиши код здесь:
d = defaultdict(set)
for word in zen.split():
    word = word.strip('!.,-*').lower()
    d[len(word)].add(word)

print(d)

Collections: Counter

Класс Counter помогает в задачах "подсчёта" чего-либо https://docs.python.org/3/library/collections.html#collections.Counter

In [ ]:
from collections import Counter

# Counter принимает на вход Iterable объект (по которому можно итерироваться) 

counter = Counter(zen)
print(counter.most_common(10))

counter = Counter([word.lower().strip('*.,-!') for word in zen.split()])
print(counter.most_common(10))

Функции в Python

Что уже знаем:

  • функция это блок кода, который мы можем использовать в других частях программы
  • функции по стандарту PEP8 называют в snake_case, т.е. в нижнем регистре с нижними подчеркиваниями
  • в функции стоит выносить одну смысловую часть, т.е. делать одну конкретную задачу
  • функции в Python это тоже объект
In [ ]:
def convert(a: str) -> list:
    """Return integers converted from string"""
    return [int(i) for i in a.split() if i.isdigit()]

Здесь есть два новых момента

  • документация к нашей функции
  • аннотация типов (с Python 3.5)
In [ ]:
help(convert)
In [ ]:
print('Function docstring:', convert.__doc__)

print('Function name:', convert.__name__)

print('Other:', dir(convert))
  • Аннотации имеют рекомендативный характер и никак не влияют на исполнение кода.

  • Делаются они с помощью двоеточия для аргументов и стрелочки для возвращаемого значения.

  • Подробнее про аннотации: https://docs.python.org/3/library/typing.html

In [ ]:
def add(x: int, y: int) -> int:
    return x + y

print(add(4, 5))
print(add('still ', 'works'))

Стоит запомнить

  • В Python каждая переменная является связью имени с объектом в памяти
  • Именно эта ссылка передается в функцию (например, в С++ можно выбирать что передавать: ссылку или объект)
  • Таким образом, изменяемые объекты внутри функции меняются и снаружи, а неизменяемые — обновляются только внутри функции (!)
In [ ]:
def incrementer(a: list):
    for i in range(len(a)):
        a[i] += 1

a = [1, 2, 3]
print(a)
# Список меняется внутри функции, но это тот же список, что и снаружи
incrementer(a)  
print(a)
In [ ]:
def replacer(a: str) -> str:
    a = a.replace('T', 'U')
    
a = 'ATUG'
print(a)
# Мы меняем строку на другую внутри функции, но ссылка снаружи осталась предыдущей
replacer(a)
print(a)
In [ ]:
# Для таких случаев в Python используют возвращаемые значения
def replacer_good(a: str) -> str:
    return a.replace('T', 'U')

a = 'ATUG'
print(a)
# Мы меняем внешний объект на другой
a = replacer_good(a)
print(a)

Именованные аргументы

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

In [ ]:
def say(name, greeting):
    print(f'{greeting}, {name}')
    
say('Kitty', 'Hello')
say(greeting='Hello', name='Kitty')
say(name='Kitty', greeting='Hello')

Аргументы по умолчанию

In [ ]:
def say(name, greeting='Hello'):
    print(f'{greeting}, {name}')

say(name='Kitty')
say(name='Kitty', greeting='Hi')

Важно запомнить

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

In [ ]:
def append_one(a=[]):
    a.append(1)
    return a

# Вроде рабоает правильно...
print(append_one([2]))

# А если вызовем с дефолтным значением несколько раз?
print(append_one())
print(append_one())
print(append_one())
In [ ]:
def append_one_good(a=None):
    a = a or []        
    a.append(1)
    return a

print(append_one_good([2]))

# А теперь всё хорошо!
print(append_one_good())
print(append_one_good())
print(append_one_good())

Переменное количество аргументов

In [ ]:
def f(*args, **kwargs):
    print(type(args))
    print(type(kwargs))

f()
In [ ]:
def printer(*args, **kwargs):    
    for arg in args:
        print(arg)
        
    for key, arg in kwargs.items():
        print(key, arg)
    
print('--- 1:')
printer(1, 2, 3)

print('--- 2:')
printer(ololo=True, name='Kitty')

print('--- 3:')
printer('first', second=True, name='Kitty')
In [ ]:
def my_max(*args):
    if len(args) == 0:
        return None
    m = args[0]
    for i in args:
        if m < i:
            m = i
    return m

print(my_max(1, 2, 3))
print(my_max(1, 2, 3, 4, 5))

Использование внешних API

Дополнительный материал к лекции для иллюстрации вариаций проектов.

Существует множество открытых API с разным функционалом: https://github.com/toddmotto/public-apis

In [ ]:
import sys

# Установка пакета requests прямо из ноутбука
!{sys.executable} -m pip install requests --user
In [ ]:
import requests

# Пример с календарём российских праздников и выходных
resp = requests.get('https://datazen.katren.ru/calendar/day')
d = resp.json()

print(type(d))
print(d)
In [ ]:
# Пример со скачиванием случайной фотографии кота
resp = requests.get('https://aws.random.cat/meow')
cat_url = resp.json()['file']
cat = requests.get(cat_url)
filename = 'cat.' + cat_url.split('.')[-1]

with open(filename, 'wb') as file:
    file.write(cat.content)

Наш скачанный котик:

Домашнее задание №6

Опциональное

Собрать команду и придумать идею проекта