Forem: Vitaly Shchurov

Python: using heapq module to find n largest items

Vitaly Shchurov — Fri, 25 Dec 2020 17:06:11 +0000

Today, I'm going to tell about using the heapq module. As you probably know, the easiest way to find the largest element in a collection in Python is by using the max() method. Or min() to find the smallest one. But what if you need to find n largest or smallest items? The solution depends on how large this n is comparing to the overall size of a collection.

Let's start with simpler cases. Later on, I'm going to give you more complicated examples, including one that requires some out-of-the-box thinking.

RELATIVELY SMALL N

If n is not about the same size as the passed-in collection, you might want to consider using the heapq library. It's equipped with nlargest(num, iterable) and nsmallest(num, iterable) functions, which are very easy to use. Let's see how they work on a list of numbers:



import heapq

nums = [-325, 252, 100, 0, 1, 128, 1000, -500, 879, 12, -57]
print('Largest:', heapq.nlargest(2, nums))
print('Smallest:', heapq.nsmallest(2, nums))

This will result in:



Largest:  [1000, 879]
Smallest:  [-500, -325]

By the way, these functions don't look for unique values. For example, if we had 1000 twice in our list, the largest result would be [1000, 1000].

RELATIVELY LARGE N

If n is almost the same size as the iterable, it's usually faster to just sort that collection and slice it:



import random

# generate a list with 110 arbitrary numbers within the given range:
nums = [random.randint(-100, 100) for _ in range(110)]

# sort, and then slice:
print('Largest 70 numbers:', sorted(nums)[-90:])
print('Smallest 70 numbers:', sorted(nums)[:90])

`heapq`: MORE ADVANCED EXAMPLES

LARGEST CITIES

The heapq example above was rather basic, but nlargest() and nsmallest() actually allow more complicated processing. The thing is that they can also accept a third optional key argument, which is a common parameter for a number of Python functions. key expects a function to be passed in (not a function call!), and this function serves as a comparison criteria that allows you to perform the operation on your own terms.

Let's try it on a list of dictionaries. We need two extract data on two world's largest cities, so we're interested in comparing their population only. To do that, we'll use lambda to specify that dictionaries with the biggest population number should be treated as the largest:



from pprint import pprint
import heapq

cities = [
    {'city': 'Cairo', 'country': 'Egypt', 'population': 20076000},
    {'city': 'São Paulo', 'country': 'Brazil', 'population': 21650000},
    {'city': 'Mumbai', 'country': 'India', 'population': 19980000},
    {'city': 'Mexico City', 'country': 'Mexico', 'population': 21581000},
    {'city': 'Tokyo', 'country': 'Japan', 'population': 37400068},
    {'city': 'Delhi', 'country': 'India', 'population': 28514000},
    {'city': 'Beijing', 'country': 'China', 'population': 19618000},
    {'city': 'Shanghai', 'country': 'China', 'population': 25582000},
]

largest = heapq.nlargest(2, cities, 
                         key=lambda x: x['population'])  # 1
print('Data on two largest cities in the world:')
pprint(largest)

# 1: here, the nlargest() will iterate through the dictionaries contained within the cities list. For each dictionary, we'll use the population key's value to compare them. Otherwise, Python will throw an error, because it can't just compare two dictionaries.

The result will be:



Data on two largest cities in the world:
[{'city': 'Tokyo', 'country': 'Japan', 'population': 37400068},
 {'city': 'Delhi', 'country': 'India', 'population': 28514000}]

HIGHEST-PAID EMPLOYEES

Now, having the employees dictionary, let's find three members of stuff with the highest salary. The problem is that if you pass in a dictionary, you won't get the result you might expect:



import heapq

employees = {
    'Susan Smith': 56000,
    'Matthew Jones': 60000,
    'Jim Taylor': 83000,
    'Emma Wilson': 150000,
    'Mary Thompson': 200000,
    'Chris Evans': 200000,
    'Andrew Evans': 200000,
    'John Evans': 150000,
}

top_paid = heapq.nlargest(3, employees)
print(top_paid)

The output will be:



['Susan Smith', 'Matthew Jones', 'Mary Thompson']

Wrong! None of these employees is among the three highest-paid ones. This happens because nlargest() iterated through the keys of the employees dictionary, which is normal for Python (for example, for loops iterate through the keys as well, by default). So, we iterated through the names only.

In case you're wondering why we didn't get Andrew Evans, it happened because in Python 'b' is bigger than 'a'. So, we got the names that appear later in the alphabet. To get it all right, we need to specify a key function:



top_paid = heapq.nlargest(3, employees, key=employees.get)

This time, we'll get the correct result:



['Mary Thompson', 'Chris Evans', 'Andrew Evans']

If you'd like to print salaries as well, you can pass dictionaries' items and use lambda like this:



top_paid = heapq.nlargest(3, employees.items(), key=lambda x: x[1])

The result will be:



[('Mary Thompson', 200000), ('Chris Evans', 200000), ('Andrew Evans', 200000)]

CHALLENGE

Now, let's have some fun! In the example above we retrieved a few highest-paid employees. The thing is, we didn't exactly get the names in alphabetical order, which is not very good for representation purposes. It's neater if Andrew Evans comes before, say Chris Evans in the output.

So, we still have to search for the highest salaries first, but if there's a tie, we need to compare the keys to put them in alphabetical order. For example, if you've got something like {'bread': 10, 'apple': 10}, you'll need to put apple first. As was mentioned earlier, the catch is that in Python:



>>> 'b' > 'a'
True

So, if you simply use nlargest(), it'll fail to sort your keys alphabetically when there's a tie. You can use nsmallest() instead, but you're still going to need the highest salaries... What do we do about it?

This is where the key parameter provides us with an excellent solution. Using it, we can write our own sorting function that can practically redefine nlargest() or nsmallest() a bit to get us what we want.



import heapq

employees = {
    'Susan Smith': 56000,
    'Matthew Jones': 60000,
    'Jim Taylor': 83000,
    'Emma Wilson': 150000,
    'Mary Thompson': 200000,
    'Chris Evans': 200000,
    'Andrew Evans': 200000,
    'John Evans': 150000,
}

def sort_key(x: tuple) -> tuple:   # 2
    return -x[1], x[0]

top_paid = heapq.nsmallest(4, employees.items(), key=sort_key)  # 1
print(top_paid)

# 1: We use nsmallest() here, so we can overcome the 'b' > 'a' constraint. So, in our final list we'll have, say, Adam before Bill. But we still have to pick the largest salaries...

# 2: And that's why we define our own sorting function that accepts a tuple as an argument, and returns it in reverse order (salary first, name second), and change the salary number to the opposite. For example, if we pass ('Susan Smith', 56000), we'll get (-56000, 'Susan Smith'). Why? So that nsmallest() can still find the biggest salaries instead of the smallest.

Remember that key only serves as a comparison criteria, it doesn't change the output. So, eventually, we'll get:



[('Andrew Evans', 200000), ('Chris Evans', 200000), ('Mary Thompson', 200000), ('Emma Wilson', 150000)]

As you can see, we got the top four salaries first, but the names are placed in alphabetical order!

One more thing, the possible downside to this solution is that using heapq.nsmallest() is less intuitive if we're talking about searching for the largest salaries, and, hence, might be less readable. So, alternatively, you can opt for heap.nlargest(), but you'll need to update your sort_key() function:



def sort_key(x: tuple) -> tuple:
    return x[1], [-ord(i) for i in x[0]]

Here, instead of changing a salary to the opposite, you change each character's ordinal number. And ordinal numbers is how Python really compares letters:



>>> ord('b') > ord('a')
True
>>> -ord('b') < -ord('a')
True

`heapq`: UNDERLYING MECHANISM

Now, let's have a real quick look under the hood of the heapq module. Underneath, the functions we've just learned convert passed-in data into a list where items are ordered as a heap (a special data structure). Let's see how it works:



>>> import heapq
>>> nums = [-15, 123, 133, 0, 100, 222, 144, 56]
>>> heapq.heapify(nums)
>>> nums
[-15, 0, 133, 56, 100, 222, 144, 123]

