Multi-threaded Python Program for Linear Search

Are you looking for an efficient way to search an element in Python?

The most common approach is to do Linear Search and when used in a multi-threaded fashion, it utilizes 100% of the CPU Core. In this article at OpenGenus, we demonstrate this by implementing Multi-threaded Linear Search in Python Programming.

In short, we divide the array into smaller chunks and then, each thread runs a separate chunk concurrently.

Table of contents:

1. Linear Search using threads
2. Python Implementation for Multi-threaded Linear Search

Linear Search using threads

• Create a list of threads

threads = []

• We create new threads and assign each thread a new chunk defined by start and end indices.

t = threading.Thread(target=linear_search, args=(arr, x, start, end))

• We start and run the thread.

threads.append(t)
t.start()

• interrupt_main() is used to stop all threads when a particular thread finds the target element. This is an efficient way of terminating early. Other options would be to use a shared variable or a control variable/ flag which are not clean solutions.

threading.current_thread().interrupt_main()

• Beyond it, we use threading.current_thread().result to store the result of each thread.

threading.current_thread().result = i
// ...
// If element is not found
threading.current_thread().result = -1

• We wait for all threads to complete.

for t in threads:
    t.join()

Python Implementation for Multi-threaded Linear Search

Following is the complete Python program to do Linear Search in a multi-threaded way:

import threading

def parallel_linear_search(arr, x, num_threads):
    n = len(arr)
    chunk_size = n // num_threads

    threads = []

    # Create threads and search through different chunks of the array
    for i in range(num_threads):
        start = i * chunk_size
        end = n if i == num_threads - 1 else (i + 1) * chunk_size

        t = threading.Thread(target=linear_search, args=(arr, x, start, end))
        threads.append(t)
        t.start()

    # Wait for all threads to finish and return the first index found
    for t in threads:
        t.join()

        if t.result != -1:
            return t.result

    # Element not found
    return -1

def linear_search(arr, x, start, end):
    for i in range(start, end):
        if arr[i] == x:
            threading.current_thread().result = i
            threading.current_thread().interrupt_main()

    # Element not found in this chunk
    threading.current_thread().result = -1

if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    x = 7
    num_threads = 4

    idx = parallel_linear_search(arr, x, num_threads)

    if idx != -1:
        print(f"Element found at index {idx}")
    else:
        print("Element not found")

Save the above code in a file named LinearSearch.py and run it using the following command:

python LinearSearch.py

The output will be as follows:

Element found at index 6

With this article at OpenGenus, you must have the complete idea of how to implement Linear Search in a multi-threaded way in Python Programming Language.