Python: Data Collections

Python produces a large number of useful data structures in its standard library, and more exotic data structures can usually be installed via pip from the Python Package Index.

Algorithmic Complexity

It is important to be familiar with the time complexity of these algorithms.

See Complexity of Python Operations for complexity of common data structures and operations.

Strings

A string can behave like an immutable data collection, consisting of characters.

Creation

name = 'Rumpelsttiltskin'

Indexing

name[:3]

'Rum'

name[-3:]

'kin'

name[3:-3]

'pelsttilts'

Concatenation

sentence = name + 'is a fairy tale by the Grimm Brothers'

sentence

'Rumpelsttiltskinis a fairy tale by the Grimm Brothers'

String methods

sentence.split()

['Rumpelsttiltskinis', 'a', 'fairy', 'tale', 'by', 'the', 'Grimm', 'Brothers']

'_'.join(sentence.split())

'Rumpelsttiltskinis_a_fairy_tale_by_the_Grimm_Brothers'

sentence.upper()

'RUMPELSTTILTSKINIS A FAIRY TALE BY THE GRIMM BROTHERS'

sentence.title()

'Rumpelsttiltskinis A Fairy Tale By The Grimm Brothers'

sentence.count('a')

3

sentence.replace('Brothers', 'Sisters')

'Rumpelsttiltskinis a fairy tale by the Grimm Sisters'

Reversing a string

''.join(reversed(sentence))

'srehtorB mmirG eht yb elat yriaf a sinikstlittslepmuR'

sentence[::-1]

'srehtorB mmirG eht yb elat yriaf a sinikstlittslepmuR'

Multi-line strings

mls = """This is
a string with
many, many lines"""

mls

'This is\na string with\nmany, many lines'

print(mls)

This is
a string with
many, many lines

Tuples

• Immutable
• Useful as records
• Random access

Creating

paul = ('Paul', 'Graham', 45, 'paul.graham@duke.edu', 3.8, ('Mathematics', 'Statistics'))

Indexing

paul[0]

'Paul'

paul[-1]

('Mathematics', 'Statistics')

paul[2:4]

(45, 'paul.graham@duke.edu')

Immutable

try:
    paul[2] = 47
except TypeError as e:
    print(e)

'tuple' object does not support item assignment

Tuple unpacking

first, last, *stuff, gpa, (major, minor) = paul

first

'Paul'

last

'Graham'

stuff

[45, 'paul.graham@duke.edu']

gpa

3.8

major

'Mathematics'

minor

'Statistics'

Named tuples

Use named tuples for readability. Importantly, there are NO performacne differences compared with plain tuples.

Creating

from collections import namedtuple

Subject = namedtuple('subject', 'major minor')
Student = namedtuple('Student', 'first last age email gpa subject')

paul = Student('Paul', 'Graham', 45, 'paul.graham@duke.edu', 3.8,
               Subject('Mathematics', 'Statistics'))

paul

Student(first='Paul', last='Graham', age=45, email='paul.graham@duke.edu', gpa=3.8, subject=subject(major='Mathematics', minor='Statistics'))

Indexing

paul.first

'Paul'

paul[0]

'Paul'

paul.last

'Graham'

paul.subject

subject(major='Mathematics', minor='Statistics')

paul.subject.major

'Mathematics'

Lists

• Similar to tuples
• Mutable
• Often (but not necessarily) used to maintain collections of the same data type
• Workhorse of general Python data processing

Creating

words = ['the', 'quick', 'brown', 'fox']

words

['the', 'quick', 'brown', 'fox']

Indexing and unpacking

Same as for tuples.

words[-2:]

['brown', 'fox']

first, *rest, last = words

first, last

('the', 'fox')

seq = list(range(10))

seq

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

seq[1::2]

[1, 3, 5, 7, 9]

seq[::-2]

[9, 7, 5, 3, 1]

Modifying lists

As lists are mutable, they can be modified.

words[2]

'brown'

words[2] = 'blue'

words

['the', 'quick', 'blue', 'fox']

words[:2] = 'a', 'slow'

words

['a', 'slow', 'blue', 'fox']

