Коллекции

Коллекции - это какие-то наборы объектов разного или одного типа. 100 кошек, 10 собак, набор - [арбуз, тыква, голый землекоп], - все это является коллекцией.

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

Словари

Часто перед нами встает задача по какому-то, нечисленному, значению, найти соответствующее ему другое значение. Например, по ФИО человека номер его паспорта

Словарь (dict) – это тип данных, хранящий соответствие одних значений другим (ключам словаря). Самым простым способом создания словаря является задание его при помощи фигурных скобок ({})

In [116]:
my_dict = { "Dmitry" : 5,
            "Alexander" : 10,
            "Jupyter": 20}
my_dict
Out[116]:
{'Alexander': 10, 'Dmitry': 5, 'Jupyter': 20}

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

In [117]:
my_dict['Jupyter']
Out[117]:
20

В случае, если ключа с таким значением нет, получите ошибку:

In [118]:
my_dict['Dogs']

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-118-027374e05090> in <module>()
----> 1 my_dict['Dogs']

KeyError: 'Dogs'

Можно использовать метод dict.get(key, default_value=None) для того, чтобы в случае отсутствия ключа в словаре получать какое-то значение по-умолчанию

In [119]:
print (my_dict.get("Dogs")) # return None 

None
In [120]:
my_dict.get("Dogs", 5)
Out[120]:
5
In [121]:
my_dict.get("Jupyter", 5)
Out[121]:
20

Проверка наличия ключа в словаре

Как и для других коллекций, для проверки наличия ключа в словаре используется слово in

In [122]:
if "Dogs" in my_dict:
    print("Hello")
else:
    print("World")

World

Проход по ключам словаря

Проход по ключам словаря можно сделать двумя способами

Учтите, что методы словаря, "возвращающие" хранимое в нем, возвращают не-совсем-списки, с этим нельзя работать как со списком

In [123]:
my_dict.keys()
Out[123]:
dict_keys(['Dmitry', 'Alexander', 'Jupyter'])
In [124]:
for key in my_dict.keys():
    print (key)

Dmitry
Alexander
Jupyter
In [125]:
for key in my_dict:
    print (key)

Dmitry
Alexander
Jupyter

Проход по значениям словаря

In [126]:
my_dict.values()
Out[126]:
dict_values([5, 10, 20])
In [127]:
for value in my_dict.values():
    print (value)

5
10
20

Проход по ключам и значениям словаря

In [128]:
for key in my_dict.keys():
    value = my_dict[key]
    print (key, value)

Dmitry 5
Alexander 10
Jupyter 20
In [129]:
my_dict.items()
Out[129]:
dict_items([('Dmitry', 5), ('Alexander', 10), ('Jupyter', 20)])
In [130]:
for key, value in my_dict.items():
    print (key, value)

Dmitry 5
Alexander 10
Jupyter 20
In [131]:
list(my_dict.keys())
Out[131]:
['Dmitry', 'Alexander', 'Jupyter']
In [132]:
list(my_dict.values())
Out[132]:
[5, 10, 20]
In [133]:
list(my_dict.items())
Out[133]:
[('Dmitry', 5), ('Alexander', 10), ('Jupyter', 20)]

Добавление элементов в словарь

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

In [134]:
d = dict() # another way to create dict
# d = {}
d[10] = "Hello"
d
Out[134]:
{10: 'Hello'}
In [135]:
d["hello"] = "world"
d
Out[135]:
{10: 'Hello', 'hello': 'world'}
In [136]:
d[10] = -100
d
Out[136]:
{10: -100, 'hello': 'world'}
In [137]:
my_key = "hi"
my_value = [1,2,3]
d[my_key] = my_value
d
Out[137]:
{10: -100, 'hello': 'world', 'hi': [1, 2, 3]}
In [138]:
d[[1,2,3]] = 5  

# error, list is mutable (unhashable, to be precise)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-138-63e2845468f0> in <module>()
----> 1 d[[1,2,3]] = 5
      2 
      3 # error, list is mutable (unhashable, to be precise)

TypeError: unhashable type: 'list'