heapq.heapify orders our nums list as a heap here, but it doesn't exactly sort it. The important feature of a heap as a data structure is that its first element (heap[0]) is always the smallest item. You can use this to easily access the next smallest item by popping it and heapifying the list again:



>>> heapq.heappop(nums)
-15
>>> heapq.heappop(nums)
0
>>> nums
[56, 100, 133, 123, 144, 222]
>>> heapq.heappop(nums)
56

56 wasn't the third in the queue to leave our wonderful collection, but it got to the beginning as soon as it became the smallest number. Needless to say, it wouldn't have worked with the list method .pop(), because the point is that the list is being heapified after popping an item. It requires O(log n) operations where n is the size of the heap.

Now, you know how to use the heapq library. To sum it all up, I prepared a little cheat sheet for you.

Hope you enjoyed my post! If you did, don't forget to like it. Thank you :)

Python tips: playing with round()

Vitaly Shchurov — Wed, 23 Dec 2020 09:06:13 +0000

You have probably already worked with the Python built-in round() function. It takes a number as an argument and simply rounds it. But depending on its second parameter, the function can actually perform a range of rounding calculations with different types of precision. As you'll see later, you can even pass negative numbers as parameters.

To begin with, round() can simply take one value as a required argument to perform a standard rounding operation:

>>> round(1.2489)  # <- returns the nearest integer
1
>>> round(1.5)
2
>>> round(2.5)
2

If rounding both 1.5 and 2.5 to 2 is not precise enough for you, round() accepts the second parameter to represent the number of digits from the decimal point you wish your number to be rounded to. Just like that:

>>> num = 1.28372
>>> round(num, 1)
1.3
>>> round(num, 2)
1.28
>>> round(num, 3)
1.284

We can now round the numbers from the chunk of code above more precisely:

>>> round(1.2489, 2)
1.25
>>> round(1.5, 2)
1.5
>>> round(2.5, 2)
2.5

The more interesting thing is that round() also accepts negative numbers as the second argument and, in this case, rounding takes place for tens, hundreds, thousands, and so on:

>>> num = 274895
>>> round(num, -1)
274900
>>> round(num, -2)
274900
>>> round(num, -5)
300000

And a bit more surprisingly:

>>> round(num, -6)
0

If you pass in a floating point value with a negative parameter, the function will return a float instead of an integer:

>>> num = 274895.56
>>> round(num, -1)
274900.0
>>> round(num, -2)
274900.0

Hope you enjoyed my post! If you did, don't forget to like it. Thank you :)

Python guide to using generators more

Vitaly Shchurov — Thu, 17 Dec 2020 14:06:50 +0000

When writing a function that's supposed to return a sequence of results, returning some data structure like a list or dictionary is often the most obvious choice, yet not necessarily the most effective one. Sometimes, it can be beneficial to design your functions as generators.

A QUICK REMINDER

If you know the basics, you can skip to the next section. To put it simply, a generator is a function that returns its result values one by one. This function is created using the keyword yield instead of return.

When reached, this keyword will pass back one result value, the function will remember its state and sleep until resumed to produce the subsequent value.

In fact, generators don't return the results themselves. If you just call them like a normal function, all you'll get is a generator object:

>>> def generator_func(seq):
        for num in seq:
            yield num   
>>> generator_func([1, 2, 3])
<generator object generator_func at 0x0000022BE0AA4848>

To get it working, you need to iterate over it in a for loop or using methods like next(), list(), set(), tuple().

>>> gen = generator_func([1, 2, 3])
>>> next(gen)
1

Another important feature is that generators exhaust themselves and raise a StopIteration exception when they run out of values to return.

>>> for remaining in gen:
        print(remaining)    
2
3

We only got 2 and 3, because 1 has already been yielded. Here, we don't see any exceptions, because for loops handle them under the hood. So do methods like list(), tuple(), sum(). The next() method doesn't, though:

>>> next(gen)
Traceback (most recent call last):
  File "<pyshell#16>", line 1, in <module>
    next(gen)
StopIteration

This particular generator is exhausted. To use the function again, you need a new generator object, which means you'll have to call the function again. Now, let's move on to why use generators at all.

WHY DESIGN A FUNCTION AS A GENERATOR?

There a few reasons to write your function as a generator rather than a normal return function:

Achieving better design clarity and readability (and sometimes, but not always, making it shorter).
A generator feeds the results to the calling code one by one instead of storing the entire data structure in memory (like lists do). In some cases, this can be a deciding factor (read more about it in my previous post.)
Separating processing data and using the results. Instead of compelling a function to interact with the output and return it, you separate functionality. A generator produces the data, and the calling code or some other function uses it. By the way, it's called decoupling interfaces, and it can boost your code's reusability.

To clarify the last point, let's imagine you wrote a function that produces a list, returns it to a calling function, which continues torturing the poor list :)

In case you need to make some future changes to your code, or even toss away the long-suffering list, because now you need a dictionary, you'll have to adjust all your code to the new reality.

However, if you design the processing function as a generator - all you return now is a generator object, which you may iterate over or turn into a data structure using methods like list(), set(), tuple(). And when you need to change something, you'll only be changing the calling code, while the generator can be left in peace.

PRACTICAL EXAMPLE

Let's see how it can be done in practice. Say we need to analyze the vocabulary of some text (you can use mine). Tasks like this can get pretty complicated, but we'll keep our code simple to focus on the issue at hand:

from collections import defaultdict
from pprint import pprint

def analyze_text(file: 'I/O',) -> dict:
    """ 
    Search text data for words according to a pattern,
    then add found words to a defauldict, and count their frequency.
    """
    frequency = defaultdict(int)
    pattern = ' \n\'",.;!?()@#$%^&*`~'
    for line in file:
        for word in line.split(' '):
            word = word.strip(pattern).lower()
            if word.isalpha():
                frequency[word] += 1
    return dict(frequency)

if __name__ == '__main__':
    with open('Sherlock Holmes.txt', 'r') as file:
        frequency = analyze_text(file)
    pprint(frequency)

This piece of code is not very flexible. Suppose, you'd want not only to do frequency analysis, but some further processing as well. In this case, you'll have to rewrite both the text_analyzer and the calling code. In real life, a few changes like that can lead to some messy code. Not to mention that if our file was much bigger, our current code would lead to a memory crash.

With a couple of minor changes, we can make our code more adjustable:

from collections import defaultdict
from pprint import pprint

def analyze_text(file: 'I/O', 
                 pattern = ' \n\'",.;!?()@#$%^&*`~') -> str:
    """ 
    Search text data for words according to a pattern, then
    yield found words.
    """
    for line in file:
        for word in line.split(' '):
            word = word.strip(pattern).lower()
            if word.isalpha():
                yield word

if __name__ == '__main__':
    frequency = defaultdict(int)
    with open('Sherlock Holmes.txt', 'r') as file:
        for word in analyze_text(file):
            frequency[word] += 1  # do the frequency counting here
    pprint(dict(frequency))

Now, the calling code and analyze_text do two completely different jobs. analyze_text breaks down any passed-in text file and returns each word one by one. It doesn't care what you're going to do with these words after that, it'll be the job of the calling code.

What's more, the second version is very well suited for working with processing huge amounts of data, because all the working memory a generator function requires is the maximum length of one line of input.

Interested to learn more advanced stuff on generators? Check out my previous post.

Hope you enjoyed my post. If so, please, don't forget to like it :)

Python: how to 'reuse' a generator?

Vitaly Shchurov — Wed, 16 Dec 2020 14:56:05 +0000

Generators can help you write reusable and scalable Python code, but the problem is that complicated processing often requires using the same data multiple times. However, the issue with generators is that they exhaust themselves, meaning they can produce results only once. Trying to retrieve new output from an exhausted generator will lead to a StopIteration exception.

Even more troubling is that for loops, list(), tuple(), set(), and many other functions in Python expect a StopIteration exception to be raised when passed-in generators are exhausted, which is why it's handled in these methods. So, you might find yourself in a situation when your code returns a wrong result, instead of throwing an error:

