Multi-threaded RUST Program for Linear Search

Rust is one of the most performant Programming Languages today and if you want to implement Linear Search efficiently in Rust, multi-threading is the answer.

In this article at OpenGenus, we have explained how to implement Linear Search in Rust Programming Language using threads along with the complete Rust code.

For the single-threaded version of Linear Search in Rust, go through this article.

Table of contents:

1. Multi-threaded Linear Search approach in Rust
2. Rust implementation for Linear Search using threads
3. Run the code

Multi-threaded Linear Search approach in Rust

• Start by importing the thread module in Rust

use std::thread;

Assuming there are 4 threads, we create 4 chunks of data:

let chunk_size = data.len() / 4;

• Create a new thread and assign a particular chunk to it to perform Linear Search.

let handle = thread::spawn(move || {
    for (j, &item) in data[start..end].iter().enumerate() {
        if item == search_key {
            return Some(start + j);
        }
    }
    None
});

• We wait for all threads to finish execution and return the result accordingly.

for handle in handles {
    if let Some(idx) = handle.join().unwrap() {
        result = Some(idx);
        break;
    }
}

We have added comment for each line in our Rust program to help you understand it completely.

Rust implementation for Linear Search using threads

Following is the complete implementation in Rust Programming Language for Linear Search using threads (to run it in a multi-threaded fashion):

// Import the 'thread' module from the Rust standard library.
use std::thread;

// Define a function to perform linear search on an array of integers.
fn linear_search(data: &[i32], search_key: i32) -> Option<usize> {
    // Initialize the result variable to None.
    let mut result = None;

    // Divide the data array into 4 equal chunks.
    let chunk_size = data.len() / 4;

    // Initialize a vector to hold the handles of all the spawned threads.
    let mut handles = Vec::new();

    // Spawn 4 threads, one for each chunk of the data array.
    for i in 0..4 {
        // Calculate the start and end indices for the current chunk.
        let start = i * chunk_size;
        let end = if i == 3 {
            data.len()
        } else {
            (i + 1) * chunk_size
        };

        // Spawn a new thread to search the current chunk for the search key.
        let handle = thread::spawn(move || {
            for (j, &item) in data[start..end].iter().enumerate() {
                if item == search_key {
                    return Some(start + j);
                }
            }
            None
        });

        // Store the handle of the spawned thread in the 'handles' vector.
        handles.push(handle);
    }

    // Wait for all threads to finish and check their results.
    for handle in handles {
        if let Some(idx) = handle.join().unwrap() {
            result = Some(idx);
            break;
        }
    }

    // Return the index of the found element or None.
    result
}

// Define the main function.
fn main() {
    // Define some sample data and a search key.
    let data = [2, 5, 7, 1, 9, 3, 6, 8];
    let search_key = 9;

    // Call the linear search function with the sample data and search key.
    let result = linear_search(&data, search_key);

    // Print the result of the linear search.
    match result {
        Some(idx) => println!("Found element {} at index {}", search_key, idx),
        None => println!("Element {} not found", search_key),
    }
}

Run the code

Save the above code in a file named "linearSearch.rs" and use the following command to compile the code:

rustc linearSearch.rs

Following it, use the following command to run the executable generated using the previous command:

./linearSearch

The output will be:

Found element 9 at index 4

With this article at OpenGenus, you must have the complete idea of how to implement Linear Search in Rust Programming Language using threads for 100% CPU utilization.