2-data-structures-discussion.md

% Data structures discussion
% Gökçe Aydos


# Review Python basics

##
<!-- interactive interpreter, autocompletion -->
you are working on the interactive interpreter and have a string called `name`. You are trying to remember a method you used before, but cannot remember its exact name. What could help? 

A) `name.<F1>`
A) `name?`
A) `name.<TAB>`
A) `name.<SPACE>`
A) I don't know


<!-- interactive interpreter, getting more info etc -->
##
`name` is a string. You type `name.<TAB>` and see multiple methods available. How can you get information about which arguments a method has?

A) `name.method<F1>`
A) `name.method<TAB>`
A) `name.method?`
A) `help(method)`
A) I don't know

. . .

- `help(name.method)` also works
- also try
  - `str.*find*?`
  - `*Warning?`


<!-- modules, running vs importing -->
##
`efficient_words.py`:
```py
...
def is_efficient(word):
	...
def main():
	...
if __name__ == '__main__':
	main()
```

How can we run `is_efficient()` in the interactive interpreter?

A) `python efficient_words.py; is_efficient('ball')`
A) `./efficient_words.py; is_efficient('ball')`
A) `import efficient_words; is_efficient('ball')`
A) `from efficient_words import is_efficient; is_efficient('ball')`
A) I don't know


<!-- File I/O, advantage context manager -->
##
why the following should be preferred
```py
with open('words.txt') as f:
	...
```
over this?:
```py
f = open('words.txt')
...
```

A) the file will be closed independent of errors
A) we have to write less code
A) is tremendously faster
A) the second example can lead to syntax errors
A) I don't know


# lists
##
<!-- list, properties -->
which property does not belong to lists?

A) mutable
A) frozen
A) ordered
A) finite
A) I don't know


<!-- list, what does mutable mean? -->
##

```py
cheeses = ['gouda']
cheeses.append('paneer')

cheeses    # outputs ['gouda', 'paneer']
```

Which property of `list`s does the behavior above prove?

A) mutable
A) frozen
A) ordered
A) finite
A) I don't know


<!-- list, what does finite mean? -->
##
we mentioned that *lists are finite*. What does this mean?

A) we can create only a finite amount of lists in a Python program
A) a list has a finite amount of items
A) the variable names can take finite amount of characters
A) there are finite amount of list types in Python
A) I don't know
<!-- when do we have an infinite structure? generator functions (lazy evaluation) -->


<!-- list, add-on to the mutability question: what does mutable mean? -->
##
which property of strings does the inequality of `cheeses` and `favorites` prove?
```py
cheeses = 'gouda'
favorites = cheeses
cheeses += ' paneer'

cheeses    # outputs 'gouda paneer'
favorites  # outputs 'gouda'
```

A) immutable
A) frozen
A) ordered
A) finite
A) I don't know
<!-- strings are immutable, and Python creates a new object for `favorites` to point at-->


## 
<!-- functions vs methods -->
which is not a list method?

A) `len()`
A) `append()`
A) `count()`
A) `extend()`
A) I don't know


##
<!-- list, sorting using a key -->
sort the following list from the longest name to the shortest:

*Hint*: possible using a single line

```py
names = ['Cora', 'Su', 'Hüseyin']
```

. . .

```py
names.sort(key=len, reverse=True)
names  # ['Hüseyin', 'Cora', 'Su']
```


##
<!-- insert() -->
a number is missing in the following list with increasing numbers and you want to amend it. Which code does work?
```py
years=[2019, 2020, 2022]
```

A) `years += 2021`
A) `years += [2021]`
A) `years[2] += [2021]`
A) `years.insert(2, 2021)`
A) I don't know


##
<!-- in-place vs returning a new object -->
what is the output?
```py
names = ['Cora', 'Su', 'Hüseyin']
sorted(names, key=len)
names
```

A) `KeyError`
A) `['Su', 'Cora', 'Hüseyin']`
A) `['Cora', 'Su', 'Hüseyin']`
A) `['Hüseyin', 'Cora', 'Su']`
A) I don't know


##
<!-- reversing a list -->
Find three ways to reverse the following list:

