Efficient way to get location of match between vectors

r

Solution

Here's a relatively faster way using `data.table`:

require(data.table)
vv <- vapply(y, length, 0L)
DT <- data.table(y = unlist(y), id = rep(seq_along(y), vv), pos = sequence(vv))
setkey(DT, y)
# OLD CODE which will not take care of no-match entries (commented)
# DT[J(c("chocolate", "good")), list(list(pos)), by=id]$V1

setkey(DT[J(c("chocolate", "good"))], id)[J(seq_along(vv)), list(list(pos))]$V1

The idea:

First we unlist your list into a column of `DT` named `y`. In addition, we create two other columns named `id` and `pos`. `id` tells the index in the list and `pos` tells the position within that `id`. Then, by creating a key column on `id`, we can do fast subsetting. With this subsetting we'll get corresponding `pos` values for each `id`. Before we collect all `pos` for each `id` in a list and then just output the list column (V1), we take care of those entries where there was no match for our query by setting key to `id` after first subsetting and subsetting on all possible values of `id` (as this'll result in `NA` for non-existing entries.

Benchmarking with the `lapply` code on your post:

x <- list(c('I', 'like', 'chocolate', 'cake'), c('chocolate', 'cake', 'is', 'good'))
y <- rep(x, 5000)

require(data.table)
arun <- function() {
    vv <- vapply(y, length, 0L)
    DT <- data.table(y = unlist(y), id = rep(seq_along(y), vv), pos = sequence(vv))
    setkey(DT, y)
    setkey(DT[J(c("chocolate", "good"))], id)[J(seq_along(vv)), list(list(pos))]$V1
}

tyler <- function() {
    lapply(y, function(x) {
        which(x %in% c("chocolate", "good"))
    })
}

require(microbenchmark)
microbenchmark(a1 <- arun(), a2 <- tyler(), times=50)

Unit: milliseconds
          expr       min        lq    median        uq       max neval
  a1 <- arun()  30.71514  31.92836  33.19569  39.31539  88.56282    50
 a2 <- tyler() 626.67841 669.71151 726.78236 785.86444 955.55803    50

> identical(a1, a2)
# [1] TRUE

Problem

I am in need of efficiency for finding the indexes (not the logical vector) between two vectors. I can do this with: ``` which(c("a", "q", "f", "c", "z") %in% letters[1:10]) ``` In the same way it is better to find the position of the maximum number with `which.max`: ``` which(c(1:8, 10, 9) %in% max(c(1:8, 10, 9))) which.max(c(1:8, 10, 9)) ``` I am wondering if I have the most efficient way of finding the position of matching terms in the 2 vectors. EDIT: Per the questions/comments below. I am operating on a list of vectors. The problem involves operating on sentences that have been broken into a bag of words as seen below. The list may contain 10000-20000 or more character vectors. Then based on that index I will grab 4 words before and 4 words after the index and calculate a score. ``` x <- list(c('I', 'like', 'chocolate', 'cake'), c('chocolate', 'cake', 'is', 'good')) y <- rep(x, 5000) lapply(y, function(x) { which(x %in% c("chocolate", "good")) }) ```

Original source