Удаление элементов из словаря

In [139]:
a = {"A" : 0,
     "T" : 1, 
     "G": 2, 
     "C" : 3, 
     "G" : 4, 
     "U" : 5}
In [140]:
a
Out[140]:
{'A': 0, 'C': 3, 'G': 4, 'T': 1, 'U': 5}
In [141]:
del a['U']
a
Out[141]:
{'A': 0, 'C': 3, 'G': 4, 'T': 1}
In [142]:
del a['U']

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-142-a67e9e64d21f> in <module>()
----> 1 del a['U']

KeyError: 'U'

Можно использовать метод pop - он правильнее

In [143]:
a = {"A" : 0, "T" : 1, "G": 2, "C" : 3, "G" : 4, "U" : 5}
a.pop('U')
a
Out[143]:
{'A': 0, 'C': 3, 'G': 4, 'T': 1}
In [144]:
a.pop('U')

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-144-f443700df4c8> in <module>()
----> 1 a.pop('U')

KeyError: 'U'
In [145]:
a.pop('U', None)

А вот так делать нельзя!

In [146]:
a = {"A" : 0, 
     "T" : 1,
     "G": 2, 
     "C" : 3, 
     "G" : 4,
     "U" : 5}

for key in a.keys():
    if key == "C":
        a.pop(key)
    

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-146-6d1d906eb976> in <module>()
      6      "U" : 5}
      7 
----> 8 for key in a.keys():
      9     if key == "C":
     10         a.pop(key)

RuntimeError: dictionary changed size during iteration

Можно обойти проблему так:

In [147]:
a = {"A" : 0, "TC" : 1, 
     "G": 2, "CG" : 3, 
     "GC" : 4, "U" : 5}

keys = list(a.keys())
for key in keys:
    if "C" in key:
        a.pop(key)
a
Out[147]:
{'A': 0, 'G': 2, 'U': 5}

Порядок ключей в словаре

До версии Python3.5 включительно никто не гарантировал вам никакого порядка ключей в словаре. То есть то, как они вам выдавались функцией keys и т.д не зависело ни от порядка вставки элементов, не от результата их сравнения напрямую.

Однако с версии Python3.6 в наиболее распространненой реализации (CPython), а с версии Python3.7 - в любой, порядок ключей в словаре соответствует порядку их вставки в него. Если ключ уже существовал в словаре и вы его перезаписали, то порядок ключей не изменится.

In [1]:
a = {}
a[2] = 20
a[-10] = 3
a
Out[1]:
{2: 20, -10: 3}

Преимущества словарей

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

Недостатки словарей

Словари "кушают" много памяти. Все операции на словарях быстры в среднем — отдельная операция может длиться очень долго.

Кортежи

Если очень хочется сделать ключом словаря список, то нужно использовать не list, а другой тип данных — кортеж (tuple). Кортеж, на первый взгляд, отличается от списка только заменой квадратных скобок на круглые, например:

In [148]:
ta = (1, 2, 5, 4)
ta[0]
Out[148]:
1
In [149]:
a = (1)
print (a)

a = (1, )
print(a)

1
(1,)

Кортеж во многом похож на список, но главным отличием является то, что кортеж неизменяем.

In [150]:
ta[0] = 5

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-150-387a39ba50ab> in <module>()
----> 1 ta[0] = 5

TypeError: 'tuple' object does not support item assignment
In [151]:
dt = {}

dt[(1, 2)] = "Hello"
dt[(2, 1)] = "world"
dt
Out[151]:
{(1, 2): 'Hello', (2, 1): 'world'}
In [152]:
dt[(1,2)]
Out[152]:
'Hello'

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

urllib.request

In [2]:
import urllib.request
In [10]:
handle = urllib.request.urlopen("https://istina.msu.ru/workers/232537526/")
print(handle.readline())
print(handle.readline())
print(handle.readline())

b'\n'
b'\n'
b'<!DOCTYPE html>\n'

Возвращается строка в бинарном виде. Что с этим делать?

In [11]:
line = handle.readline()
print(line)