*Hints*: `reversed()`, `reverse()`, `slicing`
```py
l=[1, 2, 3]
...
l  # outputs [3, 2, 1]
```

. . .

```py
list(reversed(l))
l[::-1]
l.reverse()
```


##
<!-- deleting, modifying lists -->
write code which corrects the quotation:
```py
kirk='Where yes monkey has gone sailing before!'
s=kirk.split()
s[...  # replace second and third words
...    # remove the second last word
...
```

. . .

[Quotation from Star Trek](https://en.wikipedia.org/wiki/Where_no_man_has_gone_before): 

> Space: the final frontier. These are the voyages of the starship Enterprise. Its five-year mission: to explore strange new worlds. To seek out new life and new civilizations. To boldly go where no man has gone before!

. . .

```py
s[1:3] = ['no', 'man']
del s[-2]  # or s.remove('sailing'), s.pop(-2)
' '.join(s)
```


##
<!-- shallow copy -->
```py
p1 = ['Helia', 1995]
p2 = ['Ram', 1993]
group1 = [p1, p2]
group2 = group1.copy()
group2[0].append('space')
group1, group2
```
A) ```py
([['Helia', 1995, 'space']],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995, 'space'], ['Ram', 1993]],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995], ['Ram', 1993]],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995], ['Ram', 1993]],
 ['space', ['Helia', 1995], ['Ram', 1993]])
```
A) I don't know

. . .

- this is called *shallow copy*. Also works: `group2 = group1[:]`


##
<!-- shallow copy only copies references -->
```py
p1 = ['Helia', 1995]
p2 = ['Ram', 1993]
group1 = [p1, p2]
group2 = group1.copy()
group2[0].append('space')
group1.pop()  # added compared to previous problem
group1, group2
```
A) ```py
([['Helia', 1995, 'space']],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995, 'space'], ['Ram', 1993]],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995], ['Ram', 1993]],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```
A) ```py
([['Helia', 1995], ['Ram', 1993]],
 ['space', ['Helia', 1995], ['Ram', 1993]])
```
A) I don't know

. . .

- alternative to shallow copy: [`copy.deepcopy()`](https://docs.python.org/3/library/copy.html?#copy.deepcopy)


##
<!-- deep copy digs deeper  -->
```py
from copy import deepcopy
p1 = ['Helia', 1995]
p2 = ['Ram', 1993]
group1 = [p1, p2]
group2 = deepcopy(group1)
group2[0].append('space')
group1, group2
# outputs:
([['Helia', 1995], ['Ram', 1993]],
 [['Helia', 1995, 'space'], ['Ram', 1993]])
```


# tuples

##
<!-- difference between tuples and lists -->
which is false?

A) lists cannot be altered but tuples can
A) both tuples and lists can store heterogeneous data (different datatypes)
A) packing and unpacking data is more convenient with tuples (we have to type less)
A) `enumerate()` returns a tuple
A) I don't know

. . .

- when we use `list`s as a collection, we tend to fill it with a single data type even `list`s support also heterogeneous data. The reason could be that we iterate over the collection and mostly apply similar operations on the items.

  tuples on the other hand contain usually heterogeneous data.

contd...

## 2

- tuples are usually used for *packing* and *unpacking* data. Lists can also be used for this purpose, but tuples are more convenient: `a,b,c = x`
- if you need a collection as a key to a `dict`, you would need a hashable (and therefore immutable) data structure like `tuple` or `frozenset`

more info: [data structures tutorial - tuples and sequences](https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences)

## 3

We said that lists can also be used for unpacking. Let us see some examples:

```py
x = [1, 2, 3]
print(x)
# outputs the list: `[1, 2, 3]`

print(*x)
# outputs print(x[0], x[1], x[2]): `1 2 3`
```

## 4

What about other containers?

```py
d = {1:'a', 2:'b', 3: 'c'}
x, y, z = d
print(x)  # outputs `1`
print(*d)  # outputs `1 2 3`

s = {1, 2, 3}
x, y, z = s
print(x)  # outputs `1`
print(*s)  # outputs `1 2 3`
```

Nice!

