Grep in for loop to detect names in 1 million iterations, too slow

Question

I have a list of 1 million names and i want to look them up in each cell of a column having 150k rows. i am using Grep to lookup the names one by one and if found in any cell, make the cell blank. i am running this loop 1 million times, but it will take a lot of time. How can i speed up the loop?

install.packages("babynames")
install.packages("randomNames")
names = babynames::babynames ###creating a random dataset for this example
temp_new2= data.frame(names$name) ##temp_new2 is a single column name dataframe

random_names<-strsplit((randomNames(n=1000,
                            which.names="first",
                            name.sep=" ",
                            sample.with.replacement=TRUE,
                            return.complete.data=FALSE
)
),"\n")
count = 0
t=0
list_of_names = list()

for (i in random_names)
    {
      if (length(grep(paste0("\\b",i,"\\b"),temp_new2$cleaned_names,ignore.case = TRUE)) != 0) 
      {
        p = length(grep(paste0("\\b",i,"\\b"),temp_new2$cleaned_names,ignore.case = TRUE))
        print(i)
        list_of_names = append(list_of_names,i)
      }
      else
      {t=0
       p=0
      }

      count = count + p
      temp_new2[grep(paste0("\\b",i,"\\b"),temp_new2$cleaned_names,ignore.case = TRUE),]<- ""

    }

it takes about 4 mins to run a loop of 1000 names, so it will take 4000 mins to run a loop of 1 million names

`list_of_names = list()` this is where you probably start. You are growing a list using the for-looop which makes your code slow. Initialize the list with an appropriate length. Please, try to provide a reproducible example for your problem. What is in random_names? How does temp_new2 look like? Use `dput` or `dput(head(your_data))` and see https://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example — kath, Jun 13 '19 at 10:28
list_of_names will contain the names out of the 1 million names that will be matched in the temp_new2 data column. so I cannot be sure of the number of elements of the list apriori. — karan wanchoo, Jun 13 '19 at 10:31
Please edit the question with additional information and do not put this into the comments. — kath, Jun 13 '19 at 10:38
possible (easy) join-question.. but post some sample data first...., see comments by @kath — Wimpel, Jun 13 '19 at 10:40
i also commented the list_of_names line, where i append the names matched into a list. it still takes the same amount of time. — karan wanchoo, Jun 13 '19 at 10:58
i cannot use a left join, because the real data in temp_new2 is a string of words and not single words. — karan wanchoo, Jun 13 '19 at 11:08
You run the very same `grep` 3 times in the loop!!! At least 2 of them will always execute. In my tests, with just one call, `grep` accounts for 99% of the total execution time. — Rui Barradas, Jun 13 '19 at 11:31

kath · Accepted Answer · 2019-06-13T12:28:55.357

I played around a little bit and got the following results with microbenchmark:

microbenchmark::microbenchmark(your_fun(), fun_initialize_list(), fun_list_one_grep(), fun_lapply())
Unit: milliseconds
                  expr      min       lq     mean   median       uq       max neval
            your_fun() 51.02420 52.61047 55.19147 54.20093 55.98069  77.55637   100
 fun_initialize_list() 50.86644 52.81099 55.52799 54.23134 56.37564 102.21945   100
   fun_list_one_grep() 25.68943 26.31398 28.51748 27.73832 28.46759  56.01566   100
          fun_lapply() 25.22339 26.02261 27.83738 27.26183 27.90310  43.80443   100

The functions are defined below and are simply a wrapper around the different procedures. As @RuiBarradas already pointed out, the grep call is execute 3 times. Reducing this, reduces the execution time by 50% in my case.

Your approach

your_fun <- function() {

  count <- 0
  t <- 0
  list_of_names <- list()

  for (i in random_names) {
    if (length(grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names,ignore.case = TRUE)) != 0) {
      p <- length(grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names,ignore.case = TRUE))
      list_of_names <- append(list_of_names,i)
    } else {
      t <- 0
      p <- 0
    }
    count <- count + p
    temp_new2[grep(paste0("\\b",i,"\\b"),temp_new2$cleaned_names,ignore.case = TRUE),] <- ""
  }

}

Initializing the list before the for-loop
You are right, that did not improve the speed tremendously, probably because grep takes so much time.

fun_initialize_list <- function() {
  count <- 0
  t <- 0
  list_of_names <- logical(length(random_names))
  k <- 0

  for (i in random_names) {
    k <- k + 1
    if (length(grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names,ignore.case = TRUE)) != 0) {
      p <- length(grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names,ignore.case = TRUE))
      list_of_names[k] <- TRUE
    } else {
      t <- 0
      p <- 0
      list_of_names[k] <- FALSE
    }
    count <- count + p
    temp_new2[grep(paste0("\\b",i,"\\b"),temp_new2$cleaned_names,ignore.case = TRUE),] <- ""
  }

  list_of_names <- random_names[list_of_names]
}

Using only one call for grep

fun_list_one_grep <- function() {
  count <- 0
  t <- 0
  list_of_names <- logical(length(random_names))
  k <- 0

  for (i in random_names) {
    k <- k + 1
    name_match <- grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names, ignore.case = TRUE)
    len_match <- length(name_match)
    if (len_match != 0) {
      p <- len_match
      list_of_names[k] <- TRUE
    } else {
      t <- 0
      p <- 0
      list_of_names[k] <- FALSE
    }
    count <- count + p
    temp_new2[name_match, ] <- ""
  }

  list_of_names <- random_names[list_of_names]
}

Approach with lapply

fun_lapply <- function() {
  random_matches <- lapply(random_names, function(i) {
    grep(paste0("\\b",i,"\\b"), temp_new2$cleaned_names, ignore.case = TRUE)
  })

  temp_new2[unlist(random_matches), ] <- ""
  count <- length(unique(unlist(random_matches)))

  list_of_names <- random_names[!sapply(random_matches, is.null)]
}

Data

names = babynames::babynames ###creating a random dataset for this example
temp_new2 = data.frame(cleaned_names = names$name[1:1000], 
                       stringsAsFactors = FALSE) ##temp_new2 is a single column name dataframe

set.seed(23)

random_names <- strsplit((
  randomNames::randomNames(
    n = 100,
    which.names = "first",
    name.sep = " ",
    sample.with.replacement = TRUE,
    return.complete.data = FALSE
  )), "\n")

And there's also `stringr::str_detect`, vectorized on both the string and the pattern. — Rui Barradas, Jun 13 '19 at 12:02

Grep in for loop to detect names in 1 million iterations, too slow

1 Answers1