Data Structures in Python

Pros to Complex Types being included Natively

• Convenient, as you don’t have to implement the data structure or operations yourself

• Can lead to short and elegant solutions (parsimonious)

• Can lead to powerful programming paradigms (e.g. list based languages, functional programming paradigms)

Cons to Complex Types being included Natively

• Harder to understand performance underlying operations

• Generic implementations are rarely efficient for all tasks (data dependent)

• Can be harder to control run time behaviour (especially with respect to memory use or bounded resources)

Python Data Types

• Lists - Ordered, mutable, allows duplicate elements. Useful for sequences of data

• Tuples - Ordered, immutable, allows duplicate elements. Effectively immutable lists

• Sets - Unordered, mutable, contains unique elements. Useful for testing membership and eliminating duplicates from e.g. lists

• Dictionaries - Unordered, mutable, mapped by key-value pairs. Key-value pairs (think hash-table, where we look up the value for a given ‘key’)

Does Order Matter?

Sometimes:

• Every time we examine the queue the relative order of elements is preserved

• LIFO (queue) and FIFO (stack), and other ADTs (trees, heaps,…) order matters!

• For others, the internals are more opaque

Tuples

• marked by () parentheses, and may have 0 or more values

• variables are mutable, and can be changed

• the structure itself is not mutable, you can’t update it’s value

• accessing the first value in the structure using array subscript notation

Lists

• denoted by [], and are mutable

• can address the list as an array

• can update/assign values to a list

Data Types in Python are Objects

• have built in methods

• includes .append() a value, .extend() with another list

• can pop() values from it, insert() values within it

• the list is ordered, so we can build a queue or a stack, and even .sort() it

Data Structures Can do ‘Arithmetic’

Sets

Mutable, but unordered

• We can’t add sets, but we can union them! (with |)

• We can |= just like we can +=

• We can test if an element is in a set

• The order is not preserved, but uniqueness is

Elements

Can be any type, types can be nested

Name Value Pairs

Very useful

myDict = {'Adrian': 'is old', 'Saad': 'is young'}

• Creates a dictionary with two keys ‘Adrian’, and ‘Saad’

• Keys and values are both strings in this case

• myDict[‘Adrian’] returns ‘is old’

• myDict[‘Joe’] throws a KeyError

Functions

an entire data structure

def get_lecturers():
	return {'Adrian' : 18, 'Saad' : 21}

a nested data structure

def get_lectures():
	return [('Adrian', 18), ('Saad', 21)]

something inside a data structure

def get_age(name):
	return {'Adrian' : 18, 'Saad', 21}[name]

multiple values

def get_details():
	return 'Adrian', 18

Assignment

we can assign multiple variables

can pack and unpack data structures into and from variables

the number of variables corresponds to the number of elements we wish to unpack

Multiple Assignment

name, age = 'Saad', 21

Packing

x = 'Adrian', 18

Unpacking

name, age = x

Iterators

iter gets the iterator from an iterable

next gets the next element, if it can

finishes with ‘StopIteration’

Using a Loop for Iteration

call the iterator for us

can iterate through a data structure using ‘for’

for lists, sets and tuples this returns each element

Unpacking in Loops

can unpack a dictionary as (key, value) tuples

filter(function, iterable)

selects items from an iterable that satisfy a condition

input - a function that returns T/F, an iterable

output - iterator with only the items where function returns true

filter Example with Regular Function

grades = [50, 55, 45, 62, 30, 75]

def has_passed(grade):
	return grade >= 50

passed = list(filter(has_passed, grades))
#[50, 55, 62, 75]

filter Example with Lambda Function

grades = [50, 55, 45, 62, 30, 75]

passed = list(filter(lambda grade: grade >= 50, grades))
#[50, 55, 62, 75]

Lambda Function

lambda arguments : expression

small anonymous function

can take any number of arguments, but only one expression

map (function, iterable)

transforms each item in an iterable using a function

input - function to execute for each item and return new item, iterable

output - iterator with transformed items

map Example with Regular Function

passed = [50, 55, 62, 75]

def add_bonus(grade):
	return grade + 5

updated = list(map(add_bonus, passed))
#[55, 60, 67, 80]

map Example with Lambda Function

passed = [50, 55, 62, 75]

updated = list(map(lambda grade: grade + 5, passed))
#OR
updated = [grade + 5 for grade in passed]
#[55, 60, 67, 80]

reduce (function, iterable[, initialiser])

reduces the iterable to a single value by applying the function cumulatively

input - function that takes 2 arguments and performs an operation on them, iterable, optional initialiser as a starting value for the operation

output - single value

reduce Example with Regular Function

numbers = [1, 2, 3, 4, 5]

def add(x, y)
	return x + y

reduced = reduce(add, numbers)
#15

reduce Example with Lambda Function

numbers = [1, 2, 3, 4, 5]

reduced = reduce(lambda x, y: x + y, numbers)
#15

reduce Example with Operator Library Function

numbers = [1, 2, 3, 4, 5]

from operator import add
reduced = reduce(add, numbers)
#15