>>> gen = (x for x in range(5))
>>> sum(gen) * sum(gen)  # instead of an exception, we get 0:
0
>>> list(gen)  # an empty list here instead of an exception:
[]

We can use regular functions instead of generators, of course, but they won't be up to the challenge when it comes to processing enormous amounts of data, because of storing the entire output in memory.

Fortunately, Python has a couple of tricks up its sleeve. To make it simpler, I'll be starting from the easiest ways to solve our problem.

SOLUTION I: COPYING THE RESULTS

Suppose, you're doing a research for a supermarket chain and you have raw .txt data on one of the supermarket's check sums for a certain period of time, which looks like this:

122
78
161
64
# ...

You first need to calculate the average check before getting down to more serious analysis. If you'd like to practice yourself, you can download the file I used here.

Now, let's write a very simple program that will read each line from the file, convert it to a float, and then calculate the average check sum by dividing the total sum of money that customers spent in the supermarket by the number of checks (i.e., customers):

def average_check(gen: 'function') -> float:
    """ Calculate the average check per supermarket. """
    data = list(gen)
    return sum(data) / len(data)  # 1

def read_checks(path: str) -> float:
    """ Each line contains information about one check sum. """
    with open(path) as file:
        for line in file:
            yield float(line)

if __name__ == '__main__':
    avg = average_check(read_checks('checks.txt'))
    print(f'The average check is: {avg}')

# The result:
# The average check is: 100.543487

# 1: as you can see, we needed the data from the file twice, which is why we exhausted the iterator on purpose and kept a copy of its results in a list. It means we stored them all in memory, and that's exactly what we are trying to avoid in the first place. If we use this code on bigger datasets, we'll still get memory blowup. But for smaller data, this solution is perfectly acceptable.

SOLUTION II: USING LAMBDA

We can come to a more elegant solution to our problem:

def average_check(gen: 'function') -> float:
    """ Calculate the average check per supermarket. """
    spent: float = sum(gen())  # spent in total
    checks: int = sum(1 for _ in gen())  # count the number of purchases
    avg: float = spent / checks  # an average check
    return avg

def read_checks(path: str) -> float:
    """ Each line contains information about one check sum. """
    with open(path) as file:
        for line in file:
            yield float(line)

if __name__ == '__main__':
    avg = average_check(lambda: read_checks('checks.txt'))  # 1
    print(f'The average check is: {avg}')

# The result:
# The average check is: 100.543487

#1 : lambda keyword returns a function, so, on this line we expect a generator function to be passed in to average_check. We pass in the function without calling it! Only from within average_check we call it (twice): to count the total sum of purchases and the number of checks.

Notice, how I used a generator expression to count the number of checks checks: int = sum(1 for _ in gen()) instead of using a for loop. Generator expressions work the same as normal generators, they're just different in syntax.

This code won't cause a memory error if you need to process a huge number of checks for the whole supermarket chain. Now, while this solution requires less typing than the next one, it's still not the most elegant one. Also, remember that lambda expressions slow your code down a bit.

SOLUTION III: USING A CONTAINER CLASS

Python iterator protocol and object-oriented programming offer a better solution.

As you may know, iterable is an object that we can iterate over. In Python, the iterables are required to support the following methods. The __iter__() method creates (returns) an iterator object. To access this object and return the next item from it, the __next__() method is used. It's also responsible for raising a StopIteration exception once the iterator is exhausted. These two methods combined form the iterator protocol in Python, and its how Python for loops and other expressions traverse iterables.

The easiest way to implement the iterator protocol and create a special container class is to define the __iter__() method as a generator like this:

def average_check(gen) -> float:
    """ Calculate the average check per supermarket. """
    spent: float = sum(gen)  # spent in total
    checks: int = sum(1 for _ in gen)  # count the number of purchases
    avg: float = spent / checks  # an average check
    return avg

class ReadChecks:
    """ Convert each line to a float value, and yield it. """
    def __init__(self, path: str):
        self.path = path

    def __iter__(self) -> float:
        with open(self.path) as file:
            for line in file:
                yield float(line)

if __name__ == '__main__':
    it = ReadChecks('checks.txt')
    avg_check = average_check(it)
    print(f'The average check is: {avg_check}')

Our ReadChecks container works just fine when passed to the average_check function without any lambda keywords or other modifications. Although, implementing a container class requires additional lines of code, but it provides a cleaner interface, and it's faster than using lambda. Internally, each use of the gen argument creates a separate generator.

By the way, this code will successfully accept any iterable as an argument. If you put this code into the final part:

if __name__ == '__main__':
    checks = [100, 100, 100, 50, 50, 50]
    avg_check = average_check(checks)
    print(f'The average check is: {avg_check}')

You'll get:

The average check is: 75.0

The only problem is that if you pass an iterator, it'll be exhausted after sum(gen) that runs the entire generator and you may get an error or a wrong result. Try running that:

checks = [100, 100, 100, 50, 50, 50]
    avg_check = iter(checks)
    print(f'The average check is: {average_check(avg_check)}')

You'll get a ZeroDivisionError, because sum(1 for _ in gen) will return 0 (remember, sum() prevents raising a StopIteration exception).

So, we're in need of some error handling. To do that, we can use the following feature. When iterating over a generator, internally the iter() method is called, and the iteration protocol states if iter() gets an iterator as an argument, it'll return the very same iterator:

>>> num = [1, 2, 3]
>>> it = iter(num)
>>> iter(num) is iter(num)  # creates two different iterators
False
>>> iter(it) is iter(it)  # iter(it) returns the same it iterator
True

In the first example, we get two different iterators from the same sequence, but in the second one we passed in an iterator as an argument and the iter() function returned it back twice.

So, let's finalize our code:

def average_check(gen) -> float:
    if iter(gen) is iter(gen):
        raise TypeError('Cannot pass an iterator as an argument!')
    spent: float = sum(gen)  # spent in total
    checks: int = sum(1 for _ in gen)  # number of purchases
    avg: float = spent / checks  # an average check
    return avg

class ReadChecks:
    def __init__(self, path: str):
        self.path = path

    def __iter__(self) -> float:
        with open(self.path) as file:
            for line in file:
                yield float(line)

if __name__ == '__main__':
    it = ReadChecks('checks.txt')
    avg_check = average_check(it)
    print(f'The average check is: {avg_check}')

    checks = [100, 100, 100, 50, 50, 50]
    avg_check = average_check(checks)
    print(f'The average check is: {avg_check}')

    avg_check = iter(checks)
    print(f'The average check is: {average_check(avg_check)}')

The first two chunks will execute just fine, but in the third case our code will raise a TypeError exception to prevent returning a wrong result:

The average check is: 100.543487
The average check is: 75.0
# error feedback
TypeError: Cannot pass an iterator as an argument!

SPEED PERFORMANCE

One more thing you should keep in mind. Using data structures like lists is usually more efficient for smaller inputs, the generators are good when you need to provide scalability and avoid memory crashes when dealing with large datasets or if your code is interacting with a network and instead of waiting for the whole input, it can start processing and yielding the results as soon as they come. Read more about it in my post about using generator expressions over large list comprehensions.

Equipped with this, you can count the average checks for the whole world without your program crashing, if you so wish :) And do many other interesting things as well.

Enjoyed my post? Don't forget to leave a like, please :)

You can connect me on LinkedIn.

Python: avoid large list comprehensions

Vitaly Shchurov — Wed, 09 Dec 2020 21:11:23 +0000

As is well known, Python list comprehensions work faster than loops. However, there are situations when they can seriously damage your program's performance or even lead to a memory crash. In these cases, you might want to consider using generator expressions instead.

Syntactically, these two are very similar. The only difference between them is that you declare list comprehensions with [] and generator expressions with (), just like this:

list_compr = [x**2 for x in range(10)]
gen_expr = (x**2 for x in range(10))