b'<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ru" lang="ru">\n'

Нам хватает того, что это работает.

In [12]:
line.decode()
Out[12]:
'<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ru" lang="ru">\n'

Функции

Функция - фрагмент программного кода, к которому можно обратиться из другого места программы

В Python функции задаются ключевым словом def.

In [23]:
def say_hello():
    print ("Hello")
    
say_hello()

Hello
In [3]:
def mod(a, b):
    return a % b

print (mod(3,4))

3
In [13]:
def wrong_mod(a, b):
    a % b

print (wrong_mod(3,4))

None

Функция может возвращать несколько значений, в этом случае она вернет их в качестве кортежа.

In [1]:
def s_pats(string, pats):
    ind = -1
    for p in pats:
        ind = string.find(p)
        if ind != -1:
            break
    return ind, p

res = s_pats("Hello, world", ["Hell", "world",
                              "happiness"])
print (type(res))
ind, p = res
print(ind, p)

<class 'tuple'>
0 Hell

Пример функции, реализующей факториал и вычисление n-го числа Фибоначчи

In [12]:
def factorial(n):
    acc = 1
    for i in range(2,n + 1):
        acc *= i
    return acc

def fibonacci(n):
    f0, f1 = 0, 1
    for i in range(n):
        f0, f1 = f1, f0 + f1
        # temp = f0
        # f0 = f1
        # f1 = f1 + temp
    return f0
In [13]:
print (factorial(5))
print (fibonacci(5))

120
5

Рекурсия

recursion

Python поддерживает механизм рекурсии - вызов функцией самой себя. Перепишем, например, предыдущие функции в рекурсивной форме

In [4]:
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

def fibonacci_rec(n):
    if n < 0:
        return 0
    
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    return fibonacci_rec(n - 1) + fibonacci_rec(n - 2)
In [7]:
print (factorial_rec(5))
print (fibonacci_rec(5))

120
5

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

factorial

Замедление из-за использования рекурсии

Здесь это объясняется тем, что рекурсия - допронительные расходы для приостановки работы функции и возвращении в нее после.

In [9]:
%%timeit
factorial(1000)

402 µs ± 851 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [8]:
%%timeit
factorial_rec(1000)

739 µs ± 14.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Здесь же все еще хуже

In [11]:
%%timeit
fibonacci(20)

1.9 µs ± 1.93 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
In [10]:
%%timeit
fibonacci_rec(20)

6.01 ms ± 35.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

У fibonacci сразу две проблемы - то, что есть необходимость приостановки функций, и то, что мы повторяем многие вычисления множество раз. Например, вычисление второго числа Фибоначчи на картинке будет осуществлено 3 раза.

С этим можно бороться, но это не тема этой лекции

fibonacci

Бесконечная рекурсия

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

In [17]:
def factorial_rec_no_exit(n):
    return n * factorial_rec_no_exit(n - 1)

factorial_rec_no_exit(10) # good night, sweet prince

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-17-0e60f9985128> in <module>()
      2     return n * factorial_rec_no_exit(n - 1)
      3 
----> 4 factorial_rec_no_exit(10) # good night, sweet prince

<ipython-input-17-0e60f9985128> in factorial_rec_no_exit(n)
      1 def factorial_rec_no_exit(n):
----> 2     return n * factorial_rec_no_exit(n - 1)
      3 
      4 factorial_rec_no_exit(10) # good night, sweet prince

... last 1 frames repeated, from the frame below ...

<ipython-input-17-0e60f9985128> in factorial_rec_no_exit(n)
      1 def factorial_rec_no_exit(n):
----> 2     return n * factorial_rec_no_exit(n - 1)
      3 
      4 factorial_rec_no_exit(10) # good night, sweet prince

RecursionError: maximum recursion depth exceeded

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

Достаточно часто встречается ситуация, когда большинство предпочтительных аргументов для функции известно (например, вы знаете, что ваш алгоритм лучше всего запускать с lambda = 0.73, а n_samples = 143). В таком случае, конечно, можно написать в комментариях к своей функции, но лучше воспользоваться аргументами по-умолчанию.

