Linear Search in R [single-thread + multi-thread]

R is an open-source programming language for statistical computing and graphics. It is widely used for Data Science.

If you are confused how to implement Linear Search in R, this article at OpenGenus will help you. We have provided both single-threaded and multi-threaded implementation in R for Linear Search.

Table of contents:

1. Approach
2. R implementation for Single-threaded Linear Search
3. R implementation for Multi-threaded Linear Search
4. Run the code

Approach

For Linear Search in R, we define a data array as:

data <- c(2, 5, 7, 1, 9, 3, 6, 8)

and loop through it as:

for (i in seq_along(data)) {
   # ...
}

In the process of looping through each element, compare each element with target element for Linear Search.

Approach for Multi-thread Linear Search

• Import the library future.apply
• Split data into smaller chunks

data_chunks <- future.apply::future_chunk(as.list(data), num_threads)

• Create each thread for each chunk and apply Linear Search for that chunk of data

futures <- future.apply::future_lapply(data_chunks, linear_search_worker, search_key=search_key)

• Execute all the threads

results <- future.apply::future_get(futures)

• Get the data for each thread and compute the final result accordingly

for (i in seq_along(results)) {
    if (results[[i]] != -1) {
      return((i - 1) * length(data_chunks[[1]]) + results[[i]])
    }
}

R implementation for Single-threaded Linear Search

Following is the single-threaded program in R for Linear Search:

# Define a function to perform linear search on a vector of integers.
linear_search <- function(data, search_key) {
  # Loop through the vector and compare each element to the search key.
  for (i in seq_along(data)) {
    if (data[i] == search_key) {
      # If the search key is found, return its index.
      return(i)
    }
  }
  
  # If the search key is not found, return -1.
  return(-1)
}

# Define some sample data and a search key.
data <- c(2, 5, 7, 1, 9, 3, 6, 8)
search_key <- 3

# Call the linear search function with the sample data and search key.
result <- linear_search(data, search_key)

# Print the result of the linear search.
if (result == -1) {
  cat("Element", search_key, "not found\n")
} else {
  cat("Found element", search_key, "at index", result, "\n")
}

R implementation for Multi-threaded Linear Search

Following is the multi-threaded program in R for Linear Search:

library(future.apply)

# Define a function to perform linear search on a subset of data.
linear_search_worker <- function(data, search_key) {
  # Loop through the subset of data and compare each element to the search key.
  for (i in seq_along(data)) {
    if (data[i] == search_key) {
      # If the search key is found, return its index.
      return(i)
    }
  }
  
  # If the search key is not found, return -1.
  return(-1)
}

# Define a function to perform linear search with multiple threads.
linear_search_parallel <- function(data, search_key, num_threads) {
  # Split the data into equal-sized chunks for each thread.
  data_chunks <- future.apply::future_chunk(as.list(data), num_threads)

  # Create a list of futures for each thread to perform linear search on each data chunk.
  futures <- future.apply::future_lapply(data_chunks, linear_search_worker, search_key=search_key)
  
  # Wait for all futures to complete and get their results.
  results <- future.apply::future_get(futures)
  
  # Loop through the results and return the index of the search key if found.
  for (i in seq_along(results)) {
    if (results[[i]] != -1) {
      return((i - 1) * length(data_chunks[[1]]) + results[[i]])
    }
  }
  
  # If the search key is not found, return -1.
  return(-1)
}

# Define some sample data and a search key.
data <- c(2, 5, 7, 1, 9, 3, 6, 8)
search_key <- 1
num_threads <- 2

# Call the linear search function with multiple threads using the sample data and search key.
result <- linear_search_parallel(data, search_key, num_threads)

# Print the result of the linear search.
if (result == -1) {
  cat("Element", search_key, "not found\n")
} else {
  cat("Found element", search_key, "at index", result, "\n")
}

Run the code

Save the code in a file named as "linearSearch.R" and use the following command to run it from R console:

source("linearSearch.R")

If you are using an IDE like RStudio, you can load and run the code using "Source" button.

The output will be as follows:

Found element 1 at index 3

With this article at OpenGenus, you must have the complete idea of how to implement Linear Search in R Programming Language using both single and multi-threads.