##
<!-- editing does not work on tuples, tuples can be defined w/o parantheses -->
What is the output?
```py
s = 'Hello', 12
s[0] = 'Namaste'
s
```

A) `TypeError`
A) `{'Namaste'}`
A) `('Namaste')`
A) `['Namaste']`
A) I don't know


##
<!-- unpacking values -->
what is the output?
```py
m1 = 'BRAF', 'P15056', 673
m2 = 'AKT1', 'P31749', 207
# ...
gene, _, entrez_id = m1
f'{gene} has the Entrez id {entrez_id}.'
```

A) `BRAF has the Entrez id 673.`
A) `BRAF has the Entrez id P31749`
A) `'BRAF' has the Entrez id 'P31749'`
A) `SyntaxError`
A) I don't know


##
<!-- swapping values in one step -->
```py
a = 0; b = 1
b = a; a = b
a, b  # outputs: (0, 0)
```
What is the output?
```py
a = 0; b = 1
a, b = b, a
a, b
```

A) `SyntaxError`
A) `(1, 0)`
A) `(0, 1)`
A) `(b, a)`
A) I don't know


##
<!-- using tuples as a key in dict -->
you want to create a mapping between ingredients and the meal. Which meals are edible? All of them. But how many are not edible for Python?
```py
meals = dict()
```

- `meals['water',] = 'water'`
- `meals[['water', 'heat']] = 'cooked water'`
- `meals['rice', 'water', 'heat'] = 'cooked rice'`
- `meals[{'milk', 'bacteria'}] = 'yogurt'`

A) 1
A) 2
A) 3
A) 4
A) I don't know


##
<!-- unpacking tuples into functions, star operation -->
```py
data = 'Elif', 'Sinatra', 1993

def db_add(forename, surname, birthyear):
	# appends the person to the database
	...
```
Which does not work?

A) `db_add(data[0], data[1], data[2])`
A) `db_add(birthyear=data[2], forename=data[0], surname=data[1])`
A) `db_add(data)`
A) `db_add(*data)`
A) I don't know



##
<!-- `enumerate()` -->
```py
l = [5, 3, 1, 2, 6, 4]
def bubble(numbers):
	# takes the first number (n = numbers[0])
	# swaps with its right neighbor if `n` greater
	# continues swapping n as long as it can

bubble(l)  # [3, 1, 2, 5, 6, 4]
```

. . .

explanation on next slide...


## 2

[Do not try to modify the list that you are looping on using an item](https://www.quora.com/Why-can’t-you-modify-lists-through-for-in-loops-in-Python), because the items will not be updated after starting the loop, e.g.:

```py
def bubble(numbers):
	for i, n in enumerate(numbers[:-1]):
		print(n, numbers[i+1], numbers[i:i+2])
		if n > numbers[i+1]:
			numbers[i:i+2] = numbers[i+1], n
		else:
			break
	return numbers
```

contd...


## 3

You see that the `n` does not get updated even we swap the items in the list. Correct solution is to use the item variable for the values in the original list, and store the first number in another variable.

```py
def bubble(numbers):
	first=numbers[0]
	for i, n in enumerate(numbers[:-1]):
		if i == 0:
			continue
		elif first > n:
			numbers[i-1], numbers[i] = n, first
		else:
			break
	return numbers
```


##
<!-- mutable object in a tuple -->
```py
directors = ['Craig Foster']
d = 'The Great Dance', 2000, directors
directors += ['Demon Foster']
d[2]
```
What is the output?

A) `TypeError: 'tuple' object does not support item assignment`
A) `IndexError: 'tuple' object items cannot be altered`
A) `['Craig Foster']`
A) `['Craig Foster', 'Demon Foster']`
A) I don't know

. . .

The tuple stores the reference, which does not change even we alter the list.


# dictionaries
##
<!-- how do we declare dictionaries? -->
In which case `d` is not a dict?

A) `d = {'Botswana' => 'Africa'}`
A) `d = {'Karoha Langwane' : 'San'}`
A) `d = dict()`
A) `d = {}`
A) I don't know


##
<!-- key vs value -->
which is wrong?

