我想要一個非常快速的搜索，看起來，使用哈希（通過環境）是最好的方法。現在，我得到了一個運行環境的例子，但它不會返回我所需要的。R：列表（環境）中的快速哈希搜索

下面是一個例子：

a <- data.table::data.table(a=c(1, 3, 5), b=c(2, 4, 6), time=c(10, 20, 30)) 
my_env <- list2env(a) 
x <- a[2, .(a, b)] # x=c(3,4) 
found <- get("x", envir = my_env)

我希望found = c(3, 4, 20)但收到found = c(3, 4) （我想代替返回未知的行子集的整行）

底色：我有一個包含osrm計算的路由源和目的地的巨大列表，例如

lattitude1, longitude1, lattitude2, longitude2, travel-time 
46.12, 8.32, 47.87, 9.92, 1036 
...

該列表在第一個示例中包含約100000行。在data.table中使用二進制搜索將我的代碼加速了100倍，但是一次搜索仍然需要1 ms。由於我必須在模擬過程中搜尋很多路線（大約2e5次搜索），我希望能夠更快。
@Gregor：我在爲r的初學者，但我不認爲我的問題是重複的：

我知道第二個環節，這是專家們列出可能性的抽象的概念。此外，它是4歲。
我不知道第一個鏈接，但從這些答案我看不到我是否應該切換到環境以及實現如何工作。也沒有關於搜索巨大列表的一部分的討論。

摘要（感謝DigEmAll低於他的運行例子）：

對整數使用RCPP，搜索是更少的內存，沒有任何質量損失費。更重要的是，它快了3倍。
當您想查找雙打（必須轉換爲字符串）時，請勿使用散列環境。
現有代碼中的實現應該很容易。

來源

2016-05-04 Christoph

嗯......我沒有得到你想要達成的目標，但是這裏有一些誤解。首先，'list2env'將列表轉換爲evironment，data.frame（或data.table）是列的列表......所以最後'my_env'將包含3個變量'a，b，time'，對應於列。然後，'get（「x」，envir = my_env）'在my_env中搜索一個名爲「x」的變量，但由於它不存在，它會在環境層次結構中上升並在全局環境中找到「x」（這是你剛剛定義的'x'） – digEmAll

順便說一句，對data.table行的鍵控訪問非常快，所以既然你已經在使用data.table，我認爲你不需要使用環境.. – digEmAll

@digEmAll：好的:-)我明白了。有沒有辦法，在環境中使用散列搜索？看到我上面的編輯。否則我會等很多...如果有幫助，我可以上傳一個測試程序。 – Christoph

下面是使用環境和data.table一個例子，代碼是不言自明：

library(data.table) 

# create a big random example (160k rows) 
set.seed(123) 
fromTo <- expand.grid(1:400,1:400) 
colnames(fromTo) <- c('a','b') 
DF <- as.data.frame(cbind(fromTo,time=as.integer(runif(nrow(fromTo), min = 1, max=500)))) 

# setup the environment to use it as hashtable: 
# we simply put the times inside an enviroment using 
# a|b (concatenation of a with b) as key 
timesList <- as.list(DF$time) 
names(timesList) <- paste(DF$a,DF$b,sep='|') 
timesEnv <- list2env(timesList) 

# setup the data.table to use it as hashtable 
DT <- setDT(DF,key=c('a','b')) 

# create search functions 
searchUsingEnv <- function(a,b){ 
    time <- get(paste(a,b,sep='|'),envir=timesEnv,inherits=FALSE) 
    return(time) 
} 
searchUsingDataTable <- function(from,to){ 
    time <- DT[.(from,to),time] 
    return(time) 
}

基準：

# benchmark functions 
# i.e. we try to search ~16K rows in ourtwo kind of hashtables 
benchEnv <- function(){ 
    n <- nrow(fromTo) 
    s <- as.integer(n * 0.9) 
    for(i in s:n){ 
    searchUsingEnv(fromTo[i,'a'],fromTo[i,'b']) 
    } 
} 
benchDT <- function(){ 
    n <- nrow(fromTo) 
    s <- as.integer(n * 0.9) 
    for(i in s:n){ 
    searchUsingDataTable(fromTo[i,'a'],fromTo[i,'b']) 
    } 
} 

# let's measure the performances 
> system.time(benchEnv(), gcFirst = TRUE) 
user system elapsed 
2.26 0.00 2.30 
> system.time(benchDT(), gcFirst = TRUE) 
user system elapsed 
42.34 0.00 42.56

結論：
環境似乎重複單鍵訪問data.table要快得多，所以你可以試試我們e it。

編輯：

Enviroments具有快速訪問，但他們只能佔據超過一倍多存儲器串鑰匙。所以，我添加使用Rcpp和std::map<>有多個值映射的例子：
（注：如果您使用的是Windows，你需要爲了使RCPP工作安裝RTools）

library(data.table) 
library(Rcpp) 
library(inline) 

nRows <- 1e7 

############# create data.table "DT" containing coordinates and times 
generate_routes_dt <- function(nmax) { 
    set.seed(123) 
    routes <- data.table(lat1 = numeric(nmax), 
    lng1 = numeric(nmax), 
    lat2 = numeric(nmax), 
    lng2 = numeric(nmax), 
    time = numeric(nmax)) 
    tmp <- sample(seq(46, 49, length.out = nmax), nmax) 
    routes$lat1 <- tmp 
    tmp <- sample(seq(8, 10, length.out = nmax), nmax) 
    routes$lng1 <- tmp 
    tmp <- sample(seq(46, 49, length.out = nmax), nmax) 
    routes$lat2 <- tmp 
    tmp <- sample(seq(8, 10, length.out = nmax), nmax) 
    routes$lng2 <- tmp 
    tmp <- sample(seq(0, 1e7, length.out = nmax), nmax) 
    routes$time <- as.integer(tmp) 
    data.table::setkey(routes, lat1, lng1, lat2, lng2) 
    return(routes) 
} 