The key point is that a list comprehension is evaluated where it occurs. As soon as we define a list comprehension in the interactive shell, we'll get the result list:

>>> [x**2 for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

A generator expression, in contrast, will return a generator object:

>>> (x**2 for x in range(10))
<generator object <genexpr> at 0x0000023DD840F7C8>

To get it working, we'll need to either use the next() method, iterate over a generator expression or use methods like list(), set(), or tuple().

In the examples above, using list comprehensions is actually more preferrable. When memory is not an issue, they outperform generator expressions.

The problem arises when you need to handle really large amounts of data, because list comprehensions store all their output in memory at once (as we've just seen in our code).

A generator, in contrast, is a concept designed to produce (yield) results one at a time instead of loading the entire data structure into memory. That makes possible working with huge datasets without a risk of blowup in memory usage.

It's also woth mentioning that generator expressions are especially useful with functions like sum(), min(), and max().

They also have another benefit. Generator expressions can easily be chained (composed) together, thus creating a data pipeline that can process massive amounts of data item by item.

However, they're not well suited for cases where you need to use the values more than once, because once a generator is exhausted, you can't access the values it produced.

Let's perform a small benchmark test and also see how generator expressions can be chained together. We're going to:
1) count the length of each line in a file,
2) then extract a square root from each line length,
3) sum up the square roots.
Of course, this example will be more instructional.

I'm going to use 'The Adventures of Sherlock Holmes' in a .txt format, which you can download here if you'd like to practice yourself. You can choose some other text file.

Let's use list comprehensions first:

import time

execution = []
for i in range(100):
    start = time.time()
    filename = 'Sherlock Holmes.txt'
    lengths = [len(line) for line in open(filename)]
    roots = [x**0.5 for x in lengths]
    print(sum(roots))
    end = time.time()
    execution.append(end-start)
print(f'Avg execution time with list comprehensions: '
      f'{sum(execution)/len(execution):.5f}')

With generator expressions, this code will look pretty much the same:

import time

execution = []
for i in range(100):
    start = time.time()
    filename = 'Sherlock Holmes.txt'
    lengths = (len(line) for line in open(filename))
    roots = (x**0.5 for x in lengths)
    print(sum(roots))
    end = time.time()
    execution.append(end-start)
print(f'Avg execution time with generator expressions: '
      f'{sum(execution)/len(execution):.5f}')

The second chunk will be run differently. Instead of producing the entire result on each line, Python will read one line from the file, then measure its length, and add it to the sum. Then the interpreter will proceed to the next line, and so on. This is exactly what chaining (composing) generator expressions into a data pipeline means.

So, let's run both versions:

Avg execution time with list comprehensions: 0.00486
Avg execution time with generator expressions: 0.00530

As you can see, on this dataset, list comprehensions run faster. But if I run the same code on a file that contains over 10 million lines on my machine, the outcomes will be different (I just copy-pasted the text in my Sherlock Holmes many times over):

Avg execution time with list comprehensions: 4.26855
Avg execution time with generator expressions: 3.79113

As you can see, in this case, generator expressions have beaten comprehensions :)

CONCLUSION

To sum up, generator expressions are more efficient when working with large datasets and can help your program avoid crashing. What's more, they're easily chained together, thus, creating data pipelines able to generate result values one by one.

At the same time, on smaller data (how much smaller - depends on the machine), list comprehensions usually outperform generator expressions, and they can be more useful if you need to access the produced data more than once.

If you feel like learning something else, check my previous post where I tell when it's good to use deques instead of lists.

Connect me on LinkedIn.

Python: deque vs. list

Vitaly Shchurov — Sun, 06 Dec 2020 20:07:14 +0000

Do you know how to keep track of the last five data points during some kind of processing instead of managing huge lists? How to append and pop items from the opposite ends of a data row faster and easier than with lists?

Today, I'm going to share with you all the how-tos of using the deque from the collections standard library module. First, we'll cover some basics, and then move on to solving problems. Hope you'll enjoy my post! If you do, please don't forget to like it :)

WHAT IS A DEQUE?

A list is one of the main workhorses in almost every Python script, yet, in some cases, opting for deques can lead to much faster performance. A deque is short for a double-ended queue, which is why it's called so. Double-ended means that it supports adding and removing elements from both ends.

In fact, deques are not entirely different from stacks and queues, they sort of integrate their features. This image may help you understand the distinction:

As you can see, deques are sort of a generalization of stacks and queues, but to see what deques really are in practice, we need to compare them with lists, so we won't be talking about stacks and queues anymore. To get the contrast between the two 'rivals', we're going to look more closely into how they're implemented under the hood.

Internally, deque is a representation of a doubly-linked list. Doubly-linked means that it stores at least two more integers (pointers) with each item, which is why such lists take up more memory space.

In contrast, lists in Python are implemented with fixed size memory blocks (arrays) and hence, they use less memory space than deques, but lists have to reallocate memory when a new item is inserted (except when appending).

DEQUE vs. LIST

This leads to the following distinctions in performance:

First, reallocation allows lists to access elements almost immediately by indexation. Using the Big-O notation, it can be measured as O(1).

If you're not familiar with the Big O notation, I'll just briefly inform you that it tells you how fast an algorithm (operation) works. It doesn't exactly measure time, but rather the possible maximum number of operations needed to perform a task.

O(1) means that it takes constant time to access data no matter how many elements are there. O(n) means that the more elements a structure holds, the longer it takes to find it. So, an O(1) algorithm is faster than O(n).

In our situation, a deque doesn't perform reallocation and to find an element by an index, internally Python will need to iterate over the deque. So, if there are n elements in the deque, the interpreter will have to carry out up to n operations in the worst-case scenario (if the element is at the very end). For lists, it's always O(1).

So, for accessing elements, lists are always a better choice, it's not at all what deques were designed for.

Second, because deques are implemented as doubly-ended arrays, they have the advantage when appending or popping from both the right and the left side of a deque (measured as O(1)).

It happens because internally only pointers should be corrected to insert a new node on a given position. It works just for the end sides, because anywhere else the interpreter will have to iterate over the deque, and it'll be O(n) time instead of O(1).

In contrast, lists don't have that luxury. Due to the reallocation, doing the same can take as many as O(n) operations. Well, actually, lists do support fast append and pop operations (measuread as O(1)), but only at the end.

Moreover, changes in the list trigger the reallocation process, which takes additional time on its own, while deque's append and pop performance is consistent, because it never uses reallocation.

So, when you need to add or remove elements from the 'head' or
'tail', use deques.

If your code doesn't process much data, this advantage of deques can be neglected, but it can have a significant performance boost if you process large amounts of data.

Third, deques are well suited for tracing the last occurrences or last elements of something (e.g., five latest client's transactions), because they allow to set the maximum length. Of course, it can be done using lists, but with deques, you already have the interface for that, and it's much faster.

It should also be mentioned that deques are thread-safe for appends and pops from opposite sides, because the append(), appendleft(), pop(), popleft() methods are atomic in CPython.

By the way, if you don't know much about threading, I recommend you to read my article where I explain the difference between threading and asyncio (so, you may shoot two birds with one stone and grasp both concepts if you don't know asyncio yet.)

A little cheat sheet to help you remember the performance difference between deques and lists:

To summarize the above,

Python lists are much better for random access and fixed-length operations, including slicing, while deques are much more useful for pushing and popping things off the ends, with indexing (but not slicing, interestingly) being possible but slower than with lists. (source)

PROBLEM SOLVING

Now, let's go through a couple of examples to see how it all works. I wouldn't explain the deque interface in detail, cause it's quite similar to what you've been doing with lists, and it's laid out very well in the collections documentation.

TRACING LAST TRANSACTIONS

In many apps, you've probably seen something like 'Last visits', 'Previous songs', 'Latest articles'. Now, let's see how we can easily keep a history of the x last user transactions with a deque.

To see if it's working, we'll also store all transactions in a list so we can make sure that the last of them actually match those we'll put in our deque:



from collections import deque
from random import randint