```py
d = {'Mounika' : 'LSI',
     'Adem' : 'LSI',
     'Sriraam' : 'MCS'}
``` 

A) the forenames in `d` are the keys of `d`
A) every key in a dict is unique
A) values can be of every datatype
A) keys can be of every datatype
A) I don't know

. . .

Python generates a hash (a unique number) out of each key which is not allowed to change during the lifetime of a dict. Therefore keys must be immutable.

Why can we only use immutable items? Couldn't we create a hash out of a `list`?

It is possible but then we would have to calculate the hash everytime we use the list as a key. You would had to pay attention that the list never changes. A better way is to not allow it at all by using for example `tuple`s.

Practically Python does not allow this [by looking for a method called `__hash__` to see if an object can be used as a key](https://stackoverflow.com/a/25193267).

##
<!-- similarity between dict and set -->
a dict stripped of its values corresponds to a:

A) list
B) set
C) tuple
D) defaultdict
A) I don't know

. . .

```py
d = {'a' : 'vowel, 'b' : 'consonant'}
set(d)  # outputs {'a', 'b'}
```


##
<!-- KeyError -->
```py
d = {'Kalahari desert' : ['springbok', 'vulture']}
d['Sahara desert'].append('desert fox')
d
```
What is the output?

A) `KeyError: 'Sahara desert'`
A) `IndexError: 'Sahara desert'`
A) ```py
{'Kalahari desert' : ['springbok', 'vulture'],
 'Sahara desert': ['desert fox']}
```
A) ```py
{['Kalahari desert', 'Sahara desert'] :
 ['springbok', 'vulture', 'desert fox']}
```
A) I don't know

. . .

<!-- avoiding keyerrors by using getting with default -->
How can we fix this?


## 2

- ```py
d['Sahara desert'] = []
d['Sahara desert'].append('desert fox')
```
- ```py
from collections import defaultdict
d = defaultdict(list)
# now every value will be automatically a list
d['Sahara desert'].append('desert fox')
```

which option do you find more convenient?

. . .

the first choice has more freedom. The values can have other datatypes than `list` compared to the second choice. The second choice makes sense if you already know that the dict will store `str`-`list` pairs. This approach could avoid wrong usage of the dict.


##
<!-- deleting elements -->
```py
character2house = {'Ron' : 'Gryffindor',
                   'Hermione' : 'Gryffindor',
                   'Draco' : 'Slytherin'}
for k, v in character2house.copy().items():
	if v == 'Gryffindor':
		### YOUR CODE HERE
```
Which code deletes all characters which belong to the house Gryffindor?

A) `del v`
A) `del k`
A) `character2house.pop(k)`
A) `character2house.popitem()`
A) I don't know

. . .

- we have to copy the dict, otherwise we could get a `RuntimeError: dictionary changed size during iteration`

...


## 2

- `del` cannot know which key to delete if the dict's name is not given
- `d.popitem()` returns the lastly added item and deletes it, so items with the keys `'Draco'` and `'Hermione'` will be removed instead of `'Ron'` and `'Hermione'`.
  - an *item* is a component of a collection. An item of a dict is a key-value pair.
  - note that `d.popitem(k, v)` does not exist. It would not make sense, because we can easily access items by their key


##
<!-- keys, values, items -->
`d` is a `dict`. Which iteration does not work?

A) `for k in d.keys()`
A) `for k, v in d`
A) `for v in d.values()`
A) `for k, v in d.items()`

<!-- TODO what if k,v are tuples in B) -->

. . .

-  `for k in d` iterates over the keys of `d`


##
<!-- d.copy() makes a *shallow* copy -->
```py
her = {'Lady Gaga' : ['pop'],
       'Mozart' : ['classic']}
mine = her.copy()
mine['Lady Gaga'].append('jazz')
her, mine
```
A) ```py
({'Lady Gaga': ['pop'], 'Mozart': ['classic']},
 {'Lady Gaga': ['pop', 'jazz'], 'Mozart': ['classic']})
```
A) ```py
({'Lady Gaga': ['pop', 'jazz'], 'Mozart': ['classic']},
 {'Lady Gaga': ['pop', 'jazz'], 'Mozart': ['classic']})
```
A) `TypeError`
A) ```py
({'Lady Gaga': ['pop'], 'Mozart': ['classic']},
 {'Lady Gaga': ['jazz'], 'Mozart': ['classic']})
```
A) I don't know


