Finden Sie die längste Übereinstimmung von 2 ganzen Zahlen in R

Question

Ich habe 2 Listen mit Zahlen und ich muss die Werte einer Liste mit den anderen übereinstimmen. Die Übereinstimmung muss basierend auf dem Anfang der Nummer erfolgen. Es muss die row_id der längsten Übereinstimmung zurückgeben, die möglich ist.

lookup value: 12345678 

find_list: 
a 1 
b 12 
c 123 
d 124 
e 125 
f 1234 
g 1235 

In diesem Beispiel würden wir eine Übereinstimmung mit a,b,c,f und R muss f zurückkehren. Seit f ist die längste und daher die beste Übereinstimmung.

Ich habe jetzt die startsWith Funktion in R verwendet. Aus dieser Antwort wähle ich den Wert, der am längsten ist. Aber das Problem ist, dass die Listen riesig sind. Ich habe 18,5 Millionen Lookup-Werte und 300.000 mögliche Werte in der find_list und R stürzt nach einer Weile ab.

Gibt es einen klügeren Weg, dies zu tun? Hier

Answer 1

ist eine Methode, in der Basis R.

# construct a vector of all possible matches for the lookup value 
lookupVec <- floor(lookup * (10^(-1 * (0:(nchar(lookup)-1))))) 

Das gibt

lookupVec 
[1] 1234567 123456 12345 1234  123  12  1 

# find the value of the first variable that matches the maximum value 
# lower values in the vector 

dat$V1[which.min(match(dat$V2, lookupVec))] 
[1] f 
Levels: a b c d e f g 

Sie können dies wahrscheinlich beschleunigen durch Basis R ersetzt match Funktion mit der fastmatch Funktion aus dem Paket der gleichen Name, wie es die Tabellenwerte hashen wird, wenn Sie über diese ein zweites Mal suchen.

Daten

dat <- 
structure(list(V1 = structure(1:7, .Label = c("a", "b", "c", 
"d", "e", "f", "g"), class = "factor"), V2 = c(1L, 12L, 123L, 
124L, 125L, 1234L, 1235L)), .Names = c("V1", "V2"), class = "data.frame", 
row.names = c(NA, -7L)) 

lookup <- 12345678 

Answer 2

Vielleicht gibt es eine intelligentere Art und Weise zu tun, was Sie wollen, aber die folgende erzeugt das Ergebnis in der Frage.
Sie benötigen das Paket installiert.
Zuerst die Daten in der Frage.

lookup <- "12345678" 
find_list <- read.table(text = " 
a 1 
b 12 
c 123 
d 124 
e 125 
f 1234 
g 1235 
") 
find_list$V2 <- as.character(find_list$V2) 

Jetzt der Code.

inx <- which(stringi::stri_detect(lookup, regex = find_list$V2)) 
inx <- inx[which.max(nchar(find_list$V2[inx]))] 
find_list[inx, ] 
# V1 V2 
#6 f 1234 

Answer 3

Hier ist eine Option, falls Sie Ihren find_list in ein data.table umwandeln können:

y <- 123456789 

x <- data.table(sample(1:1000000, 1000000, replace = T)) # find list 
n <- round(log(y, base = 10)) + 1 # number of digits 
z <- floor(y/(10^(1:(n)))) # split up into all possible integers 

x[V1 == x[V1 %in% z, max(.SD),],, which = T] 

Dies gibt auch mehrreihige ids falls es Duplikate

. Anstatt nur Zeilennummern zurückzugeben, könnten Sie eine zweite Spalte mit IDs haben, die zurückgegeben werden sollen.

Für eine Liste von 20 Millionen ganzen Zahlen dauert es weniger als eine Sekunde.

Unit: seconds 
              expr  min   lq  mean  median   uq  max neval 
x[V1 == x[V1 %in% z, max(.SD), ], , which = T] 0.00076113 0.000871416 0.02571112 0.000945884 0.00109958 0.6195882 25 

Answer 4

find_list$X[which.max(sapply(find_list$find_list, function(myX) 
    attr(gregexpr(myX, lookup_value)[[1]], "match.length")))] 
#[1] "f" 

DATA

find_list = structure(list(X = c("a", "b", "c", "d", "e", "f", "g"), find_list = c(1L, 
12L, 123L, 124L, 125L, 1234L, 1235L)), .Names = c("X", "find_list" 
), class = "data.frame", row.names = c(NA, -7L)) 

lookup_value = 12345678