ts_all = []  # to keep all transactions
ts_history = deque(maxlen=10)  # to keep only the latest
for i in range(30):
    ts_sum = randint(1, 10000)  # random transaction sum
    record = f'Transaction sum: {ts_sum} dollars.'
    ts_all.append(record)  # store the record in a list
    ts_history.append(record)  # store the record in a deque

# Let's print our transactions from the deque:
for ts in ts_history:
    print(ts)

# Now, make sure if our deque transactions match
# ten last transactions in the list:
assert list(ts_history) == ts_all[-10:]

The interpreter din't throw an error, so we can see that we got it right.

FIND A TEXT PATTERN WITH SOME PREVIOUS CONTEXT

Suppose we need to find a pattern in a text file, and provide it with some previous context (a couple of lines will do). In my code, I used 'The Adventures of Sherlock Holmes' in a .txt format, which you can download here for your own experiments. Somewhere in the text I put a phrase 'Harry Potter was there!' which is the pattern we're going to look for :)

We're all set to go:



from collections import deque

def search(text: 'IO', pattern: str, maxlen= 4):
    previous_lines = deque(maxlen=maxlen)
    for line in text:
        if pattern in line:
            yield line, previous_lines
        else:
            previous_lines.append(line)

if __name__ == '__main__':
    with open('Sherlock Holmes.txt', 'r') as file:
        pattern = 'Harry Potter was there!'
        for line, previous_lines in search(file, pattern):
            for item in previous_lines:
                print(item, end='')  # suppress extra new lines
            print(line)

After running the script, we'll get:



somewhere. I lay listening with all my ears. Suddenly, to my
horror, there was a distinct sound of footsteps moving softly in
the next room. I slipped out of bed, all palpitating with fear,
and peeped round the corner of my dressing-room door.
...Harry Potter was there!

I found a nice place to put my Harry Potter phrase and spoil the atmosphere of horror Conan Doyle worked so hard on :)

RETURN N LAST LINES OF A FILE

Now, as in the last example, let's see how to retrieve the last n lines from a file. I'll be torturing our Sherlock Holmes file again :)



from collections import deque

def tail(filename, n=6):
    'Return the last n lines of a file'
    with open(filename) as f:
        return deque(f, n)

if __name__ == '__main__':
    filename = 'Sherlock Holmes.txt'
    last_lines = tail(filename)
    for line in last_lines:
        print(line, end='')

After executing, we'll get three lines if we use poor Sherlock Holmes. Yes, we asked for six, but we've suppressed the empty lines with print(line, end=''):



interest in her when once she had ceased to be the centre of one

of his problems, and she is now the head of a private school at

Walsall, where I believe that she has met with considerable success.

SUMMARY

To sum it all up, in most use cases lists are fine. However, depending on specific tasks, there can be significant performance and thread safety advantages to a deque.

I hope you now understand how deques work. If you feel like learning some more interesting stuff about Python, I suggest you read my posts about starred expressions: the basics and problem solving parts.

Python starred expressions: practical challenges

Vitaly Shchurov — Sat, 05 Dec 2020 20:33:53 +0000

As I promised, I'm continuing my post on how to use starred expressions, this time with more practical and complicated examples.

RUNNING AN ONLINE SHOP

Let's write a simple programme that would calculate a discount for online orders. For ordinary purchases, we'll add up all customer's discounts (loyalty programme for regulars, promo codes, etc.). For special offers like a 30% or 50% discount, we'll just choose the biggest discount, otherwise your little shop will go bankrupt :)

The thing is, you don't know how many bonuses a customer might have, but you need to process them all. And that's how we'll do it:

data = [
    ('Abraham Lincoln', 'special', 50, 5, 25, 3, 15, 'address'),
    ('George Washington', 'regular', 5, 5, 'address'),
    ('Thomas Jefferson', 'regular', 10, 3, 'address'),
    ('James Maddison', 'special', 30, 10, 10, 'address')
]

def special_offer(discounts: list) -> int:
    """ We choose the biggest discount for a special offer. """
    return max(discounts)

def regular_offer(discounts: list) -> int:
    """ If there's no special offer, we sum up the discounts. """
    return sum(discounts)

if __name__ == '__main__':
    for line in data:
        customer, tag, *discounts, _ = line
        if tag == 'special':
            percent = special_offer(discounts)
        else:  # regular
            percent = regular_offer(discounts)
        print(f'Customer {customer} is offered a discount of {percent}%')

Let's execute the script:

Customer Abraham Lincoln is offered a discount of 50%
Customer George Washington is offered a discount of 10%
Customer Thomas Jefferson is offered a discount of 13%
Customer James Maddison is offered a discount of 30%

Nice, but we can do better! The interesting thing here is that in a for loop we have an implicit assignment, and we don't really need to assign line to variables in a separate line. So, let's rework our last chunk a bit:

if __name__ == '__main__':
    for customer, tag, *discounts, _ in data:
        if tag == 'special':
            percent = special_offer(discounts)
        else:  # regular
            percent = regular_offer(discounts)
        print(f'Customer {customer} is offered a discount of {percent}')

An implicit tuple assignment means that a row of variables customer, tag, *discounts is treated here as a tuple being assigned values, so you may as well type (customer, tag, *discounts) and nothing will change. It's just more comfortable not to use ().

Python's PEP 3132 offers us another example. It's a little abstract, though, but demonstrates the concept:

for a, *b in [(1, 2, 3), (4, 5, 6, 7)]:
    print(b)

After executing, you'll get:

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

SENDING A HOLIDAY CARD

Now, we'd like to send a holiday card to our online shop customers. See how clean our code looks when using *_ instead of awkward indexes with arbitrary-sized tuples:

data = [
    ('Abraham Lincoln', 'special', 50, 5, 25, 3, 15, 'address'),
    ('George Washington', 'regular', 5, 5, 'address'),
    ('Thomas Jefferson', 'regular', 10, 3, 'address'),
    ('James Maddison', 'special', 30, 10, 10, 'address')
]

if __name__ == '__main__':
    for customer, *_, address in data:
        print(f'A card for {customer} to some {address}')

DOING BUSINESS RESEARCH

Let's solve another problem. You're a data scientist conducting a research on salaries (or whatever) in local companies. You've got raw data strings containing a company name and impersonated data on each employee's salary there. Since each company has a different number of employees, you'd want to write code that would be able to process them all regardless of the number of the employees.

You can use a string method .split(), and extract a company name using .pop():

salaries = 'ImageInc|100000|110000|80000|60000|115000|250000|20000'
salaries = salaries.split('|')
company = salaries.pop(0)
print(company, salaries)

You'll get:

ImageInc ['100000', '110000', '80000', '60000', '115000', '250000', '20000']

Let's just use starred expressions:

data = 'ImageInc|100000|110000|80000|60000|115000|250000|20000'
company, *salaries = data
print(company, salaries)

Something wrong, eh? We forgot to split it, it's a string, so each character was treated as a value. Let's fix it:

data = 'ImageInc|100000|110000|80000|60000|115000|250000|20000'
company, *salaries = data.split('|')  # unpacking a list now

We've saved ourselves and our fellow programmers some time. Nice!

DAILY STUFF

Starred expressions are something that could be used quite often even in very trivial assignments:

nums = [1, 2, 3, 4]
# first, rest = nums[0], nums[1:]  # the hard way
first, *rest = nums  # the Python way :)

See? No need to wonder which index goes where.

SELF-PRACTICE

If you'd like to practice on your own a little, I've got a task for you. You've got some raw data here:

raw_data = [
    (10, 100, 349, 304, 203, 402, 798, 356),
    (465, 1254, 124, 875),
    (312, 46, 25, 96, 564, 183),
    (828, 4723, 7472, 588, 127, 872, 743, 400)
]

Using starred expressions, first print the sum of the first values from each tuple in a raw_data list. Then, do the same with all values between the first and the last in each tuple.

Now, you're fully ~~starred~~ prepped to use starred expressions! Hope you enjoyed my post! Please don't forget to leave a like if you did :)

If you still feel like learning some more Python tips, check out my post about elegant exception handling.

