Recently I’ve been into competitive programming and I use Python3 to solve challenges. With the different challenges I encountered, I learnt to use Python efficiently during a competition. The goal is to : * fastly code what I want * fastly run what I want

In this post - which I use as a memo - I share advice on how to make faster code in Python3.

Useful functions

First let’s see a bunch of useful builtin functions.

map

This function is useful to apply a function on all the list members :

cities = ["Paris", "New York", "Barcelone", "Madrid", "Berlin"]
res = list(map(lambda x:len(x), cities))
print(res)

[5, 8, 9, 6, 6]

sorted

This function is really useful to sort a list because you can specify what field you only want to consider during the sorting operations.

objects = [("albert", 57), ("vanessa", 43), ("james", 24), ("harry", 22)]
res = sorted(objects, key=lambda x:x[1])
print(res)

[('harry', 22), ('james', 24), ('vanessa', 43), ('albert', 57)]

Protips : to check if a list is sorted, compare it with the output of the sorted function !

Dicts

One of the cool things about dicts is that it has an average complexity of O(1). You thus might want to use this instead of lists. Dicts are also really short to code and to use : setting or getting a variable is as simple as getting a list element !

flights = {
    "Paris": ["New York", "Tokyo", "Sao Paulo", "Rabat", "London", "Los Angeles"],
    "New York": ["Madrid", "Paris", "Rabat"],
    "Tokyo": ["Paris", "Los Angeles", "London"],
    "Sao Paulo": ["New York", "Paris", "London"],
    "Rabat": ["Paris", "New York", "Madrid"],
    "London": ["Paris", "New York", "Tokyo", "Sao Paulo", "Madrid"],
    "Madrid": ["Rabat", "Paris", "London"],
    "Los Angeles": ["Paris", "Los Angeles", "New York", "Tokyo"],
}

Sets

Lists are cool but can be very long to use if you have a lot of elements. In certain cases, you can use sets instead. In Python, sets are unsorted arrays composed of unique elements. It implements a lot of features which are really useful to work on sets of values, for example finding common values.

Sets are also extremely fast. Here are two codes which set two lists of 20k unique values and print the number of common elements.

With lists

list1 = [i for i in range(20000)]
list2 = [i**i for i in range(20000)]
ttl = 0
for i in list1:
    for j in list2:
        if i == j:
            ttl += 1
            break
print(ttl)

5
python3 /tmp/lists.py  64.69s user 0.15s system 99% cpu 1:04.97 total

That’s pretty long …

With sets

set1 = {i for i in range(20000)}
set2 = {i**i for i in range(20000)}
print(len(set1.intersection(set2)))

5
python3 /tmp/sets.py  36.49s user 0.16s system 99% cpu 36.708 total

We reduce the code length by 2 and the execution time by 2. And here a large part of those 36s consists of the 20k elements creation, but the rest of the operation (intersection) is almost instantly done.