Practical advice for python3 algorithm practice

When dividing, be careful with large numbers

Sample: they should be different, but due to the float format, they become the same.

1
2
3
4
a = (1 - 500000000) / (1 - 499999999)
b = (500000000 - 1000000000) / (499999999 - 999999998)
print(a, b, a == b)
# 1.000000002 1.000000002 True

In this situation, we can just simply use Decimal.

1
2
3
4
5
from decimal import Decimal
a = Decimal(1 - 500000000) / Decimal(1 - 499999999)
b = Decimal(500000000 - 1000000000) / Decimal(499999999 - 999999998)
print(a, b, a == b)
# 1.000000002000000008000000032 1.000000002000000004000000008 False

How to create a matrix

Wrong method

1
2
3
4
5
6
7
8
# Wrong method (shallow copy)
list_two = [[0] * 3] * 3
print(list_two)
# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
list_two[1][1] = 2
print(list_two)
# [[0, 2, 0], [0, 2, 0], [0, 2, 0]]

Correct Method

1
2
3
4
5
6
7
# Correct method (deep copy)
list_three = [[0 for i in range(3)] for j in range(3)]
print(list_three)
# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
list_three[1][1] = 3
print(list_three)
# [[0, 0, 0], [0, 3, 0], [0, 0, 0]]

Useful tool classes in python3

defaultdict

A dict that has default value.

1
2
3
4
5
6
7
from collections import defaultdict
a = defaultdict(list)
b = defaultdict(lambda: [])
c = defaultdict(lambda: 0)
# b[0]: []
# c[0]: 0
# c[1] += 1  =>  c[1] == 1

Counter

A dict to auto-count items.

1
2
3
4
from collections import Counter
a = [1, 2, 3, 3]
b = Counter(a)
# b: Counter({3: 2, 1: 1, 2: 1})

More efficient way to code

for loop with value and index

1
2
3
4
5
6
# first way
for i in range(len(items)):
    pair = (i, items[i])
# second way: more efficient
for i, v in enumerate(items):
    pair = (i, v)

don’t use len() in for loop

1
2
3
4
5
6
7
# first way
for i in range(len(items)):
    print(items[i])
# second way: more efficient
n = len(items)
for i in range(n):
    print(items[i])

cache function value

@functools.cache(user_function)
Simple lightweight unbounded function cache. Sometimes called “memoize”.
Returns the same as lru_cache(maxsize=None), creating a thin wrapper around a dictionary lookup for the function arguments. Because it never needs to evict old values, this is smaller and faster than lru_cache() with a size limit.
For example:

1
2
3
4
5
from functools import cache

@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

Comments

⬆︎TOP