Topic_02. Algorithm, sets, dictionaries, functions

1. Introduction to Python

Session 2

2. Agenda

• Algorithms
• Set
• Dictionary
• Functions, part 1

3.

Algorithm and complexity
3

4. Definition

The complexity of an algorithm is assessed via counting the number of elementary operations
done by the algorithm. It is also assumed that the time for each elementary operation is fixed.
O-notation is used to describe the complexity of algorithms.
When we speak “complexity”, we usually mean “time complexity”. Though memory complexity
is also considered.
4

5. Algorithm complexity

• O(1) – constant time
• O(log log n) – double-logarithmic time
• O(log n) – logarithmic time
• O(n) – linear time
• O(n log n) – log-linear time
• etc.
5

6. Algorithm complexity examples

# Find element in sorted array. Simple search:
Complexity – O(n)
Search
array = [11,23,34,43,44,47,59,634]
element_to_find = 59
for item in array:
if item == element_to_find:
print("Found")
break
else:
print(“Is not found")
ref ref
ref ref ref ref
ref ref
59
11
23
634
6

7. Algorithm complexity examples

# Find element in sorted array. Binary search:
Complexity – O(log n)
array = [11,23,34,43,44,47,59,634]
element_to_find = 59
middle
11
23
34
43 44
47 59 634
middle
Search
first = 0
last = len(array) - 1
found = False
while(first <= last and not found):
mid = (first + last) // 2
if array[mid] == item :
found = True
else:
if item < array[mid]:
last = mid - 1
else:
first = mid + 1
print(found)
44
47 59 634
middle
59 634
7

8. Algorithm complexity

Источник: https://www.bigocheatsheet.com/
8

9.

Hash
9

10. Hash function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.
The values returned by a hash function are called hash values, hash codes, digests, or
simply hashes. The values are usually used to index a fixed-size table called a hash table.
A hash function should be:
• deterministic
• quickly calculated
• hard to invert
• (extra) uniform
• (extra) applicable
• (extra) etc.
10

11. Hash function

“Dog”
Hash function
C935D187F0B998EF720390F85014ED1E
“Dog was here”
Hash function
4A0D8D78A5144E1C712BE9D5E202C935
“Dog is here”
Hash function
6BE08BED83836AB70FD91636A0A71D29
11

12. Hash in Python

>>>hash(5)
5
>>>hash(5.2)
461168601842739205
>>>hash('string')
4282184674599114870
Hashable objects
>>>hash((1, 2, 3))
2528502973977326415
>>>hash(MyOwnCustomObject())
-9223371895723587417
Immutable
objects
>>>hash(sum)
154009903285
>>>hash([1, 2, 3])
TypeError: unhashable type:
'list'
12

13.

Dictionaries
13

14. Definition

Dictionary is an unordered set of key-value pairs.
Like lists, a dictionary stores only references to objects but not their values.
In Python, a dictionary is a hash-table.
Features:
• keys are unique
• quick search by key
• quick access by key
• order is not preserved*
• does not support search by value (out-of-box)
14

15. Initialization

>>> dict0 = {}
>>> dict0_1 = dict()
>>> dict1 = {'abc': 456}
>>> dict1_1 = dict(right_hand='sword', left_hand='shield')
>>> dict2 = {'abc': 123, 98.6: [3, 7]}
>>> dict3 = {'Alice': '2341', 'Beth': '9102', 'Cecil': '3258'}
15

16. Item access

my_dict = {
'Name': 'Zara',
'Age': 7,
'Class': 'First',
}
print("my_dict['Name']: ", my_dict['Name'])
print("my_dict['Age']: ", my_dict['Age'])
print("my_dict['Class']: ", my_dict['Class'])
16

17. Item update

my_dict = {
'Name': 'Zara',
'Age': 7,
'Class': 'First',
}
my_dict['Age'] = 8 # update existing entry
my_dict['School'] = "DPS School" # add new entry
print("my_dict['Age']: ", my_dict['Age'])
print("my_dict['School']: ", my_dict['School'])
17

18. Item removal

my_dict = {
'Name': 'Zara',
'Age': 7,
'Class': 'First',
}
del my_dict['Name']
my_dict.clear()
del my_dict
# remove entry with key 'Name’
# remove all entries in dict
# delete entire dictionary
18

19. Key properties

Key are unique.
my_dict = {'Name': 'Zara', 'Name': 'Manni'}
print(my_dict)
{'Name': 'Manni'}
19

20. Key requirements

my_dict = {'Digits': [1,2,3]}
print(my_dict['Digits'])
my_dict = {(1,2,3): [1,2,3]}
print(my_dict[(1,2,3)])
# BUT:
my_dict = {[3,4,5]: 'Some list'}
TypeError: unhashable type: 'list’
my_dict = {(1,2,[3,4,5]): 'Some tuple with list inside'}
TypeError: unhashable type: 'list'
20

21. Operations complexity

Python dictionaries have very fast element access and search:
Index
Search for
element (on
average)
Insert element
(on average)
Delete element
(on average)
Dict
O(1)
O(1)
O(1)
O(1)
List
O(1)
O(n)
O(n)
O(n)
21

22. Other methods

dict
clear()
copy()
fromkeys(iterable[,value])
get(key[,default])
items(), keys(), values()
pop(key[,default])
popitem()
setdefault(key[,default])
update(dict)
https://docs.python.org/3/library/stdtypes.html#mapping-types-dict
22

23.

Sets
23

24. Definition

Sets in Python are unordered collections of unique and hashable objects. In fact, they can be
considered as dictionaries without values.
Sets:
• give possibility to quickly remove duplicates since, by definition, they may contain only unique
elements;
• allow for various mathematical operations, such as union, intersection, and difference.
24

25. Initialization

>>> set0 = set()
>>> set1 = {1, 2, 3 }
>>> set2 = {'linux', 'python', 'go' }
>>> set3 = {'good', ('stuff', ), 42 }
>>> set4 = {1, 2, [3, 4]}
TypeError: unhashable type: 'list’
>>> set3 = set('good')
{'g', 'o', 'd'}
25

26. Item access

my_set = {'Python', 'and', 'Go', 'community'}
for item in my_set:
print(item)
==================================================
while my_set:
print(my_set.pop())
==================================================
>>> my_set[0]
TypeError: 'set' object is not subscriptable
26

27. Item addition

>>> my_set = {'C'}
>>> my_set.add('Python')
>>> my_set.update({'Go', 'Rust'})
>>> my_set
{'Go', 'Rust', 'C', 'Python'}
27

28. Item removal

>>> my_set = {'Python', 'Go', 'C', 'Rust'}
>>> my_set.remove('Rust')
>>> my_set.remove('Go')
>>> my_set
{'Python', 'C'}
28

29. Binary operator support

>>>fib = {1,2,3,5,8,13}
>>>prime = {2,3,5,7,11,13}
>>>fib | prime # Union
{1, 2, 3, 5, 7, 8, 11, 13}
>>>fib & prime # Intersection
{2, 3, 5, 13}
>>>fib ^ prime # Symmetric Difference
{1, 7, 8, 11}
29

30. Other methods

clear()
Set
copy()
difference(set, [set1, ...])
discard(item)
intersection(set, [set1, ...])
isdisjoint(set)
issubset(set)
issuperset(set)
symmetric_difference(set)
union(set)
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
30

31. frozenset

Frozen sets differ from sets only with the fact that frozen sets are immutable.
>>> frozen_set = {1, 2, 3}
>>> frozen_set.add(5)
AttributeError: 'frozenset' object has no attribute 'add'
31

32.

Functions
32

33. Function definition

Function is a code fragment that performs a specific task, packaged as a unit
Importance of function:
• abstraction,
• possibility to re-use the code,
• limited name space,
• possibility to use in any other place in project,
• logical unit
33

34. Function definition

def function_name(arguments):
"""optional_function_docstring"""
[function_suite]
return [expression]
34

35. Function definition

Parameter is a variable which is assigned with an input value while function call.
def function_name(a, b):
<do_something…>
Argument is a value itself which is passed to function while its call.
function_name(100, 200)
35

36. Argument types

Python 3.* - …:
Positional
arguments
Positional arguments
Positional with default value
Tuple of positional arguments
Keyword
arguments
Keyword arguments
Keyword with default value
Dictionary of keyword arguments
36

37. Argument types

>>> def foo(a, b=2, *c, d, e=4, **f):
...
Pass
>>> foo(1, 2)
TypeError: foo() missing 1 required keyword-only argument: 'd'
>>> foo(a=1, 2)
SyntaxError: positional argument follows keyword argument
>>> foo(1, d=2) # OK
>>> foo(d=2, 1)
SyntaxError: positional argument follows keyword argument
>>> foo(d=2, a=1) # OK IN 3.* - 3.7. Not ok in 3.8
37

38. Argument types

>>> def foo(pos1, pos2, /, pos_or_kwd, *, kwd1, kwd2):
_ _ _ _ _ _
_ _ _ _ _ _
_ _ _ _ _ _
|
|
|
|
Positional or keyword
|
|
Keyword only
Positional only
https://docs.python.org/3/tutorial/controlflow.html#defining-functions
https://docs.python.org/3/tutorial/controlflow.html#more-on-defining-functions
38

39. Arguments are passed by reference/value

In Python, arguments can be passed both by reference and by value.
If an object is immutable, it is passed by value:
• numeric types (int, float, complex)
• strings (str)
• tuples.
Mutable objects are passed by reference.
• list
• set
• dict.
39

40. Argument unpacking

>>> def func(a, b, c, d=False, *args, **kwargs):
...
print(a, b, c, d, args, kwargs)
...
>>> func(*[1,2,3,4,5], **{'6':7})
1 2 3 4 (5,) {'6': 7}
>>> func(*[1,2,3,], **{'d':7})
1 2 3 7 () {}
>>> func(1, 2, *[3,], **{'d':7})
1 2 3 7 () {}
40

41.

Anonymous functions
41

42. Anonymous functions

Literally, anonymous function is a function without a name.
In Python, anonymous function is created via using keyword lambda.
lambda [arg1 [,arg2,.....argn]]: expression
# Function definition
sum = lambda a, b: a + b
# Sum as a function
print("sum: ", sum(10, 20))
42

43. Anonymous functions usage

>>> numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> func = lambda x: x ** 2
>>> func(numbers[3])
16
>>> [func(item) for item in numbers]
[1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> [item**2 for item in numbers]
[1, 4, 9, 16, 25, 36, 49, 64, 81]
43

44. Anonymous functions usage

>>> animals = ['cat', 'dog', 'cow']
>>> caps = map(lambda x: x.upper(), animals))
>>> list(caps)
['CAT', 'DOG', 'COW']
>>> flt = filter(lambda x: 'o' in x, ['cat', 'dog', 'cow'])
>>> list(flt)
['dog', 'cow']
44

45.

Packing and Unpacking
in Python
45

46. Unpacking Tuples

>>> (a, b, c) = 1, 2, 3
>>> a, b, c = (1, 2, 3)
>>> a, b, c = 1, 2, 3
46

47. Unpacking Iterables

>>> a, b, c = '123'
>>> a
'1'
>>> b
'2'
>>> c
'3'
>>> a, b, c = [1, 2, 3]
>>> a
1
>>> b
2
>>> c
3
>>> gen = (i ** 2 for i in range(3))
>>> a, b, c = gen
>>> a
0
>>> b
1
>>> c
2
47

48. Unpacking dictionaries

>>> my_dict = {'one': 1, 'two':2, 'three': 3}
>>> a, b, c = my_dict # Unpack keys
>>> a
'one'
>>> b
'two'
>>> c
'three'
>>> a, b, c = my_dict.values()
>>> a
1
>>> b
2
>>> c
3
>>> a, b, c = my_dict.items()
>>> a
('one', 1)
>>> b
('two', 2)
>>> c
('three', 3)
48

49. The * Operator

>>> *a = 1, 2, 3
>>> a
[1, 2, 3]
>>> *a, b = 1, 2, 3
>>> a
[1, 2]
>>> b
3
>>> seq = [1, 2, 3, 4]
>>> first, *body, last = seq
>>> first, *body, last
(1, [2, 3], 4)
>>> my_tuple = (1, 2, 3)
>>> (0, *my_tuple, 4)
(0, 1, 2, 3, 4)
>>> my_str = '123'
>>> [*my_tuple, *my_str, *range(1, 4)]
[0, 1, 2, 3, 4, '1', '2', '3', 1, 2, 3]
49

50. The ** Operator

>>> numbers = {'one': 1, 'two':2, 'three': 3}
>>> letters = {'a': 'A', 'b': 'B', 'c': 'C'}
>>> new_dict = {**numbers, **letters}
>>> new_dict
{'one': 1, 'two':2, 'three': 3, 'a': 'A', 'b': 'B', 'c': 'C'}
More examples:
https://stackabuse.com/unpacking-in-python-beyond-parallel-assignment/
50

51. Q & A

Q&A