Соответствующий код работает в O (n2). Можете ли вы предложить альтернативный код, который работает ближе к O (n)?

Question

У меня есть большие фреймы данных со столбцом (символом) названий видов, называемым hit.match. hit.match может содержать одно название вида или более 20 названий видов, разделенных символом «|». Я хочу, чтобы быстрый код проверял совпадения с одним видом в hit.match. Мой текущий код масштабируется как O (n2) (n-квадрат), где n - количество входных записей. Мне нужно, чтобы он масштабировался быстрее, ближе к O (n).

##Function matched looks in hit.match in the input df, and returns one of the prioritized species in the input species list match.list that match hit.match in a priority order. If none of the prioritized species is found, it returns the original hit.match
#Input is a df and a list of species scientific names (genus species) locally called match.list
#Output is a df with hit.match replaced with the prioritized species name or retaining the original hit.match

 matched <- function(df, match.list) {
# Iterate through match.list
for(i in seq_len(length(match.list))) {
match <-grep(match.list[[i]],df$hit.match)
for(j in seq_len(length(match))) {
    df$hit.match[[ match[j] ]] <- match.list[[i]]
    } #end For j
} #end for i
df
}

df$hit.match = cbind("Nomina nudum", " Nomina nudum1 | Nomina nudum2", " Nomina nudum | Nomina nudum1 | Nomina nudum2", " Nomina nudum1", " Nomina nudum2")

match.list = c("Nomina nudum", " Nomina nudum1 ", " Nomina nudum2")

matched(df, match.list)

вывод должен быть («Nomina nudum», «Nomina nudum1», «Nomina nudum», «Nomina nudum1», «Nomina nudum2»") Функция работает нормально, но слишком медленно.

Answer 1

Мы можем разбить строку на "|", создать шаблон, вставив match.list вместе. Если шаблон соответствует любому элементу в hit.match, мы возвращаем первое совпадение или возвращаем hit.match снова.

pat <- paste0(match.list, collapse = "|")

sapply(strsplit(df$hit.match, "\\|"), function(x) {
     inds <- grep(pat, x)
     if (length(inds) > 0)   trimws(x[inds[1L]]) 
     else paste0(x, collapse = "|")
})
#[1] "Nomina nudum"  "Nomina nudum1" "Nomina nudum"  "Nomina nudum1" "Nomina nudum2"

data

df <- data.frame(hit.match = c("Nomina nudum", " Nomina nudum1 | Nomina nudum2", 
    " Nomina nudum | Nomina nudum1 | Nomina nudum2", " Nomina nudum1", 
    " Nomina nudum2"), stringsAsFactors = FALSE)

match.list <- c("Nomina nudum", " Nomina nudum1 ", " Nomina nudum2")