In [20]:
import random

def make_random_sequence(length=200,
                         alphabet="ATGC"):
    seq_lst = [] 
    for i in range(length):
        seq_lst.append(random.choice(alphabet))
    seq = "".join(seq_lst) 
    return seq
In [21]:
make_random_sequence()
Out[21]:
'CGACTCGAGGACGAGCCTCTGAAGTTTACTCGGGACGCGGCAAACACAACGGAAGGCTATGGCAGCCTGGAGCTCTTCATTTAACTGGAGGGGAATGCTATCAATCCTAGTAAGGAGCAATGGGTATCCCGGACATTCAAATTATTAACATAACGGCCTGTTCCCTCACATTTCGACTATATTCTCTACCTATAGGGTCC'
In [15]:
make_random_sequence(length=100)
Out[15]:
'CATCGAGTTGGCCCAAACATCTCTAGCTATGCCTGATGATCCAAATTTATCCAATGTTATAAGTGACCCGCATGCATTTTATCCCTGGTACTCTCCTAGA'
In [16]:
make_random_sequence(alphabet="AUGC", length=100)
Out[16]:
'UUAGACUGGAGAGGCCAGAGGCUAGUGUUCCCCCUGUGUCUAAGAGGCCCAGUCUCACCGAGAAAGGAAACGUUCCGCGGGUAGCCACUGUUCGACCUCU'

Также часто вы просто хотите задать поведение функции по-умолчанию/наиболее частое поведение.

In [29]:
def login(username="anonymous", password=None):
    """Some action"""
    pass

# we can call function in different ways
login("root", "ujdyzysqgfhjkm") 
login("guest")
login()
# Also you can specify the name of argument
login(password="nobody@mail.com")

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

In [22]:
def write_random_fasta(out_file_path, 
                       name="random", 
                       length=200,
                       alphabet="ATGC"):
    out_file = open(out_file_path, "w") # it is better to use with-construction here
    seq = make_random_sequence(length=length, alphabet=alphabet)
    out_file.write(">{}\n".format(name))
    out_file.write("{}\n".format(seq))
    out_file.close()
In [23]:
write_random_fasta("random.fasta")
In [20]:
write_random_fasta()

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-20-3d278c1e259e> in <module>()
----> 1 write_random_fasta()

TypeError: write_random_fasta() missing 1 required positional argument: 'out_file_path'
In [24]:
write_random_fasta("random2.fasta", length=10)
In [22]:
def add_to_list(el, lst = []):
    lst.append(el)
    return lst
In [23]:
print (add_to_list(5, [1,2,3])) # OK
print (add_to_list(5, [])) # OK
print (add_to_list(5)) # OK
print (add_to_list(5)) # WHAT???

[1, 2, 3, 5]
[5]
[5]
[5, 5]

surprise)

Дело в том, что значение по-умолчанию создавалось один раз. И вначала оно равно пустому списку. Но в третьем случае мы добавляем в этот список элемент. И после возвращения из функции изменения не пропадают. Потому на следующем вызове элемент добавляется не к пустому списку, а к списку, содержащему один элемент. И так далее. Как это лечить? - не использовать в значениях по-умолчанию изменяемые объекты (списки, словари и т.д), а использовать None

In [24]:
def add_to_list_wsmf(el, lst = None):
    if lst == None:
        lst = []
    lst.append(el)
    return lst
In [ ]:
print (add_to_list_wsmf(5, [1,2,3])) # OK
print (add_to_list_wsmf(5, [])) # OK
print (add_to_list_wsmf(5)) # OK
print (add_to_list_wsmf(5)) # Still OK

Проверку на None правильнее делать так:

In [ ]:
def add_to_list_wsmf(el, lst = None):
    if lst is None:
        lst = []
    lst.append(el)
    return lst
In [ ]:
print (add_to_list_wsmf(5, [1,2,3])) # OK
print (add_to_list_wsmf(5, [])) # OK
print (add_to_list_wsmf(5)) # OK
print (add_to_list_wsmf(5)) # Still OK