Chapter 3. Identifying a Parallelizable Problem

The previous chapter presented some of the different ways in which we can think about a problem in terms of parallelism. Now we will analyze some specific problems that will be useful in guiding us throughout the implementation.

This chapter covers the following topics:

• Obtaining the highest Fibonacci value for multiple inputs

• Crawling the Web

Obtaining the highest Fibonacci value for multiple inputs

It is known that the Fibonacci sequence is defined as follows:

In practical terms, calculating the Fibonacci value for the terms 0 to 10, the result would be 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55.

An example of Python code to calculate Fibonacci returning the highest value using the iterative method is as follows:

def fibonacci(input):
    a, b = 0, 1
    foritem in range(input):
        a, b = b, a + b
    return a

The Fibonacci function calculates the highest Fibonacci value for a specific piece of input data. Let us picture a hypothetical scenario in which it is necessary to calculate Fibonacci values, and this website will receive several inputs from a user. Suppose the user provides an array of values as input, so making these calculations sequentially would be interesting. But, what if 1 million users are connected at the same time to make requests? In this case, some users would have to wait for quite a long time until they...

Crawling the Web

Another problem to be studied throughout this book is the implementation of a parallel Web crawler. A Web crawler consists of a computer program that browses the Web to search for information on pages. The scenario to be analyzed is a problem in which a sequential Web crawler is fed by a variable number of Uniform Resource Locators (URLs), and it has to search all the links within each URL provided. Imagining that the number of input URLs may be relatively large, we could plan a solution looking for parallelism in the following way:

1. Group all the input URLs in a data structure.

2. Associate data URLs with tasks that will execute the crawling by obtaining information from each URL.

3. Dispatch the tasks for execution in parallel workers.

4. The result from the previous stage must be passed to the next stage, which will improve raw collected data, thereby saving them and relating them to the original URLs.

As we can observe in the numbered steps for a proposed solution, there is a combination...

Summary

In this chapter, we learned about common problems and potential solutions involving parallelism. The problems presented will be shown using different parallel Python libraries for the implementation of solutions.

In the next chapter, we will focus on solutions involving threads while using the threading module, solutions involving the use of processes with the multiprocessing module, and so on.