Python tips: unpack data gracefully

Vitaly Shchurov — Sat, 05 Dec 2020 01:06:34 +0000

Do you know how to easily assign data to variables from lists of various sizes? How to get a 'head' and 'tail' from a tuple without using clumsy indexes? How to use star expressions? Or simplify your code with a throaway variable? If not, get comfy :)

As you may know, we can assign values from sequences or iterables to variables. In short, a sequence is an ordered collection of items that supports accessing elements by indexing (some_list[0]). An iterable is an object that we can loop over (e.g., set is an iterable: for num in {1, 2, 3}: print(num)).

This assignment process is pretty easy, let's try assigning a list of values concerning some company's CEO:

name, experience, job = ['John Doe', 30, 'CEO']
name, experience, job
('John Doe', 30, 'CEO')

Why not try a tuple?

name, experience, job = ('John Doe', 30, 'CEO')
name, experience, job
('John Doe', 30, 'CEO')

Or a string:

a, b, c, = '123'
a, b, c
('1', '2', '3')

Since the object returned by a range() function produces a sequence, we can easily assign its contents to a bunch of variables:

d, e, f = range(3) 
d, e, f
(0, 1, 2)

If you're not very experienced with this, you may want to try playing with other iterable data structures (say dictionaries, sets).

So, what if you need to process data structures with arbitrary amounts of data? For example, you're expecting a server response with a tuple containing the information you need, but you may get more items than you expected, what then? Trying to unpack the same way will fail:

>>> name, experience, job = ('John Doe', 30, 'CEO', (2012, 1, 24))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: too many values to unpack (expected 3)

Adjusting your code to any possible mismatch wouldn't benefit your realtime application and can easily result in some ugly code. This is where starred expressions come into play. They're called so because you use a * sign before a variable name like that: *var.

Let's handle our last error:

>>> name, experience, job, *other = ('John Doe', 30, 'CEO', (2012, 1, 24), 100000)
>>> name, experience, job
('John Doe', 30, 'CEO')
>>> other
[(2012, 1, 24), 100000]

Here, we assigned all unnecessary information to a special variable. Python takes all remaining values and stores them in a list (always in a list).

In case you don't need all this other data at all, you can make your code even cleaner and use a special throwaway variable _:

>>> name, experience, job, *_ = ('John Doe', 30, 'CEO', (2012, 1, 24), 100000)

The data will still be assigned to it, but other developers will understand that this information won't be used or processed. By the way, you don't have to use it with starred expressions, it can be just _: a, _, b, _ = [1, 2, 3, 4].

You're welcome to use a starred expression in absolutely any part of your assignment:

>>> first, *middle, last = [1, 2, 3, 4]
>>> first
1
>>> middle
[2, 3]
>>> last
4

Or like that:

>>> *first, middle, last = 1, 2, 3, 4
>>> first
[1, 2]
>>> middle
3
>>> last
4

Have you noticed that we assigned variables to 1, 2, 3, 4? It's not a sequence, why didn't Python trow an exception? This is because we type 1, 2, 3, 4, but Python sees it as a tuple. In the examples at the beginning you may have seen that the interpreter always printed tuples as a result.

Another wonderful thing about star expressions is that they handle the situations where there're no extra values to be stored in them. See how we get an empty list in our John Doe example.

>>> name, experience, job, *other = ('John Doe', 30, 'CEO')
>>> name, experience, job
('John Doe', 30, 'CEO')
>>> other
[]

Now, let's try something more spicy :) Don't forget that we can unpack both sequences and iterables with starred expressions. So, let's unpack an iterator, it should be fun:

>>> seq = range(10)
>>> it = iter(seq)
>>> first, *rest = list(it)
>>> first, rest  # notice that the result is printed as a tuple:
(0, [1, 2, 3, 4, 5, 6, 7, 8, 9])

Can we get even more creative and use a couple of starred expressions in our assignment?

Actually, no. When you use a starred expression, you basically tell Python to assign certain values to certain variables, and store the rest of the data in a special starred variable.

So, if you use more than one *var during a single assignment, Python just won't know what to do. So, for one line of code, use only one star. Otherwise, you'll get an exception.

Bonus. Guess, can we use a starred expression alone? I'll publish the answer in the comments in case you'd like to guess it yourself ;)

So, this is how unpacking with starred expressions works in Python. If you'd like to see more practical examples, read my follow-up post.

Feeling curious to read some other tips? Check out my previous Python tips post about elegant exception handling.

Python tips: elegant exception handling with contextlib.suppress

Vitaly Shchurov — Wed, 02 Dec 2020 07:09:31 +0000

Python has a very elegant and concise way of handling exceptions, to my taste. What's more exciting is that it also has other techniques to make your code even more readable. Today, I'm going to share a small tip on using a context manager for handling 'lazy exceptions.'

Imagine that you need to handle a couple of possible errors and tell your program to ignore them. You can do it ‘the long way’ using the good old try except syntax:

try:
    do_a()
    try:
        do_b()
    except ExceptionB:
        pass
except ExceptionA:
    pass

Looks rather incomprehensible and ugly, not to mention the case when you've got several such exceptions to handle. Following the Python principles 'Flat is better than nested' nad 'Simple is better than complex', we can break it down:

try:
    do_a()
except ExceptionA:
    pass

try:
    do_b()
except ExceptionB:
    pass

A bit easier to read, but still, quite long for a simple 'try to do a() and b(), and if you fail, just keep going'. Here's where the contextlib module from the Python standard library comes to our rescue. contextlib provides utilities for common tasks involving the with statement, and, in our case, can help our code to achieve better clarity:

from contextlib import suppress
with suppress(ExceptionA):
    do_a()
    with suppress(ExceptionB):
        do_b()

A bit abstract, though. Python documentation gives us a more practical example. Say, we want to remove a file in case it still exists on our system. If we do it the usual way, we’ll type:

try:
    os.remove('somefile.tmp')
except FileNotFoundError:
    pass

With suppressing, it’ll be like:

from contextlib import suppress

with suppress(FileNotFoundError):  # if you get this exception
    os.remove('somefile.tmp')  # while trying to do this, go on

Two lines instead of four (well, not counting the import line). Not bad, especially if you have several such exceptions to handle.

There's a limitation to using this method, though. Use it only with specific exceptions to cover those errors where you know it's okay to keep going (pass). If you need to give specific instructions what to do if something goes wrong, than the traiditional try except will fit you better.

Hope you enjoyed my post! If you did, don't forget to like it. Thank you :)

Python Asyncio: Basic Fundamentals

Vitaly Shchurov — Tue, 01 Dec 2020 23:08:33 +0000

Asynchronous programming in Python doesn't seem to be a very easy subject, and it might be confusing when you first have to face it. In fact, it's a very practical tool, which is why it's really worth spending some effort to learn it.

This article will introduce you to the very fundamentals, another one, for more advanced stuff, will be coming out soon. Here, I will mainly focus on a high-level and easy way to use asyncio along with explaining what's so good about it, and when and why you should choose asyncio over threading.

Hope you enjoyed my article! If you find it helpful, I'll be grateful for your like :)

INTRO TO CONCURRENCY

Let's give a quick overview of what we need to understand. First, asyncio is a part of a broader concept called concurrency. Concurrent programming allows us to speed up our program by compelling our computer to do a few things at the same or seemingly at the same time instead of executing tasks one by one. There are three main types of concurrency: multiprocessing, (multi)threading and asynchronous programming.