DT <- generate_routes_dt(nRows) 

############# create data.table search function 
searchUsingDataTable <- function(lat_1,lng_1,lat_2,lng_2){ 
    time <- DT[.(lat_1,lng_1,lat_2,lng_2),time] 
    return(time) 
} 
############# 

############# create Rcpp search function 
# the following code create 2 functions: createMap and getTime 
# usage: 
# map <- createMap(lat1Vec,lng1Vec,lat2Vec,lng2Vec,timesVec) 
# t <- getTime(map,lat1,lng1,lat2,lng2) 
sourceCpp(code= 
' 
#include <Rcpp.h> 

    class MultiKey { 
    public: 
    double lat1; 
    double lng1; 
    double lat2; 
    double lng2; 

    MultiKey(double la1, double ln1, double la2, double ln2) 
     : lat1(la1), lng1(ln1), lat2(la2), lng2(ln2) {} 

    bool operator<(const MultiKey &right) const 
    { 
     if (lat1 == right.lat1) { 
      if (lng1 == right.lng1) { 
       if (lat2 == right.lat2) { 
        return lng2 < right.lng2; 
       } 
       else { 
        return lat2 < right.lat2; 
       } 
      } 
      else { 
       return lng1 < right.lng1; 
      } 
     } 
     else { 
      return lat1 < right.lat1; 
     } 
    }  
    }; 


    // [[Rcpp::export]] 
    SEXP createMap(Rcpp::NumericVector lat1, 
       Rcpp::NumericVector lng1, 
       Rcpp::NumericVector lat2, 
       Rcpp::NumericVector lng2, 
       Rcpp::NumericVector times){ 
    std::map<MultiKey, double>* map = new std::map<MultiKey, double>; 
    int n1 = lat1.size(); 
    int n2 = lng1.size(); 
    int n3 = lat2.size(); 
    int n4 = lng2.size(); 
    int n5 = times.size(); 
    if(!(n1 == n2 && n2 == n3 && n3 == n4 && n4 == n5)){ 
     throw std::range_error("input vectors lengths are different"); 
    } 
    for(int i = 0; i < n1; i++){ 
     MultiKey key(lat1[i],lng1[i],lat2[i],lng2[i]); 
     map->insert(std::pair<MultiKey, double>(key, times[i])); 
    } 
    Rcpp::XPtr< std::map<MultiKey, double> > p(map, true); 
    return(p); 
    } 

    // [[Rcpp::export]] 
    Rcpp::NumericVector getTime(SEXP mapPtr, 
           double lat1, 
           double lng1, 
           double lat2, 
           double lng2){ 
    Rcpp::XPtr< std::map<MultiKey, double> > ptr(mapPtr); 
    MultiKey key(lat1,lng1,lat2,lng2); 
    std::map<MultiKey,double>::iterator it = ptr->find(key); 
    if(it == ptr->end()) 
     return R_NilValue; 

    return Rcpp::wrap(it->second); 
    } 

') 

map <- createMap(DT$lat1,DT$lng1,DT$lat2,DT$lng2,DT$time) 

searchUsingRcpp <- function(lat_1,lng_1,lat_2,lng_2){ 
    time <- getTime(map,lat_1,lng_1,lat_2,lng_2) 
    return(time) 
} 
############# 

############# benchmark 
set.seed(1234) 
rowsToSearchOneByOne <- DT[sample.int(nrow(DT),size=nrow(DT),replace=FALSE),] 

bench <- function(searchFun2Use){ 
    for(i in nrow(rowsToSearchOneByOne)){ 
    key <- rowsToSearchOneByOne[i,] 
    searchFun2Use(key$lat1,key$lng1,key$lat2,key$lng2) 
    } 
} 

microbenchmark::microbenchmark(
    bench(searchUsingRcpp), 
    bench(searchUsingDataTable), 
    times=100) 
#############

基準結果：

Unit: microseconds 
         expr  min  lq  mean median  uq  max neval 
     bench(searchUsingRcpp) 360.959 381.7585 400.4466 391.999 403.9985 665.597 100 
bench(searchUsingDataTable) 1103.034 1138.0740 1214.3008 1163.514 1224.9530 2035.828 100

注：

我真的不THI nk使用double作爲鍵是個好主意......浮點值應該用於使用某個容差或者在一個範圍內進行搜索，而不是查找地圖內的完美匹配。

來源

2016-05-04 14:16:08 digEmAll

非常感謝你的例子:-)）我修改了它以在我的情況下進行測試，看起來，哈希搜索在1e5行或更多行中最好與DT一樣好。看到我上面的評論和要點。我真的很感激，如果你可以看看它，就像我預料的那樣，會有相反的結果。 – Christoph

@Christoph：在我的示例中data.table比較慢，這是由於函數調用的開銷（因爲它創建了一箇中間的data.table，它與大的一個進行連接等等）......環境對於單個accces更快。所以：如果你正在搜索，很多時候，只有一個單一的行使用環境，否則，如果你搜索，很多次，很多行使用data.table ... – digEmAll

@Christoph：無論如何，你應該考慮使用Rcpp並使用它編寫一些函數（也許標準庫C++地圖）... – digEmAll

R：列表（環境）中的快速哈希搜索

回答

編輯：

相關問題