Author avatar

Recnac

Python Tricks - Iterable - Part 1

Recnac

  • Nov 23, 2019
  • 8 Min read
  • 24 Views
  • Nov 23, 2019
  • 8 Min read
  • 24 Views
Data
Python

Introduction

Editor's note: This guide is part of a series on useful Python tricks. Read more about the series and find links the other guides here.

In this guide, we will begin learning iterable tricks in Python, including advanced skills related to iterables. Each Python trick is explained in two steps:

  1. A brief description of the concept and an interactive code example
  2. Some inspiring examples to enlighten you

Construct Iterator

Here are some refined definitions of iterators picked up from Hackaday:

An iterator is an object which represents a stream of data. Technically, it is an object that has an __iter__ and a __next__ method.

An iterable is something which is able to iterate. In practice, an iterable is an object which has an __iter__ method, which returns an iterator. strings, lists, files, and dictionaries are all examples of iterables.

Inspiring Example

This example is a very creative usage for an iterator. in function loops through the same iterator to make sure every character is checked just once sequentially.

1
2
3
4
5
"""construct iterator to make sure check every char only once by 'in' """
# L392: check if s is subsequence of t. s = "abc", t = "ahbgdc", return true.
def is_subsequence(s: str, t: str) -> bool:
    t = iter(t)
    return all(c in t for c in s)
python

Construct Generator

Generators provide an easy, built-in way to create instances of iterators. We can build a generator by calling a function that has one or more yield expressions. We can also construct a generator with agenerator expression in a comprehension way, which we will discuss below.

Generators do not store all the values in memory; they generate values on the fly. This is the lazy evaluation technique we discussed in the Python Tricks - Basic guide.

Inspiring Examples

To simplify the logic, we can construct the result as a generator style.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""generate all combinations of coins which sum to target amount"""
def get_coin_changes(coins: List[int], amount[int]) -> List[List[int]]:
    for i, coin in enumerate(coins):
        if coin == amount:
            yield (coin,)
        elif coin < amount:
            yield from ((coin,) + x for x in change(coins[i:], amount - coin))

"""generate all combinations of well-formed n pairs of parentheses"""
# L22: generate all combinations of well-formed n pairs of parentheses.
def generate_parenthesis(n: int) -> List[str]:
    def generate(p, left, right):
        if 0 <= left <= right:
            if not right:
                yield p
            for q in generate(p + '(', left-1, right): yield q
            for q in generate(p + ')', left, right-1): yield q
    return list(generate('', n, n))
python

Comprehension

The comprehension technique provides a short and concise way to construct new sequences (such as lists, set, dictionary, etc.) based on existing sequences.

Python provides the following four types of comprehensions:

1
2
3
4
5
6
7
8
9
10
11
"""list comprehension"""
odds_list = [x for x in range(20) if x % 2]

"""generator_expression"""
odds_generator = (x for x in range(20) if x % 2)

"""set comprehension"""
odds_set = {x for x in range(20) if x % 2}

"""dict comprehension"""
square_dict = {x: x**2 for x in range(10)}
python

Inspiring Examples

The following examples demonstrate the advanced skills of constructing a list comprehension. They also show various application scenarios.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""bfs in list comprehension way"""
# L515: find the largest value in each row of a binary tree
def find_largest_in_binary_tree_rows(root: TreeNode) -> List[int]:
    maxes, row = [], [root]
    while any(row):
        maxes.append(max(node.val for node in row))
        row = [kid for node in row for kid in (node.left, node.right) if kid]
    return maxes

"""rotate image by list comprehension"""
# L48: rotate the image by 90 degrees (clockwise)
def rotate_image_90_degrees(matrix: List[List[int]]) -> None:
    matrix[:] = [[row[i] for row in matrix[::-1]] for i in range(len(A))]

"""generate combinations by list comprehension recursively"""
# L77: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
def combine(n: int, k: int) -> List[List[int]]:
    if k == 0:
        return [[]]
    # add last element
    return [pre + [i] for i in range(k, n + 1) for pre in combine(i - 1, k - 1)]

"""generate binary trees by list comprehension recursively"""
# given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
def generate_binary_search_trees(last: int, first: int=1) -> List[TreeNode]:
    def node(val, left, right):
        node = TreeNode(val)
        node.left = left
        node.right = right
        return node
    return [node(root, left, right) 
            for root in range(first, last+1)
            for left in generate_binary_search_trees(root-1, first)
            for right in generate_binary_search_trees(last, root+1)] or [None]
python

lambda

lambda function, also called anonymous function, is a single expression with implicit return. lambda functions can have any number of arguments but only one expression.

1
lambda arguments : expression
python

Inspiring Examples

The following examples show various application scenarios for lambda.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""lambda used in lexical closure"""
def make_adder(n):
    return lambda x: x + n

plus_3 = make_adder(3)
plus_3(4)
# output: 7

"""lambda used in key"""
# sort dict by value
d = {'apple': 18, 'orange': 20, 'banana': 5, 'rotten tomato': 1}
sorted(d.items(), key=lambda x: x[1])
# alternative
from operator import itemgetter
sorted(d.items(), key=itemgetter(1))
# output: [('rotten tomato', 1), ('banana', 5), ('apple', 18), ('orange', 20)]

for pos in range(len(S)):
    """lambda used in filter"""
    matched_words = list(filter(lambda x: S[pos:].startswith(x), words))
    if matched_words:
        """lambda used in max"""
        add_interval([pos, pos + len(max(matched_words, key=lambda x: len(x)))])

"""call lambda in nested"""
# L422: given a sequence of words, check whether it forms a valid word square.
def valid_word_square(words: List[str]) -> bool:
    f = lambda x: map(None, *x)  # python 2
    return f(f(words)) == f(words)

"""use lambda to wrap parameter as callable"""
def wrapped_callable(f):
    if callable(f): return f
    else: return lambda: f
python

Conclusion

In this guide, we have learned many iterable Python tricks, such as iterator, generator, comprehension, and lambda. I hope some of them will be useful for you.

In Part 2, we will continue to learn about other iterable Python tricks.

You can also download an example notebook, iterables.ipynb, from Github.

This guide is one of a series of Python tricks guides:

I hope you enjoyed it. If you have any questions, you're welcome to contact me at [email protected]

0