Appending

words.append('jumps')

words

['a', 'slow', 'blue', 'fox', 'jumps']

Extending

words.extend(['over', 'the', 'lazy', 'dog'])

words

['a', 'slow', 'blue', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog']

Concatenation

[1,2] + [3,4] + [5,6]

[1, 2, 3, 4, 5, 6]

List methods

seq

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

seq.reverse()

seq

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

seq.sort()

seq

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

seq.extend([5,5,5])

seq

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 5, 5]

seq.count(5)

4

Conversion

paul2 = list(paul)

paul2

['Paul',
 'Graham',
 45,
 'paul.graham@duke.edu',
 3.8,
 subject(major='Mathematics', minor='Statistics')]

Dictionaries

• Use keys rather than positions to index

3 common ways of creating dictionaries

colors = {
    'red': (255,0,0),
    'green': (0,255,0),
    'blue': (0,0,255)
}

colors

{'blue': (0, 0, 255), 'green': (0, 255, 0), 'red': (255, 0, 0)}

colors = dict(red=(255,0), green=(0,255,0), blue=(0,0,255))

colors

{'blue': (0, 0, 255), 'green': (0, 255, 0), 'red': (255, 0)}

names = ['red', 'green', 'blue']
values = [(255,0,0), (0,255,0), (0,0,255)]

colors = dict(zip(names, values))

colors

{'blue': (0, 0, 255), 'green': (0, 255, 0), 'red': (255, 0, 0)}

Indexing

colors['blue']

(0, 0, 255)

Keys and values

colors.keys()

dict_keys(['red', 'green', 'blue'])

colors.values()

dict_values([(255, 0, 0), (0, 255, 0), (0, 0, 255)])

Adding to a dictionary

colors['black'] = (0,0,0)

colors

{'black': (0, 0, 0),
 'blue': (0, 0, 255),
 'green': (0, 255, 0),
 'red': (255, 0, 0)}

Merging dictionaries

Note that a key with the same name in the second dictionary will clobber the key in the first dictionary without warning.

more_colors = {
    'gray': ( 128,128,128),
    'maroon': (128,0,0),
    'black': (255, 255, 255)
}

colors.update(more_colors)

colors

{'black': (255, 255, 255),
 'blue': (0, 0, 255),
 'gray': (128, 128, 128),
 'green': (0, 255, 0),
 'maroon': (128, 0, 0),
 'red': (255, 0, 0)}

Counters

A counter is a special kind of dictionary for counting things.

from collections import Counter

dna = 'AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTGTCTGATAGCAGC'

c = Counter(dna)

c

Counter({'A': 20, 'C': 12, 'G': 17, 'T': 21})

c.most_common(2)

[('T', 21), ('A', 20)]

words = 'the the the quick brown fox jumps over the quick brown dog'.split()

wc = Counter(words)

wc.most_common(2)

[('the', 4), ('quick', 2)]

wc['brown']

2

Sets

A set corresponds to the mathematical idea of a set.

s1 = set(words)

s1

{'brown', 'dog', 'fox', 'jumps', 'over', 'quick', 'the'}

s2 = set('what does the fox say'.split())

s2

{'does', 'fox', 'say', 'the', 'what'}

s1 | s2

{'brown', 'does', 'dog', 'fox', 'jumps', 'over', 'quick', 'say', 'the', 'what'}

s1.union(s2)

{'brown', 'does', 'dog', 'fox', 'jumps', 'over', 'quick', 'say', 'the', 'what'}

s1 & s2

{'fox', 'the'}

s1.intersection(s2)

{'fox', 'the'}

s1 - s2

{'brown', 'dog', 'jumps', 'over', 'quick'}

s1.difference(s2)

{'brown', 'dog', 'jumps', 'over', 'quick'}

s2 - s1

{'does', 'say', 'what'}

s2.difference(s1)

{'does', 'say', 'what'}

Deques

Double ended queues. Sometimes you need to frequently add or remove items from both the left and right ends (list only lets you make changes to the right end).

from collections import deque

seq

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 5, 5]

deque(seq)

deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 5, 5])