When we want our machine to perform some intensive computations that we are too ~~lazy~~ busy to do ourselves, we’d better use multiprocessing (also called parallelism). In these cases, all the CPU cores our brand-new (or not very much so) computer has work at the same time to finish up some enormous task x times faster. This is the case of a true concurrency - when a computer can handle tasks at the same time better than Julius Caeser himself ever could (if only he'd had a laptop! Well, he had slaves instead :).

At times, our slave… machine doesn't work hard enough. A program that communicates with network requests or processes files on the hard drive spends most of its time waiting for responses. So, typically the process would look like:

# send a request
# wait
# get a response
# process it

# do the same again and again

This waiting around can take up most of the programme's time, so it actually rests more than it works. That won't do!

In such an event, we can achieve faster performance by starting a few such processes seemingly at the same time. While one process is ~~doing nothing~~ waiting, another one can, say, send a request, and lean back allowing the next one to do a similar job. When a server response reaches us, the first process (thread/task) gets CPU’s attention again and finishes its job, and so on. So, we don't really run things at the same time, but we just make sure that our CPU always has things to do while some threads are put on hold.

The best explanation of this strikingly beautiful and simple idea I've ever encountered is this: imagine a genius chess grandmaster who decides to put on a little show and play with, say, 20 other people. The grandmaster gets 10 seconds to plan his move, while all the other players get two minutes. If the grandmaster 'finishes off' his competitors one by one, it'll be hours before he's done.

To save himself some time, he can play with all of them (almost) at the same time by proceeding from one board to another with each his move. This way the game will be finished many times faster just because our grandmaster (CPU) will be busy working on other boards (tasks) while his opponents are contemplating their moves. So, this is what threading and asyncio do.

For now, we've established that concurrency can speed up your code's performance by using three basic ways: multiprocessing, threading and asynchronous programming. Use multiprocessing for heavy computing (CPU-bound tasks) and threading/asyncio when there's a lot of waiting around (I/O-bound tasks: web requests, working with files, etc.).

ASYNCIO AND THREADING: DIFFERENCE

Essentially, asyncio and threading are different in the way threads (tasks for asyncio) take turns.*

In threading, you don't get to control when one thread passes control to another, it can even happen in the middle of an operation like x += 1. What's more, this interruption can occur in different places each time you run your code, it's decided by your operating system.

Also, because threads operate on shared data, they can really mess up with it (so-called race conditions). So, it's considered good practice to protect against such situations by using locks, or better yet, libraries that implement them. Unfortunately, this doesn't go without some extra overhead.

In asyncio, we mark an exact place where our code gives up control using a keyword await. So, the code gives a signal that it's ready to be added to the waiting list and, meanwhile, CPU can shift to other tasks.

By default, asyncio runs a bunch of tasks in one thread, which basically removes the problem of race conditions and using locks (with all their overheads), but still saves a lot of time by cutting away the waiting time.

This explanation might present asyncio in a much better light, but it doesn't mean that you should always opt for it (more about it in a minute).

ASYNCIO vs. THREADING

STRENGTHS OF ASYNCIO

• asyncio is safer. You know exactly the points where your code will switch to the next task, which makes race conditions much harder to come by. Moreover, it makes debugging way easier comparing to threading.

• asyncio is lighter. Threads are managed by the operating system and, therefore, require more memory. asyncio almost always operates in one thread where it runs multiple tasks, which 'unburdens' it from the 'notorious' GIL makes it much lighter.

• asyncio is better for networking. Threads consume more memory since each thread has its own stack. With async code, all the code shares the same stack and it's kept small, which makes asyncio capable of supporting many thousands of simultaneous socket connections, so it's better suited for web-development.

DRAWBACKS OF ASYNCIO*

• threading is better for working with the filesystem. Operating systems usually don't support asynchronous operations with files, so for working with files, you'll need threading. There's a third-party library, though, aiofiles, which provides an async-compatible API for file operations, but, in fact, it's just delegating all the work to background threads under the hood (StackOverflow). So, if no networking is involved, it's better to stick to threading.

• many Python libraries are not asyncio-friendly. This means you cannot really use these libraries with asyncio or have to implement a special mechanism to avoid that (which comes with overhead). For example, the popular requests library doesn't support asyncio. So, you either need to use threading or choose another library (e.g., aiohttp works beautifully with asyncio).

• asyncio doesn't always makes your code faster. So, be careful to choose asyncio where it can serve its purpose best (for example, as said, don't choose it for working with files). If speed is what you are after, you might want to consider using Cython.

• since asyncio is single-threaded, it's not 'burdened' with the GIL like threading, but it cannot really benefit from multiprocessing either.

• although, asyncio removes most hard-to-trace race conditions which occur when we use threading, there are some other possible problems. Like, how will you communicate with a database that may allow only a few connections? How will your program terminate connections gracefully when you receive a signal to shut down? How will you handle blocking disk access and logging? etc.

DRAWBACKS OF THREADING:**

This is an article about asyncio, I know, but let's quickly review some of the threading's flaws as well so you'd be more comfortable when choosing between these two tools:

• threading bugs and race conditions in threaded programs can be really be hard to debug. On one run, your program is doing just fine, the next time the output is completely wrong, and there's sometimes no reliable way to find out what exactly the problem is.

• threads are resource-intensive. Threads require extra operating system resources to create (or even preallocate on 32-bit systems) per-thread stack space that consumes process virtual memory. To get around this problem on 32-bit systems, it's sometimes necessary to decrease the stack size with threading.stack_size(). Although, it can impact the degree to which function calls may be nested, including recursion. Single-threaded coroutines don't have this problem.

• At very high concurrency levels (say, more than 5,000 threads), there can also be a speed impact due to context-switching costs.

• Threading is an inefficient model for large-scale concurrency. The operating system will continually share CPU time with all threads regardless of whether a thread is ready to do work or not. For instance, a thread may be waiting for data on a socket, but the operating system may still switch to and from that thread thousands of times before any actual work needs to be done. (In the async world, the select() system call is used to check whether a socket-awaiting coroutine needs a turn; if not, that coroutine isn’t even woken up, avoiding any switching costs completely).

To sum this up, "use async IO when you can; use threading when you must."(source)

BASIC ASYNCIO SYNTAX

The simplest way to do async programming is by using the async/await syntax introduced in Python 3.5. Since Python 3.5, this syntax has become a native feature of the language, which is why asynchronous functions are now called native coroutines.

Before that, using asyncio was syntactically different. I'll focus only on the new syntax, and you should always use it unless you have to work with some pre-Python 3.5 version, in which case you might want to read about the old way here or here.

Async programming is based on using coroutines. Couroutine (or an asynchronous function) is a function that can suspend its execution before reaching return, and it can then pass control to another coroutine for some time. So, in a sense, coroutine is a specialized version of Python generators, but not quite.

The main difference lies with the fact that a coroutine suspends itself before returning (yielding) the result, and only temporarily. It gives up control to another coroutine, and then resumes itself.

A function prefixed with async def automatically becomes a coroutine.

async def coroutine():
    print("This is an asynchronous function.")

As I've mentioned, the central focus of asyncio is on how to best perform tasks that involve waiting periods. So, to tell the code to wait for something, we use the keyword await inside and only inside a coroutine (else it’s a syntax error):

import asyncio

async def main():
    print("Hello, ", end="")
    await asyncio.sleep(1)
    print("world!")

Here, we tell our code to stop and wait for a second. Because time module is not async compatible, we have imported the asyncio module from the standard library. Besides the basic native async syntax, you'll mostly be interacting with this module.

