Data Structures & Oddities#
Структурите от данни са класове и обекти с интерфейс чрез който ги използваме, като се абстрахираме от имплементацията им.
Алгоритмите са генерализирани процедури (парчета код/функции) които решават даден проблем (изпълняват дадена задача).
Oddities са модули на Python, които нямат място в друга тема, но са интересни за решаването на проблеми.
Защо?#
Структурите от данни и алгоритми:
Се използват често (по-простите от тях: List/Dict/Sort)
Подпомагат разбирането на други езици за програмиране (e.g. JavaScript обектите са Dict)
Са основа на по-сложни системи и приложения (e.g. Приоритетната опашка може да се реализира чрез запазване на опашката в база данни)
Са ключови за Google-style интервютата
3.. 2.. 1.. Go#
Сложност на алгоритми#
https://www.bigocheatsheet.com/
За оценка на сложност (бързина) на алгоритми използваме нотацията “Big O” \(O(...)\).
Сложността оценяваме спрямо размера на входа, като най-често използваме \(n\), за да обозначим размера на входа.
Примери за \(n\):
За list K: \(n = len(K)\)
За str K: \(n = len(K)\)
За int K: \(n = bytes\;of\;K = log_{10}(K) \approxeq log_2(K)\) (но обикновено int казваме че има константен размер \(O(1)\))
Най-важните сложности са:
Constant \(O(1)\)
Linear \(O(n)\)
Linearithmic \(O(n \times log(n))\)
Quadratic \(O(n^2)\)
# O(1)
def constant(x):
return x + 1
# O(n)
def linear(arr): # O(n x 1) = O(n)
for x in arr: # O(n)
print(x) # O(1)
# O(n * log n)
def linearithmic(arr):
logi = 1
while logi < len(arr): # O(log n)
# iterations = len(arr) = 2 ^ logi -> solve for logi -> logi = log(len(arr))
logi *= 2
linear(arr)
# O(n * log n)
def linearithmic2(arr):
arr.sort() # O(n * log n)
# O (n^2)
def quadratic(arr): # O(n * n * 1) = O(n^2)
for row in range(len(arr)): # O(n)
for column in range(len(arr)): # O(n)
print(arr[row][column]) # O(1)
Str#
str е поредица от символи. Ще разгледаме:
Стринговете в Python са immutable -> Повечето операции са \(O(n)\)
# Python speaks UTF-8 :) https://en.wikipedia.org/wiki/UTF-8
s = '🐍 is awesomeͤͤͤͤͤ'
print(s)
🐍 is awesomeͤͤͤͤͤ
s = '🐍 is awesomeͤͤͤͤͤ'
# .encode() Конвертира стринг до байтове.
# Някой байтове не могат да се представят със символ от азбуката
# и използват Hexadecimal Escape Sequence
# Често се използва при работа с файлове -
# понякога четем и пишем байтове вместо стрингове
encoded = s.encode('utf-8')
print(f'{s} -> {encoded}')
print('От байтове може да се върнем в стринг:', encoded.decode())
# 🐍 = \xf0\x9f\x90\x8d
# сложи символ отгоре = '\xcd'
# какво да се сложи отгоре = '\xa4'
# = 🐍 Поредица от байтове се индикира с b''
print('🐍 =', b'\xf0\x9f\x90\x8d'.decode())
print("b'' е просто списък от uint8:", bytes(
[0xf0, 0x9f, 0x90, 0x8d]).decode())
print('Дължината на 🐍 e: ', len(b'\xf0\x9f\x90\x8d')) # len(\xYY) = 1 byte
# Итерирането по стринг работи чрез итериране по символи, не по байтове
print([x for x in 'cool 🐍'])
🐍 is awesomeͤͤͤͤͤ -> b'\xf0\x9f\x90\x8d is awesome\xcd\xa4\xcd\xa4\xcd\xa4\xcd\xa4\xcd\xa4'
От байтове може да се върнем в стринг: 🐍 is awesomeͤͤͤͤͤ
🐍 = 🐍
b'' е просто списък от uint8: 🐍
Дължината на 🐍 e: 4
['c', 'o', 'o', 'l', ' ', '🐍']
print('Форматирането работи! {0} * {1} = {2}'.format('🐍', '🐍', '🐍²'))
Форматирането работи! 🐍 * 🐍 = 🐍²
if 'самобукви'.isalpha():
print('{букви} = alphabetic')
# Можем ли да конвертираме стринга до int?
if '1232367457'.isdigit():
print('{числа} = digit')
# Бърза проверка дали работим с дума или изречение (изречението има паузи и символи)
if '1283912873andLetters'.isalnum():
print('{числа, букви} = alpha-numeric')
# Трябва ли да пишем код който разбира от главни букви?
if 'малкибукви'.islower():
print('{малки букви} = lowercase')
if 'ГОЛЕМИБУКВИ'.isupper():
print('{големи букви} = uppercase')
# Използваме при разбиване на стрингове - if space : do X else do Y
if '\t\n '.isspace():
print('{празни символи} = space')
{букви} = alphabetic
{числа} = digit
{числа, букви} = alpha-numeric
{малки букви} = lowercase
{големи букви} = uppercase
{празни символи} = space
s = '🐍 is awesomeͤͤͤͤͤ'
if s.endswith('e'):
print('s завършва на e') # eͤͤͤ != e
if s.startswith('🐍 is'):
print("s започва с '🐍 is'")
print('is е на индекс', s.find('is')) # Индекс по символ, не по байт
print("'e' се среща", s.count('e'), 'пъти')
s започва с '🐍 is'
is е на индекс 2
'e' се среща 2 пъти
import re
s = '🐍 is awesomeͤͤͤͤͤ'
print(s)
print('Не винаги субституциите работят както ни се иска:',
s.replace('awesome', 'много лесен курс'))
print('Но може да сработят с regex:', re.sub(r'awesome.*', 'бЪрЗ', s))
print('Може да направим всички символи големи:', s.upper())
# Често използваме за да оеднаквим символите, A = a и няма защо
# да ги третираме различно
print('или малки:', 'THICC ->', 'THICC'.lower())
# Ако някой въведе "me@mail.com " то очевидно няма спейс в края на мейл
# -> strip() -> "me@mail.com"
print("Да разчистим празните символи ' нещо ми духа '-> '" +
' нещо ми духа '.strip() + "'")
🐍 is awesomeͤͤͤͤͤ
Не винаги субституциите работят както ни се иска: 🐍 is много лесен курсͤͤͤͤͤ
Но може да сработят с regex: 🐍 is бЪрЗ
Може да направим всички символи голем: 🐍 IS AWESOMEͤͤͤͤͤ
или малки: THICC -> thicc
Да разчистим празните символи ' нещо ми духа '-> 'нещо ми духа'
# Много подпомага дебъгването и не оставя запетая след последния елемент!!
import re
print('Удобно е да принтираме списъци:',
', '.join(['1', '2', '3', '4', 'worldwide']))
# При разбиване на стрингове
# (данни, които знаем че саразделени с някакъв символ)
print('или да разбиваме стринг на елементи:', 'fmi:poluchi:li?'.split(':'))
# за по-сложни разбивания - regex (:
print(re.split(r',|:|\?', 'kude:sym,az?kude:si,ti?'))
Удобно е да принтираме списъци: 1, 2, 3, 4, worldwide
или да разбиваме стринг на елементи: ['fmi', 'poluchi', 'li?']
['kude', 'sym', 'az', 'kude', 'si', 'ti', '']
Библиотеката string предоставя някои удобни константи
import string
# Вместо да хардкодваме "abcdef..."
print('all letters:', string.ascii_letters)
print('all lowercase:', string.ascii_lowercase)
print('all digits as a string:', string.digits)
print('all symbols:', string.punctuation)
print('all whitespaces:', string.whitespace, string.whitespace.encode())
all letters: abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
all lowercase: abcdefghijklmnopqrstuvwxyz
all digits as a string: 0123456789
all symbols: !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
all whitespaces:
b' \t\n\r\x0b\x0c'
Int#
Python няма ограничение за големината на int (C++ long long има ограничение \(2^{63}-1\)). Но операциите с големи числа са бавни - не са \(O(1)\), а \(O(log(number)) = O(number\;of\;digits)\)
Когато стойността надвиши \(2^{63}-1\) числата се обръщат в BigInt.
https://www.codementor.io/@arpitbhayani/how-python-implements-super-long-integers-12icwon5vk
%%time
result = 1
for x in range(1, 100000):
result *= x
# Същият код на C++ минава за total: 0.001 s.
# Но не връща верен отговор :)
CPU times: user 4.23 s, sys: 22.9 ms, total: 4.25 s
Wall time: 4.27 s
import sys
print('int is {0} bytes'.format(sys.getsizeof(int(1))))
print('10^1000 is {0} bytes'.format(sys.getsizeof(int(10**1000))))
print('float is {0} bytes'.format(sys.getsizeof(float(1))))
# float има прецизност като double в C++ (~14 знака след запетаята)
int is 28 bytes
10^1000 is 468 bytes
float is 24 bytes
# За по голяма прицизност може да използваме `decimal` модула
# По дефолт има прецизност 28 знака след запетаята,
# но може да му дадем повече :)
from decimal import *
getcontext().prec = 56
print(Decimal(22) / Decimal(7))
3.1428571428571428571428571428571428571428571428571428571
# Начин на използване
print('Стринг -> int:', int('42'))
print('Конвертиране от други бройни системи, освен base10:', int('ff', 16))
print('Премахване на знаците след десетичната запетая', int(-5.2), int(5.2))
print('Абсолютна стойност(-5) =', abs(-5))
Стринг -> int: 42
Конвертиране от други бройни системи, освен base10: 255
Премахване на знаците след десетичната запетая -5 5
Абсолютна стойност(-5) = 5
Math#
import math
print('Закръгляне нагоре 2.2 ->', math.ceil(2.2))
print('Закръгляне надолу 2.7 ->', math.floor(2.7))
# Може да правим побитово итериране на числото
print('Преброяване на битовете на числото 257 =', math.ceil(math.log2(257)))
# Полезно при построяване на Trie/radix sort/заделяне на hashmap
print('Преброяване на цифрите на числото 14532 =', math.ceil(math.log10(14532)))
# Математически важни функции
print('Най-голям общ делител на 35 и 15 =', math.gcd(35, 15))
print('Можем да смятаме inverse елемента по модул 15^-1 mod 26 =', pow(15, -1, 26))
# Комбинаторика (често се среща в задачи, но има и други)
print('N choose K -> 10 choose 2 =', math.comb(10, 2))
Закръгляне на горе 2.2 -> 3
Закръгляне на долу 2.7 -> 2
Преброяване на битовете на числото 257 = 9
Преброяване на цифрите на числото 14532 = 5
Най-голям общ делител на 35 и 15 = 5
Можем да смятаме inverse елемента по модул 15^-1 mod 26 = 7
N choose K -> 10 choose 2 = 45
# Специални стойности на float:
# Not a Number (полезно като дъно на стек)
print('Not a Number =', math.nan)
# Infinity (полезно като последен елемент на масив,
# нещо като терминираща нула в C++)
print('Infinity =', math.inf)
# -Infinity
print('-Infinity =', -math.inf)
# Константи
print('π = ', math.pi)
print('e = ', math.e)
Not a Number = nan
Infinity = inf
-Infinity = -inf
π = 3.141592653589793
e = 2.718281828459045
math модулът има още много функции на които няма да се спираме, защото не се използват често:
Тригонометрични функции
Хиперболични функции
Гама функция
Конвертиране между градуси и радиани
Други
List#
Саморазширяващ се списък/масив от елементи. Въпреки името list, структурата е динамичен масив, а не свързан списък.
arr = [0] * 10 # инициализиране на списък с 10 елемента O(n)
print('Списък с 10 елемента:', arr)
arr = list() # празен списък O(1)
arr.clear() # O(1) еквивалентно на ' = list()'
print('Празен списък:', arr)
# O(1*) за разлика от конкатенацията на стрингове ('abc' + 'd') която е O(n)
arr.append(1)
arr.insert(0, -1) # O(n)
arr = [-2] + arr # O(n) еквивалентно на горното АКО елементите НЕ СА list
print('До момента имаме:', arr)
arr.reverse() # O(n)
print('Може да обърнем списъка', arr)
arr.sort() # O(n * log n)
print('И да го сортираме', arr)
last_element = arr.pop() # O(1)
print('pop премахва последния елемент и го връща', arr, last_element)
Списък с 10 елемента: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Празен списък: []
До момента имаме: [-2, -1, 1]
Може да обърнем списъка [1, -1, -2]
И да го сортираме [-2, -1, 1]
pop премахва последния елемент и го връща [-2, -1] 1
Примери с често използвани техники върху list
# Сортиране на списък с обекти
tuples = [(2, 'elon'), (1, 'daddy')]
# Ако вместо tuples имаме обекти използваме obj.field, вместо x[1]
tuples.sort(key=lambda x: (x[1]))
# ламбда функцията връща tuple от елементи в каквато последователност
# трябва да се сравняват.
# Ако 0-левия елемент е един и същ, пробвай 1вия.
# Ако първият елемент е един и същ, пробвай 2рия и тн.
print(' '.join(list(x[1] for x in tuples)))
# Обръщане на списък
reversed_tuples = tuples[::-1] # създава нов списък
print(' '.join(list(x[1] for x in reversed_tuples)))
# Копиране на списък
tuples_copy = tuples[::]
tuples_copy.clear()
print(f'{tuples = }, {tuples_copy = }')
daddy elon
elon daddy
tuples = [(1, 'daddy'), (2, 'elon')], tuples_copy = []
Array#
array предоставя по-ефективно използване на паметта от list. Повече прилича на стандартните масиви в други езици. Добавянето на елемент в края на array е \(O(1)\).
Има същите функционалности като list.
При инициализиране трябва да окажем типа на елементите в списъка.
Ако се е стигнало до използване на по-оптимизирани структури в Python най-добре да използваме някоя библиотека като numpy.
%%capture
# %%capture is a jupyter instruction to hide output
from array import array
array('l') # array<32 bit int>
array('u', 'hello \u2641') # array<unicode character>
array('d', [1.0, 2.0, 3.14]) # array<double>
array('I', [1, 2, 3]) # array<unsigned 16 bit int>
Dict#
dict е питонската имплементация на Hash-Table. Повечето операции с dict са \(O(1)\). Изключение правят операциите за обработка на всички елементи, които са \(O(n)\).
Елементите на dict са key-value (ключ - стойност). Ключът задължително трябва да е от тип, който може да се хешира, стойността може да е всякаква.
Забележка: Казваме, че операциите са \(O(1)\), но всъщност зависят от размера на ключа. Обикновено ключовете са малки по размер в паметта и за това на повечето места в литературата се казва че операциите са \(O(1)\), но ако ключовете ни са стрингове с дължина 100,000 символа, то сложността на операциите не е точно \(O(1)\) :)
my_dict = {} # Инициализираме празен dict
my_dict = dict() # dict() == {}
my_dict['is big'] = 'not'
print('dict с 1 елемент', f'{my_dict = }')
del my_dict['is big'] # del изтрива елемент
print('празен dict след като изтрихме ключа "is big"', f'{my_dict = }')
# Ако се опитаме да достъпим или изтрием ключ който не
# съществува ще гръмнем с KeyError
del my_dict['non-existent key']
dict с 1 елемент my_dict = {'is big': 'not'}
празен dict след като изтрихме ключа "is big" my_dict = {}
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
Cell In [19], line 10
7 print('празен dict след като изтрихме ключа "is big"', f'{my_dict = }')
8 # Ако се опитаме да достъпим или изтрием ключ който не
9 # съществува ще гръмнем с KeyError
---> 10 del my_dict['non-existent key']
KeyError: 'non-existent key'
# Итериране по dict
person_age = {
'Gosho na pochivka': 25,
'Gosho na fmi': 11001,
}
result = []
for x in person_age: # == .keys()
result.append(x)
print('for x in dict:', result)
result = []
for x in person_age.keys():
result.append(x)
print('for x in dict.keys():', result)
result = []
for x in person_age.values():
result.append(x)
print('for x in dict.values():', result)
result = []
for x in person_age.items():
result.append(x)
print('for x in dict.items():', result)
for x in dict: ['Gosho na pochivka', 'Gosho na fmi']
for x in dict.keys(): ['Gosho na pochivka', 'Gosho na fmi']
for x in dict.values(): [25, 11001]
for x in dict.items(): [('Gosho na pochivka', 25), ('Gosho na fmi', 11001)]
# По време на итериране не е позволено да променяме dict
palindromes = {
'ami': 'ima',
'pari': 'irap',
'nema': 'amen',
}
for x in palindromes:
palindromes[x] = 'nali ne mojelo da se promenq e bai xy*'
print(palindromes)
for x in palindromes:
del palindromes[x] # промяна върху ключовете не работи :(
{'ami': 'nali ne mojelo da se promenq e bai xy*', 'pari': 'nali ne mojelo da se promenq e bai xy*', 'nema': 'nali ne mojelo da se promenq e bai xy*'}
---------------------------------------------------------------------------
RuntimeError Traceback (most recent call last)
Cell In [21], line 13
9 palindromes[x] = 'nali ne mojelo da se promenq e bai xy*'
11 print(palindromes)
---> 13 for x in palindromes:
14 del palindromes[x]
RuntimeError: dictionary changed size during iteration
print('въпреки грешката на предишната стъпка изтрихме 1 ключ (на рандъм)', palindromes)
# Тъй като не може да променяме dict докато итерираме ще трябва да създадем нов
changed = {k: 'shte si napravq moi dict togava'
for k, _ in palindromes.items() if k != 'pari'}
print(changed)
въпреки грешката на предишната стъпка изтрихме 1 ключ (на рандъм) {'pari': 'nali ne mojelo da se promenq e bai xy*', 'nema': 'nali ne mojelo da se promenq e bai xy*'}
{'nema': 'shte si napravq moi dict togava'}
# Задача
my_list = [1,2,3,4,5]
my_dict = {1:'a', 2:'b', 3:'c', 4:'d', 5:'e'}
# Коя операция е по-бърза
if 4 in my_list:
print('list')
if 4 in my_dict:
print('dict')
"""Изпълни клетката за хинт"""
import base64
print(base64.b64decode(
'0J7Qv9C10YDQsNGC0L7RgNGK0YIgaW4g0LLRitGA'
'0YXRgyBsaXN0INC1IE8obiksINCwINCy0YrRgNGF'
'0YMgZGljdCDQtSBPKDEqKQ=='.encode()).decode())
Defaultdict#
defaultdict живее в модула collections. Има същата функционалност като dict, но при инициализация трябва да окажем от какъв тип ще са стойностите. При достъпване на ключ, който не съществува, ще се създаде ключа и стойност - дефолтен обект от типа, който задаваме при инициализация.
Обикновено го използваме за удобство - не е нужно да проверяваме дали стойността зад някой ключ е инициализирана.
from collections import defaultdict
my_default_dict = defaultdict(list)
print(my_default_dict)
my_default_dict['what']
print('дори само с достъпване на ключа създаваме дефолтен обект', my_default_dict)
del my_default_dict['what']
for index, char in enumerate('this is a string'):
my_default_dict[char].append(index) # Това ще изгърми с нормален dict
my_default_dict
defaultdict(<class 'list'>, {})
дори само с достъпване на ключа създаваме дефолтен обект defaultdict(<class 'list'>, {'what': []})
defaultdict(list,
{'t': [0, 11],
'h': [1],
'i': [2, 5, 13],
's': [3, 6, 10],
' ': [4, 7, 9],
'a': [8],
'r': [12],
'n': [14],
'g': [15]})
# Задача (advanced)
# Как може да имплементираме Trie чрез defaultdict
import base64
print(base64.b64decode(
'ZGVmIHRyaWUoKToKICAgIHJldHVybi'
'BkZWZhdWx0ZGljdCh0cmllKQo='.encode()).decode())
Counter#
Counter е още един под-клас на dict. При инициализация може да се подаде колекция (или друг обект който може да се итерира и елементите му могат да се хешират), която бива итерирана и елементите ѝ се преброяват.
Елементите на колекцията стават ключове, а стойностите са колко пъти даден елемент е срещнат в колекцията.
from collections import Counter
Counter('string isn\'t a collection, but it\'s iterable')
Counter({'s': 3,
't': 6,
'r': 2,
'i': 5,
'n': 3,
'g': 1,
' ': 6,
"'": 2,
'a': 2,
'c': 2,
'o': 2,
'l': 3,
'e': 3,
',': 1,
'b': 2,
'u': 1})
# Задача
# Напишете функция която извежда най-често срещаните букви на даден стринг
import base64
print(base64.b64decode(
'ZGVmIGNvdW50KHMpOgogICAgY291bnRzID0gbGl'
'zdChDb3VudGVyKHMpLml0ZW1zKCkpCiAgICBjb3'
'VudHMuc29ydChrZXk9bGFtYmRhIHg6IC14WzFdK'
'QogICAgcHJpbnQoY291bnRzKQo='.encode()).decode())
Set#
set е dict, който има само ключове, стойностите не ни интересуват. Добавяне/премахване/проверка дали елемент е в сет-а се случва за \(O(1)\)
set се използва по-рядко от dict, и основно за да намерим уникалните елементи на колекция.
uniques = set() # няма по-кратък начин за инициализране на сет, както {} за dict
# Може директно да го инициализираме от колекция
uniques = set([1, 2, 3, 3, 3, 3, 3, 3])
print('инициализация от колекция', uniques)
uniques.add(1) # добавяме елемент
print('елемент, който вече е в сета няма да се добави отново', uniques)
print('Може да обединим 2 сета', set([1, 2, 3]).union(set([2, 3, 4])))
print('Може да вземем само общите елементи', set([1, 2, 3]) & set([2, 3, 4]))
print('Може да вземем елементите които не са общи',
set([1, 2, 3]) ^ set([2, 3, 4]))
print('Може да проверим дали даден елемент е в сета: 5 in [1,2,3]?', 5 in set(
[1, 2, 3]))
инициализация от колекция {1, 2, 3}
елемент, който вече е в сета няма да се добави отново {1, 2, 3}
Може да обединим 2 сета {1, 2, 3, 4}
Може да вземем само общите елементи {2, 3}
Може да вземем елементите които не са общи {1, 4}
Може да проверим дали даден елемент е в сета: 5 in [1,2,3]? False
# Задача: колко различни букви са използвани в следния стринг
# 'The quick brown fox jumps over the lazy dog'
import base64
print(base64.b64decode(
'bGVuKHNldCgKICAgICdUaGUgcXVpY2sgYnJvd24gZm9'
'4IGp1bXBzIG92ZXIgdGhlIGxhenkgZG9nJwogICAgLm'
'xvd2VyKCkKICAgIC5yZXBsYWNlKCcgJywgJycpCikpC'
'g=='.encode()).decode())
Frozenset#
frozenset = immutable set. Immutability носи плюсове и минуси:
(+) може да хешираме сета (да го използваме като ключ в
dictили да го добавим в другset)(-) не може да го променяме (да добавяме/премахваме елементи)
my_dict = {
set([1, 2, 3]): 'sets are unhashable, trust me',
}
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In [26], line 1
----> 1 my_dict = {
2 set([1, 2, 3]): 'sets are unhashable, trust me',
3 }
TypeError: unhashable type: 'set'
numbers = set([1, 2, 3])
my_dict = {
frozenset(numbers): 'my password',
frozenset('characters'): 'ако подадем string, ще конструираме set от буквите'
}
my_dict
{frozenset({1, 2, 3}): 'my password',
frozenset({'a',
'c',
'e',
'h',
'r',
's',
't'}): 'ако подадем string, ще конструираме set от буквите'}
Stack#
stack (стак/стек) е LIFO (Last In First Out) структура, която ни позволява бърз достъп до последния добавен елемент. В Python няма клас Stack, защото list има всички необходими методи.
stack = []
for x in range(100):
stack.append(x)
first10 = 0
for i in range(10):
first10 += stack.pop() # Достъп до последния елемент е О(1)
print('Сумата на първите 10 елемента е: ', first10) # sum(100 до 90) = 945
Сумата на първите 10 елемента е: 945
# Задача
# Имплементирайте клас, който поддържа следните операции
# - O(1) push: добавя нов елемент в стека
# - O(1) топ: връща последния вкаран елемент
# - O(1) pop: премахва последния вкаран елемент
# - O(1) get_min: връща минималният елемент от всички в стека
print(base64.b64decode(
'Y2xhc3MgTWluU3RhY2s6CiAgICBkZWYgX19pbml0X18oc2VsZik6CiAgIC'
'AgICAgc2VsZi5kYXRhID0gW10KICAgICAgICBzZWxmLm1pbnMgPSBbXQoKI'
'CAgIGRlZiBwdXNoKHNlbGYsIHg6IGludCkgLT4gTm9uZToKICAgICAgICBz'
'ZWxmLmRhdGEuYXBwZW5kKHgpCiAgICAgICAgaWYgbGVuKHNlbGYubWlucyk'
'gPiAwOgogICAgICAgICAgICBzZWxmLm1pbnMuYXBwZW5kKG1pbihzZWxmLm'
'1pbnNbLTFdLCB4KSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBzZWxmL'
'm1pbnMuYXBwZW5kKHgpCgogICAgZGVmIHBvcChzZWxmKSAtPiBOb25lOgog'
'ICAgICAgIHNlbGYuZGF0YS5wb3AoKQogICAgICAgIHNlbGYubWlucy5wb3A'
'oKQoKICAgIGRlZiB0b3Aoc2VsZikgLT4gaW50OgogICAgICAgIHJldHVybi'
'BzZWxmLmRhdGFbLTFdCgogICAgZGVmIGdldF9taW4oc2VsZikgLT4gaW50O'
'gogICAgICAgIHJldHVybiBzZWxmLm1pbnNbLTFdCg=='.encode()).decode())
Queue#
queue е thread-safe имплементация на опашка (FIFO). Може да я създадем с ограничен размер Queue(maxsize=42) - ако се напълни и се пробваме да добавим нов елемент ще се блокира нишката. maxsize=0 означава че няма лимит и ще се разширява докато имаме памет.
Ако работим в multithreaded среда, то операциите като qsize(), empty(), full() и повечето други нямат гаранции, че връщат винаги точен резултат. Резултатът е близък до точен, но няма гаранция.
Пример: Ако имаме опашка която е пълна и от 1 нишка извикаме full() докато се изпълнява full може някоя друга нишка да извика get() и да премахне елемент - съответно ще получим True когато трябва да е False.
import queue
que = queue.Queue()
for x in range(100):
que.put(x)
print('Елементите ги борим с qsize: ', que.qsize())
total = 0
while not que.empty(): # Работим на 1 нишка така че това е детерминистично
total += que.get()
print('Сумата на всички елементи е: ', total)
for x in range(100):
que.put(x)
first10 = 0
for i in range(10):
first10 += que.get()
print('Сумата на първите 10 елемента е: ', first10) # sum(1 до 10) = 45
Елементите ги борим с qsize: 100
Сумата на всички елементи е: 4950
Сумата на първите 10 елемента е: 45
PriorityQueue#
Какво правим ако искаме опашка, но елементите да са поддедени по някакъв приоритет, не по реда в който ги добавяме? - тадаа PriorityQueue 🎉
PriorityQueue предоставя добавяне/премахване на елемент за \(O(logn)\) и достъп до най-малкия елемент за \(O(1)\).
import queue
import random
numbers = list(range(1, 11)) # [1, 2, ... 10]
random.shuffle(numbers)
print('Разбъркваме числата с random.shuffle()', numbers)
que = queue.PriorityQueue()
for x in numbers:
que.put(x)
print('Данните не са подредени в реда в който ги добавяме, но 1 винаги е в началото:',
que.queue)
top3 = []
for i in range(3):
top3.append(que.get())
print('Приоритетната опашка връща елементите от най-малък към най-голям', top3)
Разбъркваме числата с random.shuffle() [1, 9, 7, 4, 10, 2, 6, 3, 5, 8]
Данните не са подредени в реда в който ги добавяме, но 1 винаги е в началото: [1, 3, 2, 4, 8, 7, 6, 9, 5, 10]
Приоритетната опашка връща елементите от най-малък към най-голям [1, 2, 3]
За съжаление не е възможно да използваме custom функция за сравнение за да направим Max Heap.
Има 2 начина да решим такава задача, единият е да създаваме клас, който да имплементира __lt__/__gt__, и __eq__.
Вторият ще разгледаме в следващата клетка.
But you know - if you like it hard I won’t stop you - https://stackoverflow.com/questions/57487170/is-it-possible-to-pass-a-comparator-to-a-priorityqueue-in-python
# Задача
# Как може да използваме вградения клас PriorityQueue като Max Heap, вместо Min Heap
print(base64.b64decode(
'0JDQutC+INC40LzQsNC80LUg0YfQuNGB0LvQsNGC0LAgW'
'zEsMiwzLDQsNV0g0LrQvtC1INC1INC90LDQuS3QvNCw0L'
'vQutC+0YLQvj8g0JDQvNC4INCw0LrQviDQuNC80LDQvNC'
'1IFstMSwtMiwtMywtNCwtNV0/Cg=='.encode()).decode())
heapq#
heapq предоставя основните методи за работа с приоритетни опашки поотделно. Тоест, не е нужно да ползваме цялата функционалност на PriorityQueue, а може да използваме само 1 от методите - например heapq.heapify.
tl;dr как работи приоритетна опашка?
Ковертираме произволен масив до
heapq.heapify()\(O(n)\)Ако искаме да добавим елемент използваме
heapq.heappush()\(O(log n)\)Ако искаме да извадим елемент използваме
heapq.heappop()\(O(log n)\)
import heapq
import random
numbers = list(range(1, 11)) # [1, 2, ... 10]
random.shuffle(numbers)
print('Разбъркваме числата с random.shuffle()', numbers)
heapq.heapify(numbers) # по-бързо от добавянето на елементи 1 по 1
print('Данните не са подредени в реда в който ги вкарваме, но 1 винаги е в началото:',
numbers)
# Добавянето на нов по-малък елемент ще го постави в началото
heapq.heappush(numbers, 0)
print('0 винаги е в началото:', numbers)
top3 = []
for i in range(3):
top3.append(heapq.heappop(numbers))
print('Приоритетната опашка връща елементите от най-малък към най-голям', top3)
Разбъркваме числата с random.shuffle() [4, 2, 9, 5, 3, 8, 1, 7, 10, 6]
Данните не са подредени в реда в който ги вкарваме, но 1 винаги е в началото: [1, 2, 4, 5, 3, 8, 9, 7, 10, 6]
0 винаги е в началото: [0, 1, 4, 5, 2, 8, 9, 7, 10, 6, 3]
Приоритетната опашка връща елементите от най-малък към най-голям [0, 1, 2]
deque#
Ако ни трябва опашка + стек, тоест искаме \(O(1*)\) за добавяне/премахване на елемент в началото използваме deque. Обикновено се имплементира върху Circular Array.
from collections import deque
deq = deque(['опашка ли съм', 'ʞǝꓕɔ иѵи'])
deq.insert(1, '¿?') # Добавянето на елемент на произволна позиция е О(n)
print(deq)
deq.append('у десно')
deq.append('у десно (1)')
deq.appendleft('у лево')
print(deq)
print('последният елемент за О(1):', deq.pop())
print('първият елемент за О(1):', deq.popleft())
deque(['опашка ли съм', '¿?', 'ʞǝꓕɔ иѵи'])
deque(['у лево', 'опашка ли съм', '¿?', 'ʞǝꓕɔ иѵи', 'у десно', 'у десно (1)'])
последният елемент за О(1): у десно (1)
първият елемент за О(1): у лево
# Интересно приложение на deque е имплементирането на round robin
def roundrobin(*iterables):
"roundrobin('ABC', 'D', 'EF') --> A D E B F C"
iterators = deque(map(iter, iterables))
while iterators:
try:
while True:
yield next(iterators[0])
iterators.rotate(-1)
except StopIteration:
iterators.popleft()
# Задача
# Имаме следната имплементация на BFS. Как може да я обърнем до DFS?
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
def bfs(graph, start):
visited = set()
que = deque()
visited.add(start)
que.append(start)
while que:
s = que.popleft()
print(s, end=" ")
for neighbor in graph[s]:
if neighbor not in visited:
visited.add(neighbor)
que.append(neighbor)
print(base64.b64decode('0JfQsNC80LXQvdGP0LzQsCBkZXF1ZS5wb3BsZWZ0KCk'
'g0YEgZGVxdWUucG9wKCk='.encode()).decode())
Algorithms & Oddities#
Binary Search#
Бързо (\(O(logn)\)) търсене в сортиран масив.
bisect_left = кой е първият индекс на който може да поставим елемента, за да се запази подредбата?
bisect_right = кой е последният индекс на който може да поставим елемента, за да се запази подредбата?
import bisect
numbers = [0, 1, 2, 4, 4, 4, 4, 7, 8, 9]
# 0 1 2 3 4 5 6 7 8 9
print('Ако елемента съществува, връща индекса на първото срещане',
bisect.bisect_left(numbers, 4))
print('Ако елемента съществува, връща първия индекс след последното срещане',
bisect.bisect_right(numbers, 4))
print('Ако елемента не съществува, връща индекса на първото срещане',
bisect.bisect_left(numbers, 5))
print('Ако елемента не съществува, връща първия индекс след последното срещане',
bisect.bisect_right(numbers, 5))
Ако елемента съществува, връща индекса на първото срещане 3
Ако елемента съществува, връща първия индекс след последното срещане 7
Ако елемента не съществува, връща индекса на първото срещане 7
Ако елемента не съществува, връща първия индекс след последното срещане 7
# Задача
# В сортиран list от числа, напишете функция, която намира броя на срещанията на някое число
print(base64.b64decode('ZGVmIGNvdW50X29jY3VycmVuY2VzKGhh'
'eXN0YWNrLCBuZWVkbGUpOgogICAgYmlzZWN0LmJpc2VjdF9yaWd'
'odChoYXlzdGFjaywgbmVlZGxlKSAtIGJpc2VjdC5iaXNlY3RfbG'
'VmdChoYXlzdGFjaywgbmVlZGxlKQo='.encode()).decode())
Copy & Deepcopy#
Python подава аргументите на функциите по референция, така че може да ги променяме. Това не е винаги желаното поведение, така че Python предоставя 2 метода за копиране да обекти.
from copy import copy, deepcopy
def reset_tree():
return {
'value': 'parent',
'child': {
'value': 'child',
}
}
def level_up(root):
tree = root # Това не прави нищо, само преименува променливата
tree['child']['value'] = 'super child'
return tree
tree = reset_tree()
same = level_up(tree)
print(tree)
print(same)
print('Когато подаваме елемент по референция във функцията работим със същия елемент')
print(f'{id(tree) = } == {id(same) = }')
{'value': 'parent', 'child': {'value': 'super child'}}
{'value': 'parent', 'child': {'value': 'super child'}}
Когато подаваме елемент по референция във функцията работим със същия елемент
id(tree) = 4399790912 == id(same) = 4399790912
def level_up_swallow(root):
tree = copy(root)
tree['child']['value'] = 'super child'
return tree
tree = reset_tree()
same_but_different_but_same = level_up_swallow(tree)
print(tree)
print(same_but_different_but_same)
print('(shallow) copy копира обекта, но не копира обектите в него')
print(f'{id(tree) = } != {id(same_but_different_but_same) = }')
{'value': 'parent', 'child': {'value': 'super child'}}
{'value': 'parent', 'child': {'value': 'super child'}}
(shallow) copy копира обекта, но не копира обектите в него
id(tree) = 4698146048 != id(same_but_different_but_same) = 4698275328
def level_up_deep(root):
tree = deepcopy(root)
tree['child']['value'] = 'super child'
return tree
tree = reset_tree()
different = level_up_deep(tree)
print(tree)
print(different)
print('deepcopy създава копие, на обекта и рекурсивно на обектите в него')
print(f'{id(tree) = } != {id(different) = }')
{'value': 'parent', 'child': {'value': 'child'}}
{'value': 'parent', 'child': {'value': 'super child'}}
deepcopy създава копие, на обекта и рекурсивно на обектите в него
id(tree) = 4698416960 != id(different) = 4698412800
Random#
random модулът предоставя методи за избиране на случаен елемент, случайно число, случайни битове и тн.
Обикновено се използва за тестове (генериране на вход/изход).
За криптографски задачи (криптиране на данни, пароли, генериране на токени и тн), не трябва да се
използва random, а secrets модула. За да не навлизаме в разликите, нека да кажем че secrets генерира
по-рандъм изход от random модула :)
import random
# random модулът може да приеме начална стойност, която се използва
# в рандъм алгоритмите, за да върне детерминистичен изход.
# Обикновено се използва за да може даден експеримент/тест да се репродуцира
random.seed(42)
# Това е рандъм число, но заради seed = 42, винаги ще върне 82 в този notebook
random.randint(1, 100)
82
import random
print('рандъм float', random.random())
print('randint [0,1]:', random.randint(0, 1))
# Някои методи в random работят със затворени, някой с отворени интервали.
# Добре е да се провери преди използването им
print('randrange [0,1) не е много рандъм:', random.randrange(0, 1))
# randrange(a,b) = randint(a,b-1)
# Ако имаме колекция от елементи може да използваме choice, за да изберем произволен
# Алтернативният метод е да използваме random.randrange(0, len(collection))
print('Епа кот дойде:', random.choice(['fuck', 'marry', 'kill']))
# Може да задаваме и тежести - 50% ще е първият елемент, 25% втория и 25% третия
print('Понякога рандъм изборът не е много рандъм',
random.choices(
['boiko', 'pak boiko', 'totally not boiko'],
weights=[2, 1, 1]
))
# Понякога трябва да разбъркаме някяква колекция. Например преди да правим quicksort
numbers = list(range(1, 11))
random.shuffle(numbers)
print('shuffle:', numbers)
# При експерименти или когато имаме много данни искаме да изберем произволна подгрупа
print('Избор на 2 елемента без повторения:', random.sample(numbers, 2))
рандъм float 0.11133106816568039
randint [0,1]: 1
randrange [0,1) не е много рандъм: 0
Епа кот дойде: fuck
Понякога рандъм изборът не е много рандъм ['boiko']
shuffle: [8, 3, 6, 7, 1, 4, 5, 10, 9, 2]
Избор на 2 елемента без повторения: [7, 9]
%%capture
import random
# За пълнота трябва да споменем, че random модулът има имплементация на
# повечето видови разпределения от статистиката, но няма да навлизаме в подробности
random.uniform(1, 10)
random.gauss(1, 2)
random.expovariate(1)
random.gammavariate(10, 1)
random.normalvariate(5, 1)
Itertools#
itertools модулът предоставя методи улесняващи итерацията по елементи и често използвани конструкции. Вече сме виждали някой подобни функции като map/filter.
Функциите са доста и улесняват писането на цикли и особено вложени цикли, но понякога отнема повече време да намерим правилната функция от колкото да напишем кода от 0.
Целият списък е тук като има разширение на стандартната библиотека от more-itertools пакета.
import itertools
# Итератор, който се връща в началото на списъка като се изчерпи.
# Наподобява Ring Buffer
cycle = itertools.cycle('ABC')
for _ in range(10):
print(next(cycle), end=', ')
print()
# Итератор, който обединява няколко итератора/колекции
# Може да го използваме за да flatten-нем списък от списъци
for x in itertools.chain('first', ' ', 'second'):
print(x, end=',')
print()
# Към всеки елемент от списъка се прибавя сумата на всички предишни елементи
print(list(itertools.accumulate([-20, +10, +30, -5])))
# Може да го използваме за да генерираме всички префикси на дума
print(list(itertools.accumulate('construct')))
# Генериране на всички уникални двойки. Еквивалентно на 2 вложени цикъла
print(list(itertools.combinations('ABC', 2)))
# Генериране на всички съседни двойки
print(list(itertools.pairwise([1, 5, 7, 10])))
# Всички пермутации
print(list(itertools.permutations([0, 1, 2])))
# A x B - декартово произведение
print(list(itertools.product([1, 2, 3], 'ABC')))
A, B, C, A, B, C, A, B, C, A,
f,i,r,s,t, ,s,e,c,o,n,d,
[-20, -10, 20, 15]
['c', 'co', 'con', 'cons', 'const', 'constr', 'constru', 'construc', 'construct']
[('A', 'B'), ('A', 'C'), ('B', 'C')]
[(1, 5), (5, 7), (7, 10)]
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
[(1, 'A'), (1, 'B'), (1, 'C'), (2, 'A'), (2, 'B'), (2, 'C'), (3, 'A'), (3, 'B'), (3, 'C')]
Functools#
functools предоставя фунцкии от по-висок ред - декоратори и помощни функции. Концепциите в модула са доста сложни така че ще разгледаме само по-често използваните. В темата за функционално се разлеглежда един от основните методи - reduce.
Друг интересен пример е functools.singledispatch декоратора, който ни позволява да overload-ваме функции базирано на типа на първият им аргумент. Тъй като това не работи за функции с повече от 1 аргумент които да overload-нем, няма да му отделяме време. But it exists!
%%time
import functools
# Нека си дефинираме наивна рекурсивна функция
def fibonacci(n):
if n in [0, 1]:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
# Имаме O(2 ^ 40) извиквания на фунцкии :(
fibonacci(40)
CPU times: user 19.8 s, sys: 92 ms, total: 19.9 s
Wall time: 20 s
165580141
%%time
import functools
# Mоже да я забързаме ако кешираме извикванията
# Така няма да правим едно и също изчисление 2 пъти
@functools.lru_cache(maxsize=150)
def fibonacci(n):
if n in [0, 1]:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(40)
fibonacci(150)
# Дори fib(150) което с наивната рекурсия няма да приключи
# никога минава за под 1ms
CPU times: user 62 µs, sys: 89 µs, total: 151 µs
Wall time: 155 µs
16130531424904581415797907386349
# Ако имаме клас, за който искаме да имплементираме сравнение
# Може да имплементираме само __lt__ и __eq__ и останалите методи
# ще се имплементират за нас
# Защото понякога имплементирането им просто не е тривиално ...
import functools
@functools.total_ordering # ще имплементира __gt__, __le__, и тн.
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __lt__(self, other):
# Имплементира Z-order curve подредба на точките
most_significant_dim = 'x'
if self.less_msb(self.x ^ other.x, self.y ^ other.y):
msd = 'y'
if most_significant_dim == 'x':
return self.x < other.x
else:
return self.y < other.y
def less_msb(self, x, y):
return x < y and x < (x ^ y)
CSV#
Python предоставя няколко модула за работа с данни сериализирани под различен формат. Един от тези модули е за работа с CSV файлове (coma-separated values). Ще разгледаме само пример за парсене на такъв файл, но модулът има много различни функционалности и опции.
import csv
from io import StringIO
contents = StringIO( # == string stream
'''Lyubo,21,Sofia
Alex,22,Sofia
Ivan,49,"Ne Sofia"
''')
reader = csv.reader(contents)
for index, row in enumerate(reader):
print(index, ':', row)
0 : ['Lyubo', '21', 'Sofia']
1 : ['Alex', '22', 'Sofia']
2 : ['Ivan', '49', 'Ne Sofia']
JSON#
Друг популярен формат на данни е JSON … Разбира се в Python има модул json.
import json
my_dict = json.loads('{"foo": {"bar":["baz", null, 1.0, 2]}}')
print('От стринг конструирахме dict, който може да използваме:',
my_dict['foo']['bar'])
print('Обратната операция на сериализиране е удобна за принтене на дебъг съобщения')
print(json.dumps(my_dict, sort_keys=True, indent=4))
От стринг конструирахме dict, който може да използваме: ['baz', None, 1.0, 2]
Обратната операция на сериализиране е удобна за принтене на дебъг съобщения
{
"foo": {
"bar": [
"baz",
null,
1.0,
2
]
}
}
Regex#
Regex или още регулярни изрази са стрингове, които описват някакъв патърн, който може да използваме за търсене в обикновени стрингове.
regex може да запълни материала за цял курс, но ще се опитаме да разгледаме само често използвани примери, без да навлизаме в подробности.
Писането на регулярни изрази обикновено е трудоемка задача, за това препоръчваме инструменти като regexr, които изпълняват regex в реално време и имат обяснение защо даден стринг е match-нал.
import re
# == (.start(), .end())
print(re.search(r'123', '458971985719285712324953928572').span())
ninjas = 'ninjatreenoooinjaforestninjavoicenwvi9ew9ninja'
print('Следва ли стринга този патърн?',
re.match(r'.*ninja$', ninjas) is not None)
print('Намери всички срещания:',
re.findall(r'n.*?a', ninjas))
print('Разбиване на стринг на всяко срещане на патърн:',
re.split(r'n.*?a', ninjas))
print('Субституция на патърн в стринг:',
re.sub(r'n.*?a', '-NINJA-', ninjas))
(16, 19)
Следва ли стринга този патърн? True
Намери всички срещания: ['ninja', 'noooinja', 'ninja', 'nwvi9ew9ninja']
Разбиване на стринг на всяко срещане на патърн: ['', 'tree', 'forest', 'voice', '']
Субституция на патърн в стринг: -NINJA-tree-NINJA-forest-NINJA-voice-NINJA-
# Hint helper
import base64
print(base64.b64encode(''.encode()).decode())
print(base64.b64decode(''.encode()).decode())