Limited capacity deque

A queue shows first-in-first-out behavior.

dq = deque(seq, 5)
dq

deque([8, 9, 5, 5, 5])

Deque methods

dq.append(10)
dq

deque([9, 5, 5, 5, 10])

dq.appendleft(11)
dq

deque([11, 9, 5, 5, 5])

dq.pop()

5

dq

deque([11, 9, 5, 5])

dq.popleft()

11

dq

deque([9, 5, 5])

dq.rotate()

dq

deque([5, 9, 5])

Heap or Priority Queue

Some algorithms require adding and removing items from a priority queue. A heap or priority queue is a data structure that always generates the lowest priority item even with dynamic insertions of new items.

import heapq

items = [(3, 'A'), (1, 'B'), (2, 'C'),
         (3, 'D'), (1, 'E'), (2, 'F')]

heapq.heapify(items)

items

[(1, 'B'), (1, 'E'), (2, 'C'), (3, 'D'), (3, 'A'), (2, 'F')]

heapq.heappop(items)

(1, 'B')

heapq.heappop(items)

(1, 'E')

heapq.heappop(items)

(2, 'C')

heapq.heappush(items, (2, 'G'))
heapq.heappush(items, (1, 'H'))
heapq.heappush(items, (3, 'I'))

heapq.heappop(items)

(1, 'H')

heapq.heappop(items)

(2, 'F')

heapq.heappop(items)

(2, 'G')

items = [(3, 'A'), (1, 'B'), (2, 'C'),
         (3, 'D'), (1, 'E'), (2, 'F')]

heapq.nsmallest(3, items)

[(1, 'B'), (1, 'E'), (2, 'C')]

heapq.nlargest(3, items)

[(3, 'D'), (3, 'A'), (2, 'F')]

Trees

Trees are not available in the Python standard library, so we will use a 3rd party implementation.

! pip3 install --quiet anytree

from anytree import Node, RenderTree, Walker, PreOrderIter, PostOrderIter, LevelOrderIter
from anytree.dotexport import RenderTreeGraph

a = Node('a')
b = Node('b', a)
c = Node('c', a)
d = Node('d', b)
e = Node('e', b)
f = Node('f', c)
g = Node('g', c)
h = Node('h', f)

print(RenderTree(a))

Node('/a')
├── Node('/a/b')
│   ├── Node('/a/b/d')
│   └── Node('/a/b/e')
└── Node('/a/c')
    ├── Node('/a/c/f')
    │   └── Node('/a/c/f/h')
    └── Node('/a/c/g')

g = RenderTreeGraph(a, nodeattrfunc=lambda node: "shape=box")
g.to_picture('figs/tree.png')

Tree

c.ancestors

(Node('/a'),)

c.descendants

(Node('/a/c/f'), Node('/a/c/f/h'), Node('/a/c/g'))

c.parent

Node('/a')

c.children

(Node('/a/c/f'), Node('/a/c/g'))

w = Walker()

Find a path between two nodes

upwards, common, downwards = w.walk(e, h)

upwards

(Node('/a/b/e'), Node('/a/b'))

common

Node('/a')

downwards

(Node('/a/c'), Node('/a/c/f'), Node('/a/c/f/h'))

Iteration

[node for node in LevelOrderIter(a)]

[Node('/a'),
 Node('/a/b'),
 Node('/a/c'),
 Node('/a/b/d'),
 Node('/a/b/e'),
 Node('/a/c/f'),
 Node('/a/c/g'),
 Node('/a/c/f/h')]

[node for node in PreOrderIter(a)]

[Node('/a'),
 Node('/a/b'),
 Node('/a/b/d'),
 Node('/a/b/e'),
 Node('/a/c'),
 Node('/a/c/f'),
 Node('/a/c/f/h'),
 Node('/a/c/g')]

[node for node in PostOrderIter(a)]

[Node('/a/b/d'),
 Node('/a/b/e'),
 Node('/a/b'),
 Node('/a/c/f/h'),
 Node('/a/c/f'),
 Node('/a/c/g'),
 Node('/a/c'),
 Node('/a')]