##
<!-- double star operation -->
```py
def f(a, b, c):
	return a**b + c
d1 = 2, 5, 10
d2 = {'b': 5, 'c': 6, 'a': 10}
```
which line does not output 42?

A) `f(d1)`
A) `f(d1[0], d1[1], d1[2])`
A) `f(*d1)`
A) `f(**d2)`
A) I don't know


# Sets

##
<!-- advantage: fast membership testing -->

which is not true?

A) a list can be converted to a set
A) a set can be converted to a list
A) an item can be found in roughly equal time in set and list, because sets are simply lists without duplicates
A) `set` has similar methods to the mathematical set operations, e.g., *intersection*
A) I don't know

. . .

- why are sets so fast? :racehorse:

## 2

- proof for fast membership testing

```py
l = [i for i in range(1_000_000)]
len(l)  # 1000000
s = set(l)
len(s)  # 1000000

%%timeit
0 in l
1000 in l
1_000_000 in l
# ~ 10 ms mean

%%timeit
0 in s
1000 in s
1_000_000 in s
# ~ 72 ns mean
```


##
<!-- set eliminates duplicates -->
The file `/usr/share/dict/catalan` contains words. Write code which

- converts the words to lowercase
- eliminates the duplicates
- stores the results as a collection of words to `words`
- writes them the file `/tmp/catalan_without_duplicates`:

```py
with open('/usr/share/dict/catalan') as f:
	### YOUR CODE HERE
```

. . .

```py
with open('/usr/share/dict/catalan') as f:
	words = {l.strip().lower() for l in f.readlines()}
```

- `set` eliminates duplicates


##
<!-- defining an empty set -->
which defines an empty set?

A) `{}`
A) `{pass,}`
A) `set()`
A) `()`
A) I don't know


##
<!-- converting a string to a set of letters -->
Print a word from `/usr/share/dict/usa` which contains all the English vowels:

```py
with open('/usr/share/dict/usa') as f:
	### YOUR CODE HERE
```

. . .

```py
vowels = set('aeiou')
with open('/usr/share/dict/usa') as f:
	while word := f.readline().strip().lower():
		letters = set(word)
		if letters >= vowels:
			print(word)
			break
# outputs: abstemious
```

:open_mouth:

> abstemious: eating and drinking in moderation



##
<!-- remove() vs discard() -->
You have a list of number sets and you want to remove the number `0` from all the sets. Which does work?
```py
number_sets = [ {5, 6, 1}, {2, 4, 0} ]
for s in number_sets:
	### YOUR CODE HERE
```

A) s.remove('0')
A) s.remove(0)
A) s.discard(0)
A) del s[0]
A) I don't know


##
<!-- how does Python differentiate dict and set definitions? -->
How many of the following is a set?

- `{}`
- `()`
- `set()`
- `{1: False}`
- `set([1,2,2])`

A) 1
A) 2
A) 3
A) 4
A) I don't know


##
<!--  | (union), - (difference), & (intersection) -->

Fill the gaps between `a` and `b`:

```py
a = {1, 2, 3}
b = {2, 3, 4}
a _ b = {1, 2, 3, 4}
a _ b = {1}
a _ b = {2, 3}
```

A) `|`, `-`, `&`
A) `+`, `-`, `&`
A) `-`, `&`, `+`
A) `U`, `-`, `&`
A) I don't know


##
<!-- a |= b-->
```py
a = {1, 2, 3}
b = {2, 3, 4}
c = {0, 5}
```
how many of the following creates a union of all sets and stores it in `a`?

- `a |= b|c`
- `a = a|b|c`
- `a = a.union(b,c)`
- `a += b+c`
- `a += a+b+c`

A) 1
A) 2
A) 3
A) 4
A) I don't know


##
Which datatypes do you know so far? :pen:

- **immutable**:
```








```
- **mutable**:
```








```