더 효율적인 검색 알고리즘이 있습니까

Question

두 개의 데이터 세트를 두 개의 기준에 따라 R에 병합하려고합니다. 그들은 같은 이드와 해를 가져야한다. 벡터 중 하나의 크기는 약 10000이고 다른 하나는 2000입니다. 두 단계를 하나씩 검색하면 계산 시간이 폭발 할 것입니다. 데이터는 ID와 연도별로 정렬됩니다. 순진 비교보다 효율적인 검색 알고리즘이 있습니까?

Answer 1

이 문제에 대한 해결책은 여러 가지가 있습니다. 병합, 색인 작성, 반복 (자네가 말했듯이).

그러나 가장 좋은 해결책은 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 

이 도움이

?example(data.table) 

data.table 희망에 대한 자세한 내용을 보려면!

그렇지 않은 경우 자세한 정보를 게시하십시오!