
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:
- Linear Search using threads
- 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.