Seems like we are good to go, but if you try to execute the main() function, nothing will happen (or you'll get a runtime warning).

RUNNING ASYNC CODE (EVENT LOOP)

Why is that? It occurs because async functions need to be explicitly run on the thing called an event loop. For the time being, I'll just tell you the essential information about it without diving too deep.

In computer science, the event loop is a programming construct that waits for events (triggers) and then performs specific (programmed) actions.

You've actually had a lot of experience with them even if you don't know about it. Every time you use a computer, you interact with event loops. An event can be your laptop listening for user input, browsing, etc.

Event loops schedule and run asynchronous tasks in Python (basically, manage them for you to make your life a bit easier).

For now, to run the loop, we'll be using the asyncio.run() method, because it does all the heavy lifting for you, and you'll probably use it most of the time anyway. But bear in mind that an event loop could be created and fine-tuned using more lower-level API. What's more, you can use other implementations. For example, if fast performance is crucial for your application, uvloop offers a faster event loop than asyncio.

When executed, asyncio.run() will block the execution of a programme until the passed-in coroutine finishes:

import asyncio

async def main():
    print("Hello, ", end="")
    await asyncio.sleep(1)
    print("world!")

asyncio.run(main())

You'll get 'Hello, ', and then 'world!' in a second. So, here we created a ~~useless~~ simple task, and ran it. And what fun that was :) Now you have a taste of the syntax.

RUNNING MULTIPLE TASKS

Now, let's see how to work with a bunch of tasks, which is the whole point of asyncio). To schedule a few tasks, we need to use asyncio.gather(). By the way, asyncio.sleep() is used to imitate waiting for a web response:

import asyncio

async def task(num: int):
    print(f"Task {num}: request sent")
    await asyncio.sleep(1)
    print(f"Task {num}: response arrived")

async def main():
    await asyncio.gather(*[task(x) for x in range(1,4)])

if __name__ == '__main__':
    asyncio.run(main())

This was a primitive imitation of interaction with a server, and after the execution we'll get:

Task 1: request sent
Task 2: request sent
Task 3: request sent
Task 1: response arrived
Task 2: response arrived
Task 3: response arrived

See, how each task (coroutine) starts up, then sleeps and cedes control to another? Then, when the sleeping is over, it wakes up and keeps going. This is exactly what asyncio does. It runs your coroutines, then stops exactly where it is expected (that is, when something needs to be awaited), meanwhile remembering the state of a function, and executes the next task.

The question is, can we await anything we'd like? Actually, no. You can only await an awaitable object. What is that? It's an object that implements an __await__() method. Most of the times (not always), an awaitable object will be a function that is defined using async def (that is, a coroutine).

Hence, the problem of async-incompatible libraries mentioned above. The libraries that saw daylight before asyncio weren't designed to work with asynchronous code, and adjusting them requires a lot of work. For that reason, they cannot be properly used (there is a workaround, though, but it comes at a cost of doing lower-level programming and practically involving threading/multiprocessing at some point).

With that being said, never use the requests library with asyncio, because they're incompatible. Work with aiohttp instead, it's designed for working with asyncio. Likewise, the time module should never be used with asyncio. In fact, asyncio comes with its own asyncio.sleep() method, which will serve you just fine.

PRACTICAL CHALLENGE

Now, let's get our hands dirty! Since we already mentioned aiohttp, I suggest we use it to solve a more or less practical challenge. First, using an aiohttp session, we'll download a web page:

import asyncio
import aiohttp

async def fetch(url: str):
    async with aiohttp.ClientSession() as session:
        response = await session.get(url)
        print(await response.text())

if __name__ == '__main__':
    asyncio.run(fetch("https://python.org/"))

Notice how we created an asynchronous context manager within our async function, it's pretty basic, as you can see. Nice, let's take it further and fetch a bunch of web pages from asyncio documentation and measure their lengths:

import aiohttp
import asyncio

async def fetch_and_measure(url: str):
    async with aiohttp.ClientSession() as session:
        response = await session.get(url)
        html = await response.text()
        return len(html)

async def main(urls: list):
    result = await asyncio.gather(*[fetch_and_measure(url) for url in urls])
    return result

if __name__ == '__main__':
    urls = [
        "https://docs.python.org/3/library/asyncio.html",
        "https://docs.python.org/3/library/asyncio-task.html",
        "https://docs.python.org/3/library/asyncio-stream.html",
        "https://docs.python.org/3/library/asyncio-sync.html",
        "https://docs.python.org/3/library/asyncio-subprocess.html",
    ]
    result = asyncio.run(main(urls))
    print(result)

Notice that we have gathered tasks in a main() coroutine function. This is often considered to be a good practice.

CHAINING COROUTINES

In the example above, we could create a separate function to evaluate the length of a web page. So, can we chain coroutines together? Yes, we can. In real life, such function would do more complicated things (parsing, for example or whatever you'd like to do with your downloaded web pages), and it'd be good to keep them separated from fetching. Chaining asynchronous functions is very easy in Python, let's rework our example a little bit:

import aiohttp
import asyncio

async def measure(html: str) -> int:
    return len(html)

async def fetch(url: str):
    async with aiohttp.ClientSession() as session:
        response = await session.get(url)
        html = await response.text()
        length = await measure(html)
        return length

async def main(urls: list):
    result = await asyncio.gather(*[fetch(url) for url in urls])
    return result

if __name__ == '__main__':
    urls = [
        "https://docs.python.org/3/library/asyncio.html",
        "https://docs.python.org/3/library/asyncio-task.html",
        "https://docs.python.org/3/library/asyncio-stream.html",
        "https://docs.python.org/3/library/asyncio-sync.html",
        "https://docs.python.org/3/library/asyncio-subprocess.html",
    ]
    result = asyncio.run(main(urls))
    print(result)

Note how you create a measure() coroutine, but you don't await anything inside it, because you can await only awaitable objects. But the measure() itself is such an object - it's a coroutine! Which is why you await this coroutine when you call it from inside the fetch().

CONCLUSION

Now, you've learned what asyncio is, what it's place in Python concurrency, what advantages and flaws it has comparing to threading, and how to create coroutines and run them on an event loop based on a high-level asyncio API.

That's enough for the first encounter, but remember, asyncio is much more than that! It now supports a wide range of interactions with native Python features: there are asynchronous iterators, generators, context managers, loops, and even comprehensions! We've actually already used an async context manager.

There is a special asyncio.Queue() for working with producer-consumer tasks, and a lot of other tools and implementations (such as fast performance event loop uvloop). I hope to introduce your to more asyncio theory and practice as soon as my next article about it is ready.

There's one more thing you need to remember. Asyncio API includes interface both for end-users and framework developers. There're methods which should be used primarily by one of those users. If you develop your application, be careful to avoid tools that are meant to be used by framework developers and fine-tuning (unless you know what you're doing and really need them).

* 'Using Asyncio in Python 3' by Caleb Hattingh, p. 7-8.
** 'Using Asyncio in Python 3' by Caleb Hattingh, p. 11-13.

Forem: Vitaly Shchurov

Python: using heapq module to find n largest items

RELATIVELY SMALL N

RELATIVELY LARGE N

heapq: MORE ADVANCED EXAMPLES

LARGEST CITIES

HIGHEST-PAID EMPLOYEES

CHALLENGE

heapq: UNDERLYING MECHANISM

Python tips: playing with round()

Python guide to using generators more

A QUICK REMINDER

WHY DESIGN A FUNCTION AS A GENERATOR?

PRACTICAL EXAMPLE

Python: how to 'reuse' a generator?

SOLUTION I: COPYING THE RESULTS

SOLUTION II: USING LAMBDA

SOLUTION III: USING A CONTAINER CLASS

SPEED PERFORMANCE

Python: avoid large list comprehensions

CONCLUSION

Python: deque vs. list

WHAT IS A DEQUE?

DEQUE vs. LIST

PROBLEM SOLVING

TRACING LAST TRANSACTIONS

FIND A TEXT PATTERN WITH SOME PREVIOUS CONTEXT

RETURN N LAST LINES OF A FILE

SUMMARY

Python starred expressions: practical challenges

RUNNING AN ONLINE SHOP

SENDING A HOLIDAY CARD

DOING BUSINESS RESEARCH

DAILY STUFF

SELF-PRACTICE

Python tips: unpack data gracefully

Python tips: elegant exception handling with contextlib.suppress

Python Asyncio: Basic Fundamentals

INTRO TO CONCURRENCY

ASYNCIO AND THREADING: DIFFERENCE

ASYNCIO vs. THREADING

STRENGTHS OF ASYNCIO

DRAWBACKS OF ASYNCIO*

DRAWBACKS OF THREADING:**

BASIC ASYNCIO SYNTAX

RUNNING ASYNC CODE (EVENT LOOP)

RUNNING MULTIPLE TASKS

PRACTICAL CHALLENGE

CHAINING COROUTINES

CONCLUSION

`heapq`: MORE ADVANCED EXAMPLES

`heapq`: UNDERLYING MECHANISM