{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Built-in Data Structures and Collections\n",
"![\"Open](\"https://colab.research.google.com/assets/colab-badge.svg\")
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"- all builtin functions are listed here with examples: https://docs.python.org/3/library/functions.html\n",
"\n",
"\n",
"## built-in ** zip() ** function\n",
"- built-in zip function can help us quickly create list of tuples and then a dictionary"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class zip in module builtins:\n",
"\n",
"class zip(object)\n",
" | zip(iter1 [,iter2 [...]]) --> zip object\n",
" | \n",
" | Return a zip object whose .__next__() method returns a tuple where\n",
" | the i-th element comes from the i-th iterable argument. The .__next__()\n",
" | method continues until the shortest iterable in the argument sequence\n",
" | is exhausted and then it raises StopIteration.\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __next__(self, /)\n",
" | Implement next(self).\n",
" | \n",
" | __reduce__(...)\n",
" | Return state information for pickling.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods defined here:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
"\n"
]
}
],
"source": [
"help(zip)"
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [],
"source": [
"zdata = zip([1, 2, 3], ('a', 'b', 'c'))"
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [],
"source": [
"alist = list(zdata)"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1, 'a'), (2, 'b'), (3, 'c')]"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"alist"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{1: 'a', 2: 'b', 3: 'c'}\n"
]
}
],
"source": [
"# create dict\n",
"adict = dict(alist)\n",
"print(adict)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## exercise\n",
"Create a dict that maps lowercase alphabets to integers, e.g., a maps to 1, b maps to 2, ..., z maps to 26 and print it"
]
},
{
"cell_type": "code",
"execution_count": 82,
"metadata": {},
"outputs": [],
"source": [
"import string\n",
"lettersToDigits = dict(zip(string.ascii_lowercase, range(1, 27)))"
]
},
{
"cell_type": "code",
"execution_count": 83,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5, 'f': 6, 'g': 7, 'h': 8, 'i': 9, 'j': 10, 'k': 11, 'l': 12, 'm': 13, 'n': 14, 'o': 15, 'p': 16, 'q': 17, 'r': 18, 's': 19, 't': 20, 'u': 21, 'v': 22, 'w': 23, 'x': 24, 'y': 25, 'z': 26}\n"
]
}
],
"source": [
"print(lettersToDigits)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Set Types - set, frozenset\n",
"- https://docs.python.org/3/library/stdtypes.html#set \n",
"- as set object is an unordered collection of distinct hashable objects\n",
"- set is mutable\n",
"- frozenset is immutable"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"# create aset from a list\n",
"aset = set([1, 2, 1, 3, 'hello', 'hi', 3])"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# check the length of aset\n",
"len(aset)"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{1, 2, 3, 'hi', 'hello'}\n"
]
}
],
"source": [
"print(aset)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# membership test\n",
"'hi' in aset"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'Hi' in aset"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class set in module builtins:\n",
"\n",
"class set(object)\n",
" | set() -> new empty set object\n",
" | set(iterable) -> new set object\n",
" | \n",
" | Build an unordered collection of unique elements.\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __and__(self, value, /)\n",
" | Return self&value.\n",
" | \n",
" | __contains__(...)\n",
" | x.__contains__(y) <==> y in x.\n",
" | \n",
" | __eq__(self, value, /)\n",
" | Return self==value.\n",
" | \n",
" | __ge__(self, value, /)\n",
" | Return self>=value.\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __gt__(self, value, /)\n",
" | Return self>value.\n",
" | \n",
" | __iand__(self, value, /)\n",
" | Return self&=value.\n",
" | \n",
" | __init__(self, /, *args, **kwargs)\n",
" | Initialize self. See help(type(self)) for accurate signature.\n",
" | \n",
" | __ior__(self, value, /)\n",
" | Return self|=value.\n",
" | \n",
" | __isub__(self, value, /)\n",
" | Return self-=value.\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __ixor__(self, value, /)\n",
" | Return self^=value.\n",
" | \n",
" | __le__(self, value, /)\n",
" | Return self<=value.\n",
" | \n",
" | __len__(self, /)\n",
" | Return len(self).\n",
" | \n",
" | __lt__(self, value, /)\n",
" | Return self size of S in memory, in bytes\n",
" | \n",
" | __sub__(self, value, /)\n",
" | Return self-value.\n",
" | \n",
" | __xor__(self, value, /)\n",
" | Return self^value.\n",
" | \n",
" | add(...)\n",
" | Add an element to a set.\n",
" | \n",
" | This has no effect if the element is already present.\n",
" | \n",
" | clear(...)\n",
" | Remove all elements from this set.\n",
" | \n",
" | copy(...)\n",
" | Return a shallow copy of a set.\n",
" | \n",
" | difference(...)\n",
" | Return the difference of two or more sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in this set but not the others.)\n",
" | \n",
" | difference_update(...)\n",
" | Remove all elements of another set from this set.\n",
" | \n",
" | discard(...)\n",
" | Remove an element from a set if it is a member.\n",
" | \n",
" | If the element is not a member, do nothing.\n",
" | \n",
" | intersection(...)\n",
" | Return the intersection of two sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in both sets.)\n",
" | \n",
" | intersection_update(...)\n",
" | Update a set with the intersection of itself and another.\n",
" | \n",
" | isdisjoint(...)\n",
" | Return True if two sets have a null intersection.\n",
" | \n",
" | issubset(...)\n",
" | Report whether another set contains this set.\n",
" | \n",
" | issuperset(...)\n",
" | Report whether this set contains another set.\n",
" | \n",
" | pop(...)\n",
" | Remove and return an arbitrary set element.\n",
" | Raises KeyError if the set is empty.\n",
" | \n",
" | remove(...)\n",
" | Remove an element from a set; it must be a member.\n",
" | \n",
" | If the element is not a member, raise a KeyError.\n",
" | \n",
" | symmetric_difference(...)\n",
" | Return the symmetric difference of two sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in exactly one of the sets.)\n",
" | \n",
" | symmetric_difference_update(...)\n",
" | Update a set with the symmetric difference of itself and another.\n",
" | \n",
" | union(...)\n",
" | Return the union of sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in either set.)\n",
" | \n",
" | update(...)\n",
" | Update a set with the union of itself and others.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods defined here:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data and other attributes defined here:\n",
" | \n",
" | __hash__ = None\n",
"\n"
]
}
],
"source": [
"# see all the methods in set\n",
"help(set)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"aset.add(100)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{1, 100, 2, 3, 'hello', 'hi'}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"aset"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"# add 100 again; no effect as 100 already is a member of aset\n",
"aset.add(100)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{1, 100, 2, 3, 'hello', 'hi'}"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"aset"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"bset = frozenset(aset)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"frozenset({1, 100, 2, 3, 'hello', 'hi'})"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bset"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class frozenset in module builtins:\n",
"\n",
"class frozenset(object)\n",
" | frozenset() -> empty frozenset object\n",
" | frozenset(iterable) -> frozenset object\n",
" | \n",
" | Build an immutable unordered collection of unique elements.\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __and__(self, value, /)\n",
" | Return self&value.\n",
" | \n",
" | __contains__(...)\n",
" | x.__contains__(y) <==> y in x.\n",
" | \n",
" | __eq__(self, value, /)\n",
" | Return self==value.\n",
" | \n",
" | __ge__(self, value, /)\n",
" | Return self>=value.\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __gt__(self, value, /)\n",
" | Return self>value.\n",
" | \n",
" | __hash__(self, /)\n",
" | Return hash(self).\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __le__(self, value, /)\n",
" | Return self<=value.\n",
" | \n",
" | __len__(self, /)\n",
" | Return len(self).\n",
" | \n",
" | __lt__(self, value, /)\n",
" | Return self size of S in memory, in bytes\n",
" | \n",
" | __sub__(self, value, /)\n",
" | Return self-value.\n",
" | \n",
" | __xor__(self, value, /)\n",
" | Return self^value.\n",
" | \n",
" | copy(...)\n",
" | Return a shallow copy of a set.\n",
" | \n",
" | difference(...)\n",
" | Return the difference of two or more sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in this set but not the others.)\n",
" | \n",
" | intersection(...)\n",
" | Return the intersection of two sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in both sets.)\n",
" | \n",
" | isdisjoint(...)\n",
" | Return True if two sets have a null intersection.\n",
" | \n",
" | issubset(...)\n",
" | Report whether another set contains this set.\n",
" | \n",
" | issuperset(...)\n",
" | Report whether this set contains another set.\n",
" | \n",
" | symmetric_difference(...)\n",
" | Return the symmetric difference of two sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in exactly one of the sets.)\n",
" | \n",
" | union(...)\n",
" | Return the union of sets as a new set.\n",
" | \n",
" | (i.e. all elements that are in either set.)\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods defined here:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
"\n"
]
}
],
"source": [
"help(frozenset)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"intersection = bset.intersection(aset)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"frozenset({1, 100, 2, 3, 'hello', 'hi'})"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"intersection"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [],
"source": [
"cset = aset.copy()"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [],
"source": [
"cset.add(500)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{1, 2, 3, 100, 'hi', 'hello'}\n"
]
}
],
"source": [
"print(cset.intersection(aset))"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{1, 100, 2, 3, 500, 'hello', 'hi'}"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"cset.union(aset)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Collections\n",
"https://docs.python.org/3/library/collections.html#module-collections"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## deque\n",
"- list-like container with fast appends and pops on either end"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [],
"source": [
"from collections import deque"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"a = deque([10, 20, 30])"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [],
"source": [
"# add 1 to the right side of the queue\n",
"a.append(1)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"deque([10, 20, 30, 1])"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"# add -1 to the left side of the queue\n",
"a.appendleft(-1)"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"deque([-1, 10, 20, 30, 1, 1])"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class deque in module collections:\n",
"\n",
"class deque(builtins.object)\n",
" | deque([iterable[, maxlen]]) --> deque object\n",
" | \n",
" | A list-like sequence optimized for data accesses near its endpoints.\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __add__(self, value, /)\n",
" | Return self+value.\n",
" | \n",
" | __bool__(self, /)\n",
" | self != 0\n",
" | \n",
" | __contains__(self, key, /)\n",
" | Return key in self.\n",
" | \n",
" | __copy__(...)\n",
" | Return a shallow copy of a deque.\n",
" | \n",
" | __delitem__(self, key, /)\n",
" | Delete self[key].\n",
" | \n",
" | __eq__(self, value, /)\n",
" | Return self==value.\n",
" | \n",
" | __ge__(self, value, /)\n",
" | Return self>=value.\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __getitem__(self, key, /)\n",
" | Return self[key].\n",
" | \n",
" | __gt__(self, value, /)\n",
" | Return self>value.\n",
" | \n",
" | __iadd__(self, value, /)\n",
" | Implement self+=value.\n",
" | \n",
" | __imul__(self, value, /)\n",
" | Implement self*=value.\n",
" | \n",
" | __init__(self, /, *args, **kwargs)\n",
" | Initialize self. See help(type(self)) for accurate signature.\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __le__(self, value, /)\n",
" | Return self<=value.\n",
" | \n",
" | __len__(self, /)\n",
" | Return len(self).\n",
" | \n",
" | __lt__(self, value, /)\n",
" | Return self integer -- return number of occurrences of value\n",
" | \n",
" | extend(...)\n",
" | Extend the right side of the deque with elements from the iterable\n",
" | \n",
" | extendleft(...)\n",
" | Extend the left side of the deque with elements from the iterable\n",
" | \n",
" | index(...)\n",
" | D.index(value, [start, [stop]]) -> integer -- return first index of value.\n",
" | Raises ValueError if the value is not present.\n",
" | \n",
" | insert(...)\n",
" | D.insert(index, object) -- insert object before index\n",
" | \n",
" | pop(...)\n",
" | Remove and return the rightmost element.\n",
" | \n",
" | popleft(...)\n",
" | Remove and return the leftmost element.\n",
" | \n",
" | remove(...)\n",
" | D.remove(value) -- remove first occurrence of value.\n",
" | \n",
" | reverse(...)\n",
" | D.reverse() -- reverse *IN PLACE*\n",
" | \n",
" | rotate(...)\n",
" | Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods defined here:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data descriptors defined here:\n",
" | \n",
" | maxlen\n",
" | maximum size of a deque or None if unbounded\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data and other attributes defined here:\n",
" | \n",
" | __hash__ = None\n",
"\n"
]
}
],
"source": [
"help(deque)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## defaultdict\n",
"- dict subclass that calls a factory function to supply missing values"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [],
"source": [
"from collections import defaultdict"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [],
"source": [
"dd = defaultdict(int) # use 0 value to supply for missing key"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [],
"source": [
"# increment value of key 'a' by 1\n",
"dd['a'] += 1"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(int, {'a': 5})"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"dd"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## OrderedDict\n",
"- dict subclass that remembers the order entries were added"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [],
"source": [
"from collections import OrderedDict"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [],
"source": [
"od = OrderedDict([(1, 'one'), (2, 'two'), (3, 'three')])"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"OrderedDict([(1, 'one'), (2, 'two'), (3, 'three')])"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"od"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [],
"source": [
"od[100] = 'hundred'"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [],
"source": [
"od[-1] = 'negative one'"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"OrderedDict([(1, 'one'),\n",
" (2, 'two'),\n",
" (3, 'three'),\n",
" (100, 'hundred'),\n",
" (-1, 'negative one')])"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"od"
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class OrderedDict in module collections:\n",
"\n",
"class OrderedDict(builtins.dict)\n",
" | Dictionary that remembers insertion order\n",
" | \n",
" | Method resolution order:\n",
" | OrderedDict\n",
" | builtins.dict\n",
" | builtins.object\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __delitem__(self, key, /)\n",
" | Delete self[key].\n",
" | \n",
" | __eq__(self, value, /)\n",
" | Return self==value.\n",
" | \n",
" | __ge__(self, value, /)\n",
" | Return self>=value.\n",
" | \n",
" | __gt__(self, value, /)\n",
" | Return self>value.\n",
" | \n",
" | __init__(self, /, *args, **kwargs)\n",
" | Initialize self. See help(type(self)) for accurate signature.\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __le__(self, value, /)\n",
" | Return self<=value.\n",
" | \n",
" | __lt__(self, value, /)\n",
" | Return self reversed(od)\n",
" | \n",
" | __setitem__(self, key, value, /)\n",
" | Set self[key] to value.\n",
" | \n",
" | __sizeof__(...)\n",
" | D.__sizeof__() -> size of D in memory, in bytes\n",
" | \n",
" | clear(...)\n",
" | od.clear() -> None. Remove all items from od.\n",
" | \n",
" | copy(...)\n",
" | od.copy() -> a shallow copy of od\n",
" | \n",
" | items(...)\n",
" | D.items() -> a set-like object providing a view on D's items\n",
" | \n",
" | keys(...)\n",
" | D.keys() -> a set-like object providing a view on D's keys\n",
" | \n",
" | move_to_end(self, /, key, last=True)\n",
" | Move an existing element to the end (or beginning if last is false).\n",
" | \n",
" | Raise KeyError if the element does not exist.\n",
" | \n",
" | pop(...)\n",
" | od.pop(k[,d]) -> v, remove specified key and return the corresponding\n",
" | value. If key is not found, d is returned if given, otherwise KeyError\n",
" | is raised.\n",
" | \n",
" | popitem(self, /, last=True)\n",
" | Remove and return a (key, value) pair from the dictionary.\n",
" | \n",
" | Pairs are returned in LIFO order if last is true or FIFO order if false.\n",
" | \n",
" | setdefault(self, /, key, default=None)\n",
" | Insert key with a value of default if key is not in the dictionary.\n",
" | \n",
" | Return the value for key if key is in the dictionary, else default.\n",
" | \n",
" | update(...)\n",
" | D.update([E, ]**F) -> None. Update D from dict/iterable E and F.\n",
" | If E is present and has a .keys() method, then does: for k in E: D[k] = E[k]\n",
" | If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v\n",
" | In either case, this is followed by: for k in F: D[k] = F[k]\n",
" | \n",
" | values(...)\n",
" | D.values() -> an object providing a view on D's values\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Class methods defined here:\n",
" | \n",
" | fromkeys(iterable, value=None) from builtins.type\n",
" | Create a new ordered dictionary with keys from iterable and values set to value.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data descriptors defined here:\n",
" | \n",
" | __dict__\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data and other attributes defined here:\n",
" | \n",
" | __hash__ = None\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Methods inherited from builtins.dict:\n",
" | \n",
" | __contains__(self, key, /)\n",
" | True if the dictionary has the specified key, else False.\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __getitem__(...)\n",
" | x.__getitem__(y) <==> x[y]\n",
" | \n",
" | __len__(self, /)\n",
" | Return len(self).\n",
" | \n",
" | get(self, key, default=None, /)\n",
" | Return the value for key if key is in the dictionary, else default.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods inherited from builtins.dict:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
"\n"
]
}
],
"source": [
"help(OrderedDict)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## exercise\n",
"Create a dict that maps lowercase alphabets to their corresponding ASCII values , e.g., a maps to 97, b maps to 98, ..., z maps to 122 and print the dictionary in alphabetical order"
]
},
{
"cell_type": "code",
"execution_count": 85,
"metadata": {},
"outputs": [],
"source": [
"import string\n",
"lettersToDigits = dict(zip(string.ascii_lowercase, range(ord('a'), ord('z')+1)))"
]
},
{
"cell_type": "code",
"execution_count": 86,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'a': 97, 'b': 98, 'c': 99, 'd': 100, 'e': 101, 'f': 102, 'g': 103, 'h': 104, 'i': 105, 'j': 106, 'k': 107, 'l': 108, 'm': 109, 'n': 110, 'o': 111, 'p': 112, 'q': 113, 'r': 114, 's': 115, 't': 116, 'u': 117, 'v': 118, 'w': 119, 'x': 120, 'y': 121, 'z': 122}\n"
]
}
],
"source": [
"print(lettersToDigits)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Counter\n",
"- dict subclass for counting hashable objects"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [],
"source": [
"from collections import Counter"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [],
"source": [
"c = Counter('apple') # a new counter from an iterable"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'a': 1, 'p': 2, 'l': 1, 'e': 1})"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"c"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [],
"source": [
"# counter from iterable\n",
"d = Counter(['apple', 'apple', 'ball'])"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'apple': 2, 'ball': 1})"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"d"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [],
"source": [
"e = Counter({'apple': 10, 'ball': 20}) # counter from mapping"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'apple': 10, 'ball': 20})"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"e"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [],
"source": [
"f = c+e"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'a': 1, 'p': 2, 'l': 1, 'e': 1, 'apple': 10, 'ball': 20})"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"f"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [],
"source": [
"f = f+d"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({'a': 1, 'p': 2, 'l': 1, 'e': 1, 'apple': 12, 'ball': 21})"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"f"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('ball', 21), ('apple', 12), ('p', 2), ('a', 1), ('l', 1), ('e', 1)]"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"f.most_common()"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on class Counter in module collections:\n",
"\n",
"class Counter(builtins.dict)\n",
" | Counter(*args, **kwds)\n",
" | \n",
" | Dict subclass for counting hashable items. Sometimes called a bag\n",
" | or multiset. Elements are stored as dictionary keys and their counts\n",
" | are stored as dictionary values.\n",
" | \n",
" | >>> c = Counter('abcdeabcdabcaba') # count elements from a string\n",
" | \n",
" | >>> c.most_common(3) # three most common elements\n",
" | [('a', 5), ('b', 4), ('c', 3)]\n",
" | >>> sorted(c) # list all unique elements\n",
" | ['a', 'b', 'c', 'd', 'e']\n",
" | >>> ''.join(sorted(c.elements())) # list elements with repetitions\n",
" | 'aaaaabbbbcccdde'\n",
" | >>> sum(c.values()) # total of all counts\n",
" | 15\n",
" | \n",
" | >>> c['a'] # count of letter 'a'\n",
" | 5\n",
" | >>> for elem in 'shazam': # update counts from an iterable\n",
" | ... c[elem] += 1 # by adding 1 to each element's count\n",
" | >>> c['a'] # now there are seven 'a'\n",
" | 7\n",
" | >>> del c['b'] # remove all 'b'\n",
" | >>> c['b'] # now there are zero 'b'\n",
" | 0\n",
" | \n",
" | >>> d = Counter('simsalabim') # make another counter\n",
" | >>> c.update(d) # add in the second counter\n",
" | >>> c['a'] # now there are nine 'a'\n",
" | 9\n",
" | \n",
" | >>> c.clear() # empty the counter\n",
" | >>> c\n",
" | Counter()\n",
" | \n",
" | Note: If a count is set to zero or reduced to zero, it will remain\n",
" | in the counter until the entry is deleted or the counter is cleared:\n",
" | \n",
" | >>> c = Counter('aaabbc')\n",
" | >>> c['b'] -= 2 # reduce the count of 'b' by two\n",
" | >>> c.most_common() # 'b' is still in, but its count is zero\n",
" | [('a', 3), ('c', 1), ('b', 0)]\n",
" | \n",
" | Method resolution order:\n",
" | Counter\n",
" | builtins.dict\n",
" | builtins.object\n",
" | \n",
" | Methods defined here:\n",
" | \n",
" | __add__(self, other)\n",
" | Add counts from two counters.\n",
" | \n",
" | >>> Counter('abbb') + Counter('bcc')\n",
" | Counter({'b': 4, 'c': 2, 'a': 1})\n",
" | \n",
" | __and__(self, other)\n",
" | Intersection is the minimum of corresponding counts.\n",
" | \n",
" | >>> Counter('abbb') & Counter('bcc')\n",
" | Counter({'b': 1})\n",
" | \n",
" | __delitem__(self, elem)\n",
" | Like dict.__delitem__() but does not raise KeyError for missing values.\n",
" | \n",
" | __iadd__(self, other)\n",
" | Inplace add from another counter, keeping only positive counts.\n",
" | \n",
" | >>> c = Counter('abbb')\n",
" | >>> c += Counter('bcc')\n",
" | >>> c\n",
" | Counter({'b': 4, 'c': 2, 'a': 1})\n",
" | \n",
" | __iand__(self, other)\n",
" | Inplace intersection is the minimum of corresponding counts.\n",
" | \n",
" | >>> c = Counter('abbb')\n",
" | >>> c &= Counter('bcc')\n",
" | >>> c\n",
" | Counter({'b': 1})\n",
" | \n",
" | __init__(*args, **kwds)\n",
" | Create a new, empty Counter object. And if given, count elements\n",
" | from an input iterable. Or, initialize the count from another mapping\n",
" | of elements to their counts.\n",
" | \n",
" | >>> c = Counter() # a new, empty counter\n",
" | >>> c = Counter('gallahad') # a new counter from an iterable\n",
" | >>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping\n",
" | >>> c = Counter(a=4, b=2) # a new counter from keyword args\n",
" | \n",
" | __ior__(self, other)\n",
" | Inplace union is the maximum of value from either counter.\n",
" | \n",
" | >>> c = Counter('abbb')\n",
" | >>> c |= Counter('bcc')\n",
" | >>> c\n",
" | Counter({'b': 3, 'c': 2, 'a': 1})\n",
" | \n",
" | __isub__(self, other)\n",
" | Inplace subtract counter, but keep only results with positive counts.\n",
" | \n",
" | >>> c = Counter('abbbc')\n",
" | >>> c -= Counter('bccd')\n",
" | >>> c\n",
" | Counter({'b': 2, 'a': 1})\n",
" | \n",
" | __missing__(self, key)\n",
" | The count of elements not in the Counter is zero.\n",
" | \n",
" | __neg__(self)\n",
" | Subtracts from an empty counter. Strips positive and zero counts,\n",
" | and flips the sign on negative counts.\n",
" | \n",
" | __or__(self, other)\n",
" | Union is the maximum of value in either of the input counters.\n",
" | \n",
" | >>> Counter('abbb') | Counter('bcc')\n",
" | Counter({'b': 3, 'c': 2, 'a': 1})\n",
" | \n",
" | __pos__(self)\n",
" | Adds an empty counter, effectively stripping negative and zero counts\n",
" | \n",
" | __reduce__(self)\n",
" | Helper for pickle.\n",
" | \n",
" | __repr__(self)\n",
" | Return repr(self).\n",
" | \n",
" | __sub__(self, other)\n",
" | Subtract count, but keep only results with positive counts.\n",
" | \n",
" | >>> Counter('abbbc') - Counter('bccd')\n",
" | Counter({'b': 2, 'a': 1})\n",
" | \n",
" | copy(self)\n",
" | Return a shallow copy.\n",
" | \n",
" | elements(self)\n",
" | Iterator over elements repeating each as many times as its count.\n",
" | \n",
" | >>> c = Counter('ABCABC')\n",
" | >>> sorted(c.elements())\n",
" | ['A', 'A', 'B', 'B', 'C', 'C']\n",
" | \n",
" | # Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1\n",
" | >>> prime_factors = Counter({2: 2, 3: 3, 17: 1})\n",
" | >>> product = 1\n",
" | >>> for factor in prime_factors.elements(): # loop over factors\n",
" | ... product *= factor # and multiply them\n",
" | >>> product\n",
" | 1836\n",
" | \n",
" | Note, if an element's count has been set to zero or is a negative\n",
" | number, elements() will ignore it.\n",
" | \n",
" | most_common(self, n=None)\n",
" | List the n most common elements and their counts from the most\n",
" | common to the least. If n is None, then list all element counts.\n",
" | \n",
" | >>> Counter('abcdeabcdabcaba').most_common(3)\n",
" | [('a', 5), ('b', 4), ('c', 3)]\n",
" | \n",
" | subtract(*args, **kwds)\n",
" | Like dict.update() but subtracts counts instead of replacing them.\n",
" | Counts can be reduced below zero. Both the inputs and outputs are\n",
" | allowed to contain zero and negative counts.\n",
" | \n",
" | Source can be an iterable, a dictionary, or another Counter instance.\n",
" | \n",
" | >>> c = Counter('which')\n",
" | >>> c.subtract('witch') # subtract elements from another iterable\n",
" | >>> c.subtract(Counter('watch')) # subtract elements from another counter\n",
" | >>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch\n",
" | 0\n",
" | >>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch\n",
" | -1\n",
" | \n",
" | update(*args, **kwds)\n",
" | Like dict.update() but add counts instead of replacing them.\n",
" | \n",
" | Source can be an iterable, a dictionary, or another Counter instance.\n",
" | \n",
" | >>> c = Counter('which')\n",
" | >>> c.update('witch') # add elements from another iterable\n",
" | >>> d = Counter('watch')\n",
" | >>> c.update(d) # add elements from another counter\n",
" | >>> c['h'] # four 'h' in which, witch, and watch\n",
" | 4\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Class methods defined here:\n",
" | \n",
" | fromkeys(iterable, v=None) from builtins.type\n",
" | Create a new dictionary with keys from iterable and values set to value.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data descriptors defined here:\n",
" | \n",
" | __dict__\n",
" | dictionary for instance variables (if defined)\n",
" | \n",
" | __weakref__\n",
" | list of weak references to the object (if defined)\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Methods inherited from builtins.dict:\n",
" | \n",
" | __contains__(self, key, /)\n",
" | True if the dictionary has the specified key, else False.\n",
" | \n",
" | __eq__(self, value, /)\n",
" | Return self==value.\n",
" | \n",
" | __ge__(self, value, /)\n",
" | Return self>=value.\n",
" | \n",
" | __getattribute__(self, name, /)\n",
" | Return getattr(self, name).\n",
" | \n",
" | __getitem__(...)\n",
" | x.__getitem__(y) <==> x[y]\n",
" | \n",
" | __gt__(self, value, /)\n",
" | Return self>value.\n",
" | \n",
" | __iter__(self, /)\n",
" | Implement iter(self).\n",
" | \n",
" | __le__(self, value, /)\n",
" | Return self<=value.\n",
" | \n",
" | __len__(self, /)\n",
" | Return len(self).\n",
" | \n",
" | __lt__(self, value, /)\n",
" | Return self size of D in memory, in bytes\n",
" | \n",
" | clear(...)\n",
" | D.clear() -> None. Remove all items from D.\n",
" | \n",
" | get(self, key, default=None, /)\n",
" | Return the value for key if key is in the dictionary, else default.\n",
" | \n",
" | items(...)\n",
" | D.items() -> a set-like object providing a view on D's items\n",
" | \n",
" | keys(...)\n",
" | D.keys() -> a set-like object providing a view on D's keys\n",
" | \n",
" | pop(...)\n",
" | D.pop(k[,d]) -> v, remove specified key and return the corresponding value.\n",
" | If key is not found, d is returned if given, otherwise KeyError is raised\n",
" | \n",
" | popitem(...)\n",
" | D.popitem() -> (k, v), remove and return some (key, value) pair as a\n",
" | 2-tuple; but raise KeyError if D is empty.\n",
" | \n",
" | setdefault(self, key, default=None, /)\n",
" | Insert key with a value of default if key is not in the dictionary.\n",
" | \n",
" | Return the value for key if key is in the dictionary, else default.\n",
" | \n",
" | values(...)\n",
" | D.values() -> an object providing a view on D's values\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Static methods inherited from builtins.dict:\n",
" | \n",
" | __new__(*args, **kwargs) from builtins.type\n",
" | Create and return a new object. See help(type) for accurate signature.\n",
" | \n",
" | ----------------------------------------------------------------------\n",
" | Data and other attributes inherited from builtins.dict:\n",
" | \n",
" | __hash__ = None\n",
"\n"
]
}
],
"source": [
"help(Counter)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Exercises\n",
"### OrderedDict\n",
"1. Kattis problem: sort - https://open.kattis.com/problems/sort\n",
"- Trending Topic - https://open.kattis.com/problems/trendingtopic"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}