Python lists, dicts, tuples

dict in Python

Python dicts are a collection of key-value pairs implemented as hash tables. dicts can be updated in place and dictionaries can grow and shrink as needed.

Flattening a dict of dicts

quote_types = {
    'Bids' : {
        1 : [10, 45],
        2 : [25, 47.5],
        3 : [30, 49.5]
    },
    'Offers' : {
        1 : [30, 50.5],
        2 : [25, 52.5],
        3 : [10, 55]
    }
}

dict_of_height_3 ={
    'a' : {
        'b' :{
            'c' : 1,
            'd' : 2,
        },
        'e' : {
            'f' : 3,
            'g' : 4,
        }
    },
    'h' : {
        'i' : {
            'j' : 5,
            'k' : 6,
        },
        'l' : {
            'm' : 7,
            'n' : 8,
        },
    }
}

def flatten_dict(d : dict, parent_key = '', sep = '_'):
    result = {}
    for k,v in d.items():
        if (type(v) is dict):
            # Recursively flatten the child element
            child_flat_dict = flatten_dict(v, parent_key=str(k))

            # We now have a dict-of-dicts of height 2
            for child_k, child_v in child_flat_dict.items():
                key = parent_key + sep + child_k if parent_key > '' else child_k
                result[key] = child_v
        else:
            key = parent_key + sep + str(k)
            result[key] = v
            
    return result

print("flattening quotes\n")
flatten_dict(quote_types)

flattening quotes

{'Bids_1': [10, 45],
 'Bids_2': [25, 47.5],
 'Bids_3': [30, 49.5],
 'Offers_1': [30, 50.5],
 'Offers_2': [25, 52.5],
 'Offers_3': [10, 55]}

print("dict_of_height_3\n")
flatten_dict(dict_of_height_3)

dict_of_height_3

{'a_b_c': 1,
 'a_b_d': 2,
 'a_e_f': 3,
 'a_e_g': 4,
 'h_i_j': 5,
 'h_i_k': 6,
 'h_l_m': 7,
 'h_l_n': 8}

list() in Python

lists are mutable sequences typically used to store collections of homogenous items.

list.append(x:Any)->None adds a single-item to the end of the list, in-place. list.extend(Iterable)->None extends the list in-place by appending all items from the iterable, and returns None.

list.insert(i,x)->None inserts an element x at the given index i. list.remove(x) removes the first item from the list who value is equal to x. list.pop([i]) removes the item at the given position in the list and returns it. If no index is specified, list.pop() removes and returns the last element in the list.

Reverse a list

from typing import List
l = [1, 2, 3, 4, 5]

l.reverse()  # reverse in place
print(l)

[5, 4, 3, 2, 1]

# recursive solution
def reverse(l : List, acc : List = []) -> List:
    if(len(l) == 0):
        return acc
    
    if(len(l) == 1):
        l.extend(acc)
        return l
    
    new_acc = [l[0]]
    new_acc.extend(acc)
    return reverse(l[1:], new_acc)

def reverse_iter(l : List) -> List:
    result = []
    for element in l:
        result.insert(0, element)

    return result

items = [2, 17, 42, 15, 3]
reverse(items)

[3, 15, 42, 17, 2]

Determine if the list is a palindrome

from typing import List
def is_palindrome(l : List) -> bool:
    n = len(l)
    i = 0
    j = n - 1

    while(i <= j):
        if(l[i] != l[j]):
            return False
        
        i += 1
        j = n - i - 1

    return True

print(is_palindrome([1, 2, 3, 2, 1]))
print(is_palindrome([1, 2, 2, 1]))

True
True

Flatten a nested list

def flatten_list(l : List):
    result = []
    for element in l:
        if (type(element) is list):
            simple_list = flatten_list(element)
            result.extend(simple_list)
        else:
            result.append(element)
    return result

flatten_list(['a', ['b', ['c', 'd'], 'e']])

['a', 'b', 'c', 'd', 'e']

Eliminate consecutive duplicates of list elements

Always use key in my_dict directly instead of key in my_dict.keys(), if you want to check the existence of a key in a dict. That will use the dictionary’s \(O(1)\) hashing rather than \(O(n)\). my_dict.keys() returns a list of keys.

from typing import List

# Remove duplicates from a nested-list while preserving the
# the structure
def array_unique(l : List, unique_elements : dict={}) -> (List,dict):
    result = []
    for element in l:
        if type(element) is list:
            # get the list of unique children and append it to result
            child_list, unique_elements = array_unique(element, unique_elements=unique_elements)
            result.append(child_list)
        else:
            if element in unique_elements:
                continue
            else:
                result.append(element)
                unique_elements[element] = True

    return result, unique_elements

my_array = [1, [1, 2, [1, 2, 3], 4, 5], [5, 6], 7]
result, _ = array_unique(my_array)
result

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

List comprehensions

squares = [x**2 for x in range(5)]
print(squares)
combs = [(x,y,z) for x in range(2) for y in range(2) for z in range(2)]
print(combs)

[0, 1, 4, 9, 16]
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

Nested List comprehensions

matrix = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
]

# Take the transpose of a matrix
[[row[i] for row in matrix]for i in range(4)]

[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

tuples in Python

lists are mutable wherease tuples are immutable types. The contents of a tuple cannot be modified at run-time. They usually store a heterogenous collection of items.

sets in Python

Python also includes a data-type for sets. A set is an unordered collection with no duplicate elements. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations such as union, intersection, difference and symmetric difference.

Curly braces or set() is used to create sets.

a = set('abracadabra')
b = set('alcazam')

print(a)
print(a - b)
print(a | b)
print(a & b)

{'a', 'd', 'c', 'b', 'r'}
{'d', 'b', 'r'}
{'m', 'a', 'd', 'c', 'z', 'l', 'b', 'r'}
{'c', 'a'}

Python 3.8 walrus := operator

:= assigns a value to a variable and simultaneous returns the value. For example:

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

if (n := len(my_list)):
    print(f"The list has non-zero length = {n}")

The list has non-zero length = 5

Another motivating use-case is when looping over fixed-length blocks in a protocol parser.

# Loop over fixed length blocks
while (block := f.read(256)) != '':
    process(block)