Chapter 2: Data Structures

Question 1

What are container sequences? Provide examples.

Answer 1

Container sequences hold references to the objects they contain.
e.g list, tuple, collections.deque

Question 2

What are flat sequences? Provide examples.

Answer 2

Flat sequences store the value of its contents in its own memory space, not as distinct python objects
e.g str, bytes, array.array
The Python array is a single object, holding a C language array

Question 2

What are mutable sequences? Provide examples

Answer 2

Mutable sequences have methods that allow them to be mutated. Mutable sequences (virtually) inherit from MutableSequence, which in turn inherits from Sequences.
e.g list, bytearray, array.array, collections.deque
These methods include insert, append, reverse

Question 3

What are immutable sequences? Provide examples

Answer 3

Immutable sequences do not have methods that allow them to be mutated. Mutable sequences (virtually) inherit from Sequence.
e.g tuple, str, bytes

Question 4

What is the Walrus operator?

Answer 4

Assigns values to variables as part of a larger expression.
Can also be used during list comprehension to kep the variable in scope with the last value when the comprehension is finished

Question 5

Why may one use a generator expression in the place of a list comprehension?

Answer 5

A generator expression saves memory because it yields items one by one instead of building the whole list just to then feed another constructor

Question 6

What are the two key benefits of tuples?

Answer 6

Clarity - When a tuple is seen in code the programmer knows its length will never change.

Performance - A tuple uses less memory than a list of the same length. A list is allocated with room to spare to amortize the cost of future appends.

Also a tuple stores an array of references in the tuple struct, a list holds a pointer to the array of references stored elsewhere – this indirection is inefficient.

Question 7

Why is an array of floats more compact than a tuple of floats?

Answer 7

An array of floats is a single array object holding the raw value of the floats

A tuple of floats (a container sequence) is a tuple object with references to the float objects contained in it. Each float object has a value field and metadata fields.

Question 8

How could we mutate the contents of a tuple?

Answer 8

The contents of a tuple are immutable but that just means the references held by a tuple will always point to the same objects

We can mutate the referenced objects if they are mutable

Question 9

Why do slices and ranges exclude the last item?

Answer 9

• It’s easy to see the length of the slice or range when only the stop position is given
• It’s easy to compute the length of a slice or range when start and stop are given (stop - start)
• Easy to split a sequence in two parts at any index x
  my_list[:x] and my_list[x:]

Question 10

How can a string or list be reversed using slicing notation?

Answer 10

my_string[::-1]
Remember my_string[a:b:c]
a is start
b is stop
c is stride or step

Question 11

How is multidimensional slicing handling in python?

Answer 11

The __getitem__ and __setitem__ special methods recieve the indices in my_list[a, b] as a tuple.

my_list[a, b] calls my_list.__getitem__((a, b))

Question 12

What is the ellipsis (…) in Python?

Answer 12

It is a token recognised by the Python parser
It is not used in the Python standard library
Numpy uses it as a shortcut when slicing arrays of multiple dimensions

Question 13

How do the + and * operators work with sequences?

Answer 13

e.g a = [10, 20] + [30, 40]
Neither operand is modified
A new sequence of the same type is created as a result of the concatenation

Question 14

How does the += operator work with sequences?

Answer 14

+= works by calling the __iadd__ special method and fallback to __add__ if this is not implemented

In the case of mutable sequences, the sequence will be changed in place as __iadd__ effectively calls the extend method

If __iadd__ is not implemented a += b is the same as a = a + b
However a + b is evaluated first, producing a new object, which is bound to a

Question 15

What is the difference between list.sort and the sorted built-in?

Answer 15

list.sort methods sorts the list in place, without making a copy, and returns None

Question 16

When would an array be preferred over a list?

Answer 16

If a list contains only numbers an array.array if more efficient
- As lean as a C array only holds packed bytes representing floats as oppose to references to float objects
Initialised with a typecode and an iterable object array.array(‘d’, [1, ,3 ,4, 2, 5])
All items must be of the type specified by the typecode

Question 17

How can an array be sorted?

Answer 17

As of Python 3.10 there is no array in-place sort method. The array must be rebuilt:

a = array.array(a.typecode, sorted(a))

Question 18

What function can be used to insert into a sorted list?

Answer 18

import bisect
bisect.insort(my_list, item)
bisect.insort(my_list, item, key=lambda x: -x)

Question 19

What is memoryview in python?

Answer 19

A shared-memory sequence type
Allows memory to be shared between data structures without copying

Question 20

Why would a deque be preferred over a list?

Answer 20

Even though python lists have queue methods such as append and pop, inserting and removing the the head of a list is costly as the entire list must be shifted

Question 21

What sorting algorithm is used in sorted and list.sort?

Answer 21

Timsort
An adaptive algorithm that switches from insertion to merge sort strategies depending on how ordered the data already is
Worst case O(nlogn)