Imagine clearing snow with a friend. With one shovel, taking turns adds waiting. If one person shovels while the other spreads salt, you have split the job by function. With two shovels, you could instead divide the area into zones and clear them independently. Decomposition looks for work that can proceed without waiting for other work. section 7.2 section 7.4
There are two main approaches. Task decomposition separates different functions, such as searching for emails and displaying them. Data decomposition divides a collection into chunks and applies the same operation to each chunk, such as checking separate groups of possible passwords. A dependency graph can help reveal which tasks are truly independent before execution details are considered. section 7.1 section 7.2 section 7.4
Turn a file-search loop into separate tasks
A sequential search checks files one after another for a word. Because checking one file does not require the result from another, each file can become a separate task. A Python ThreadPool can run those checks concurrently and collect the results. Reading files still involves I/O, so concurrent tasks are not guaranteed to process their data simultaneously. section 7.5
# Chapter 7/find_files/find_files_concurrent.py
import os
import time
import typing as T
from multiprocessing.pool import ThreadPool
def search_file(file_location: str, search_string: str) -> bool:
with open(file_location, "r", encoding="utf8") as file:
return search_string in file.read()
def search_files_concurrently(file_locations: T.List[str],
search_string: str) -> None:
with ThreadPool() as pool: #1
results = pool.starmap(search_file, #1
((file_location, search_string) for #1
file_location in file_locations)) #1
for result, file_name in zip(results, file_locations):
if result:
print(f"Found string in file: `{file_name}`")
if __name__ == "__main__":
file_locations = list(
glob.glob(f"{os.path.abspath(os.getcwd())}/books/*.txt"))
search_string = input("What word are you trying to find?: ")
start_time = time.perf_counter()
search_files_concurrently(file_locations, search_string)
process_time = time.perf_counter() - start_time
print(f"PROCESS TIME: {process_time}")
The Python listing uses ThreadPool.starmap to apply the same search function to different files, then pairs results with filenames. section 7.5
Choose chunk size with care. Too few large tasks can leave processing resources idle or give one worker most of the work. Many small tasks offer scheduling flexibility but increase coordination overhead. Aim for at least as many tasks as available processing resources, preferably more; then weigh that flexibility against overhead. Decomposition does not help when an algorithm offers no independent work. section 7.9 section 13.4
