Python Tricks - Black Magic - Part 1
Nov 23, 2019 • 10 Minute Read
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 some uncommon, advanced tricks in Python. These include amazing tricks related to what I like to call "black magic." Each Python trick is explained in two steps:
- A brief description of the concept and an interactive code example
- Some inspiring examples to enlighten you
Explanation of Black Magic
This guide covers some uncommon tricks, and many of them may have side effects. But these tricks are really cool and play a magical role in specific scenarios—so I call them "black magic" in the Python world. Due to the limitations of scenarios and the side effects, their main role is to open up your mind, light up your inspiration, and level up your Pythonic ability.
Once you weigh the pros and cons and know how to use them properly, some of them could become part of your code.
EAFP
This article, Idiomatic Python: EAFP versus LBYL, makes a good point about EAFP vs. LBYL:
EAFP (easier to ask for forgiveness than permission) means that you should just do what you expect to work and if an exception might be thrown from the operation then catch it and deal with that fact.
LBYL (look before you leap) is when you first check whether something will succeed and only proceed if you know it will work.
"""LBYL"""
if "key" in dict_:
value += dict_["key"]
"""EAFP"""
# downplays the importance of the key
try:
value += dict_["key"]
except KeyError:
pass
This obeys the Python's design philosophy: "Explicit is better than implicit."
The performance of EAFP is also acceptable in Python:
But since exceptions are used for control flow like in EAFP, Python implementations work hard to make exceptions a cheap operation, and so you should not worry about the cost of exceptions when writing your code.
Unlike other black magic tricks, this is a recommended coding style in Python.
EAFP is a legitimate coding style in Python and you should feel free to use it when it makes sense.
Let's write a Fibonacci example in a Pythonic style. We will provide the result with generator and iterate in EAFP style.
"""pythonic fibonacci"""
# generator function
def fibonacci(n):
a, b, counter = 0, 1, 0
while counter <= n:
yield a
a, b = b, a + b # multiple assignment
counter += 1
f = fibonacci(5)
# EAFP
while True:
try:
print (next(f), end=" ")
except StopIteration:
break
# output: 0 1 1 2 3 5
Inspiring Examples
"""used in detect cycle in linked list"""
# L141: determine there is a cycle in a linked list
def has_cycle_in_linked_list(head: ListNode) -> bool:
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False
"""used in binary search and insert"""
# L334: given an unsorted array return whether an increasing subsequence (incontinuous) of length k exists or not in the array.
def increasing_triplet(nums: List[int], k: int) -> bool:
try:
inc = [float('inf')] * (k - 1)
for x in nums:
inc[bisect.bisect_left(inc, x)] = x
return k == 0
except:
return True
"""used in eval"""
# L301: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
def remove_invalid_parentheses(s: str) -> List[str]:
def isvalid(s):
try:
eval('0,' + ''.join(filter('()'.count, s)).replace(')', '),'))
return True
except:
pass
level = {s}
while True:
valid = list(filter(isvalid, level))
if valid:
return valid
level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
self assist
This is a trick of dynamic property. The cost is a little intrusive, as it pollutes the original structure.
Inspiring Example
Use self as the dummy node in a linked list.
"""reuse self to save the cost of dummy node"""
def traverse_linked_list(self, head: TreeNode) -> TreeNode:
pre, pre.next = self, head
while pre.next:
self.process_logic(pre.next)
return self.next # return head node
eval
eval() executes arbitrary strings as Python code. But note that eval may become a potential security risk.
Inspiring Example
Build a tree constructor and use eval to execute.
# L536: construct binary tree from string
def str2tree(s: str) -> TreeNode:
def t(val, left=None, right=None):
node, node.left, node.right = TreeNode(val), left, right
return node
return eval('t(' + s.replace('(', ',t(') + ')') if s else None
str.find
This is a clever use of str.find. Although this usage is not very generalizable, the idea can be used for reference.
Inspiring Example
We use find to construct a mechanism: if val is '#' return 1, if not return -1.
# L331: verify preorder serialization of a binary tree, if it is a null node, we record using a sentinel value #
def is_valid_serialization(preorder: str) -> bool:
need = 1
for val in preorder.split(','):
if not need:
return False
need -= ' #'.find(val)
return not need
str.replace
Use str.replace to implement a string version's union-find (disjoint-set).
Inspiring Example
Compared with ordinary union-find, this string version is concise, elegant, and efficient.
"""convert int to unicode char, and use str.replace to merge the connected nodes by reduce"""
# L323: given n nodes from 0 to n - 1 and a list of undirected edges, find the number of connected components in an undirected graph.
def count_connected_components(n: int, edges: List[List[int]]) -> int:
return len(set(reduce(lambda s, edge: s.replace(s[edge[1]], s[edge[0]]), edges, ''.join(map(chr, range(n))))))
^ (xor)
^ is usually used for removing even exactly same numbers and save the odd, or save the distinct bits and remove the same.
Inspiring Examples
These examples illustrate some amazing usages of ^.
"""Use ^ to remove even exactly same numbers and save the odd, or save the distinct bits and remove the same."""
"""bit manipulate: a^b^b = a"""
# L268: Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
def missing_number(nums: List[int]) -> int:
res = 0
for i, e in enumerate(nums):
res = res ^ i ^ e
return res ^ len(nums)
"""simply find the first index whose "partner index" (the index xor 1) holds a different value."""
# L540: find the single element, in a sorted array where every element appears twice except for one.
def single_non_duplicate(nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]
"""parity in triple comparisons"""
# L81: search a target in a rotated sorted array
def search_in_rotated_sorted_arr(nums: List[int], target: int) -> int:
"""I have three checks (nums[0] <= target), (target <= nums[i]) and (nums[i] < nums[0]), and I want to know
whether exactly two of them are true. They can't all be true or all be false (check it), so I just need to
distinguish between "two true" and "one true". Parity is enough for that, so instead of adding them I xor them"""
self.__getitem__ = lambda i: (nums[0] <= target) ^ (nums[0] > nums[i]) ^ (target > nums[i])
i = bisect.bisect_left(self, True, 0, len(nums))
return i if target in nums[i:i+1] else -1
Conclusion
In this guide, we have learned some black magic Python tricks, such as EAFP, eval, xor, and advanced skills for some built-in functions. I hope some of them will be useful for you.
In PArt 2, we will continue to learn about other black magic Python tricks. You can also download an example notebook, black_magics.ipynb, from Github.
This guide is one of a series of Python tricks guides:
- Python Tricks - Introduction
- Python Tricks - Basic - Part 1
- Python Tricks - Basic - Part 2
- Python Tricks - Iterable - Part 1
- Python Tricks - Iterable - Part 2
- Python Tricks - Black Magic - Part 1
- Python Tricks - Black Magic - Part 2
I hope you enjoyed it. If you have any questions, you're welcome to contact me at recnac@foxmail.com.