是否有更高效的搜索算法

我試圖根據兩個條件將兩個數據集合併到R中。他們必須有相同的ID和年份。其中一個載體具有約10000大小和其他2000年我想，如果我做一個二級逐一搜索，計算時間會爆炸。數據按id和年份排序。有沒有比天真的比較更有效的搜索算法？是否有更高效的搜索算法

來源

2014-04-19 Yan Song

的數據進行排序？ – Fernando

是的。它按照id和年份排序。我編輯了這個問題。 –

需要注意的是10K和2K是計算機數量相對較少。所以，這裏「爆炸」意味着......大約1ms或者什麼東西（當然是非常相對的，但你明白我的觀點）？由於它已排序，所以當事物不匹配時可以跳過。 – keyser

該問題有很多解決方案，例如，通過合併，索引，循環（如你所說）。

但是，最優雅的解決方案是使用data.table程序包，該程序包管理數據集的速度非常快，可以認爲是data.frame的演變版本。

讓我們先設置數據：根據您在問題中提供的有限信息，下面是解決該問題的虛擬嘗試。

install.packages("data.table") 

library(data.table) 

set.seed(100) 
dt1 <- data.table(
    id = 1:10000, 
    Year = sample(1950:2014,size=10000,replace = TRUE), 
    v1 = runif(10000) 
) 
head(dt1) 

dt2 <- data.table(
    id = sample(1:10000,2000), 
    Year = sample(1950:2014,size=2000,replace = TRUE), 
    v2 = runif(2000), 
    v3 = runif(2000) 
) 
head(dt2)

數據一旦建立，其餘部分就非常簡單。

第1步：設置密鑰。

setkey(dt1,id,Year) # Set keys in first table 
setkey(dt2,id,Year) # Set keys in second table

第2步：合併你想要的任何方式。

dt1[dt2,nomatch=0] 
dt2[dt1,nomatch=0]

合併數據所用的時間約爲0.02秒。這對於非常大的數據集也非常快速。

system.time(dt1[dt2,nomatch=0]) # 0.02 sec 
system.time(dt2[dt1,nomatch=0]) # 0.02 sec

要了解更多關於data.table

?example(data.table)

希望這有助於！

如果不是這樣，PLZ發佈更多細節！

來源

2014-04-20 06:30:37 Shambho

感謝您提及data.table包。我發現這個介紹data.frame helpfu。顯然，data.table使用二進制搜索而不是矢量掃描。所以速度要快得多。 [鏈接]（http://cran.r-project.org/web/packages/data.table/vignettes/datatable-intro.pdf） –

完全正確。還有另外兩個不錯的閱讀。試試：'vignette（「datatable-faq」）'和 'vignette（「datatable-timing」）' – Shambho

@YanSong，[this answer]（http://stackoverflow.com/a/20057411/559784）可能有助於回答一些關於'data.table'和二進制搜索的問題。 – Arun

是否有更高效的搜索算法

回答

相關問題