[R data.table] 키와 빠른 이진 탐색 기반의 부분 집합 선택 (Key and fast binary search based subset)
R 분석과 프로그래밍/R 데이터 전처리 2020. 10. 11. 23:19이전 포스팅에서는 R data.table 에서 여러개의 변수를 처리하는 특수부호 .SD, .SDcols, data.table의 기본구문 DT[i, j, by]를 이용하여 행 subset과 열 select하고 계산하기에 대해서 알아보았습니다.
이번 포스팅에서는 data.table 에서 "키와 빠른 이진탐색 기반의 부분집합 선택 (Key and fast binary search based subset)" 에 대해서 소개하겠습니다. data.frame 대비 data.table의 subset 속도가 미친 듯이(!) 더 빠르고 메모리 효율적인 이유가 "Key and binary search based subset" 에 있습니다.
R data.table에서 key 설정해서 정렬을 해두어 이진탐색으로 빠르게 관측치를 선별할 수 있는 것은 마치 DB에서 index를 설정해서 select 나 join 할 때 성능을 향상할 수 있는 것과 유사한 면이 있습니다.
이번 포스팅은 data.table의 vignette을 거의 번역하다시피 대부분 참조하여 작성하였습니다.
(1) data.table에서 키란 무엇인가? (What is Key in R data.table?)
(2) 이진 탐색이란 무엇인가? (What is binary search?)
(3) data.table에서 키를 설정하고, 확인하고, 사용하기 (Set, get and use keys on a data.table)
(4) 느린 벡터 스캔(slow vector scan)과 빠른 이진 탐색(fast binary search) 속도 비교
(1) data.table에서 키란 무엇인가? (What is Key in R data.table?) |
data.table 의 Key에 대해 알아보기 전에 먼저 data.frame 의 행 이름 속성(row names attributes)에 대해서 먼저 알아보겠습니다. 아래와 같이 'DF'라는 이름의 간단한 data.frame을 만들어서 예를 들어보겠습니다.
library(data.table) set.seed(1) DF = data.frame(g1 = c(rep("a", 6), rep("b", 4)), g2 = sample(1:3, 10, TRUE), x = sample(10), stringsAsFactors = FALSE, row.names = sample(LETTERS[1:10])) > DF g1 g2 x F a 1 2 D a 3 6 I a 2 9 H a 2 8 B a 3 1 G a 3 3 A b 2 5 C b 2 10 J b 2 7 E b 2 4 > > rownames(DF) [1] "F" "D" "I" "H" "B" "G" "A" "C" "J" "E"
|
우리는 data.frame의 행(row)을 아래 예시의 DF["A", ] 처럼 부분집합을 선택해서 가져올 수 있습니다.
> # subset a particular row using its row name > DF["A", ] g1 g2 x A b 2 5 |
즉, data.frame의 행이름은 data.frame의 행에 대한 인덱스(index)와 다름없습니다. 그렇지만,
1. 각 행은 정확하게 하나의 행 이름(excactly one row name)으로 한정됩니다.
(만약 2개 이상의 이름을 가져야 하는 경우 제약)
2. 그리고, 행 이름은 유일(unique)해야 합니다. 아래의 예시와 같이 행 이름에 중복이 있으면 "duplicate 'row.names' are not allowed" 라는 에러가 발생합니다.
> # row names should be unique > rownames(DF) = sample(LETTERS[1:3], 10, TRUE) Error in `.rowNamesDF<-`(x, value = value) : duplicate 'row.names' are not allowed In addition: Warning message: non-unique values when setting 'row.names': 'A', 'B'
|
위의 예제 data.frame을 data.table로 변환해보겠습니다.
> # convert a data.frame to a data.table > DT = as.data.table(DF) > DT g1 g2 x 1: a 1 2 2: a 3 6 3: a 2 9 4: a 2 8 5: a 3 1 6: a 3 3 7: b 2 5 8: b 2 10 9: b 2 7 10: b 2 4 > # Note that row names have been reset. > rownames(DT) [1] "1" "2" "3" "4" "5" "6" "7" "8" "9" "10"
|
위에서 data.frame을 data.table로 변환한 결과 행 이름이 재설정되었습니다. 비록 data.table이 data.frame을 상속하기 때문에 행 이름 속성을 가지고 있기는 하지만, data.table은 행 이름을 절대 사용하지 않습니다.
만약 data.table에서 행 이름을 계속 유지하고 싶다면 as.data.table(DF, keep.rownames = TRUE) 라는 옵션을 설정해주면 아래의 예시처럼 'rn'(row names) 이라 이름의 칼럼에 행 이름을 생성합니다.
> # if you like to preserve the row naems, keep.rownames = TRUE > # new column 'rn' is created > DT2 = as.data.table(DF, keep.rownames = TRUE) > DT2 rn g1 g2 x 1: F a 1 2 2: D a 3 6 3: I a 2 9 4: H a 2 8 5: B a 3 1 6: G a 3 3 7: A b 2 5 8: C b 2 10 9: J b 2 7 10: E b 2 4
|
data.frame의 행 이름(row names) 대신에 data.table 에서는 키(keys)를 설정하고 사용합니다. data.frame의 키(keys)를 한층 강화된 행 이름 (supercharged rownames) 이라고 생각할 수 있습니다.
data.frame의 행 이름과는 다른 data.table 의 키 특성 (Keys properties)은 다음과 같습니다.
- 키를 여러개의 칼럼에 설정할 수 있고, 칼럼은 다른 데이터 유형(예: 정수형, 실수형, 문자형, 요인형, 정수64형 등. 단, 리스트와 복소수형은 미지원) 을 사용할 수 있다.
- 유일성(Uniqueness) 제약이 없으며, 중복 키 값을 허용한다. 행은 키를 기준으로 정렬되므로, 키 칼럼의 어떤 중복값도 연속적으로 나타날 것이다.
- 키를 설정하는 것은 두가지 일을 한다.
a. 물리적으로 data.table의 행을 Reference에 의해 제공되는 칼럼을 기준으로 항상 오름차순으로 재정렬한다. (reorder by reference in increasing order)
b. 키에 해당하는 칼럼을 data.table의 'sorted'라고 불리는 속성을 설정함으로써 키 칼럼으로표시한다.
(2) 이진 탐색이란 무엇인가? (What is binary search?) |
컴퓨터공학에서 이진 탐색(bianry search, 또는 half-interval search, logarithmic search, binary chop 이라고도 함)이란 정렬이 되어 있는 배열(within a sorted array) 안에서 목표값(targer value)의 위치를 찾는 탐색 알고리즘을 말합니다.
이진탐색 알고리즘은 목표 값(Target value)와 정렬된 배열의 중간 원소(middle element of the sorted array)와 비교를 해서, 이 둘의 값이 같지 않으면 목표 값이 존재하지 않을 나머지 반절은 배제합니다. 그리고 다시 남아있는 반절의 배열에서의 새로운 중간 위치 원소와 목표 값을 비교하고, 이 둘의 값이 같지 않으면 목표 값이 존재하지 않을 나머지 반절을 배제합니다. 이 단순한 중간 원소와 목표값과의 비교하는 과정을 목표 값을 찾을 때까지 반복합니다.
아래의 예에서는 [1, 4, 5, 7, 9, 13, 14, 19, 27, 41, 44, 48, 64, 80, 85, 91, 94] 와 같이 정렬이 된 배열(sorted array)에 대해서 목표값 '9'를 찾아가는 과정을 이진 탐색 알고리즘으로 실행해 본 것입니다. 모두 4번의 실행이 필요했네요.
그러면 이진 탐색(binary search) 알고리즘이 순차 탐색 (seqneuce search) 알고리즘 보다 얼마나 더 효율적인지 최악의 경우의 시간 복잡도를 한번 비교해보겠습니다.
데이터의 전체 개수가 n개라고 하고 연산회수의 함수를 T(n) 이라고 했을 때, 순차 탐색 알고리즘의 최악의 경우의 연산회수 함수는 T(n) = n 이 됩니다.
반면에 이진 탐색 알고리즘의 최악의 경우, 아래와 같이 목표값과 비교를 할 때 마다 데이터의 반절 씩을 배제해 나가게 되면 마지막에 1개의 데이터만 남을 때까지 k + 1 번의 연산회수가 필요하고 했을 때 T(n)= k + 1 에서 k를 구해보면, 
가령, 100억명의 사람 중에 특정 1명을 찾으려고 했을 때, 순차 탐색 알고리즘으로 찾으려면 최악의 경우 100억명을 모두 뒤져서 제일 끝에 찾게 되면 100억번의 비교가 필요하게 됩니다. 반면에 이진 탐색 알고리즘으로 100억명 중에서 특정 1명을 찾으려면 최악의 경우 k = log2(10,000,000,000) = 33.2 로서 약 34 (=33+1)번만 비교 연산을 하면 어떤 경우에도 찾을 수가 있게 됩니다.
순차 탐색 알고리즘 vs. 이진 탐색 알고리즘 간의 최악의 연산회수는 10,000,000,000 번 연산 vs. 34 (=33+1)번 연산으로서 매우 매우 매우 큰 차이가 납니다.
* source: https://en.wikipedia.org/wiki/Binary_search_algorithm
data.table에서 key 를 설정하면 자동으로 물리적으로 오름차순으로 정렬하여 data.table을 생성한다고 했는데요, 이렇게 정렬해 놓은 배열에 대해 이진 탐색 알고리즘을 적용였으니 data.table의 데이터 조회가 매우 매우 빠른 것입니다.
(3) data.table에서 키를 설정하고, 확인하고, 사용하기 (Set, get, and use keys on a data.table) |
(3-1) data.table에서 키 설정하기 (Set keys on a data.table)
data.table에서 Key를 설정할 때는 setkey(DT, column_nm) 을 사용합니다. 그러면 왼쪽에 1, 2, 3, ..., n 처럼 정수로 key 가 부여되고 데이터는 키를 기준으로 오름차순 정렬이 됩니다.
또는 setkeyv(DT, "column_nm") 식으로 setkeyv() 함수안에 큰 따옴표로 키 기준 칼럼이름을 넣어서 사용하면 프로그래밍을 하기에 유용합니다.
MASS 패키지에 있는 Cars93 데이터셋에서 변수 몇개만 선별해서 DT 라는 이름의 data.table로 간단한 예제 데이터를 만들어서 예를 들어보겠습니다.
setkey(DT, Type) 으로 차종(Type)을 기준으로 키를 설정해주면 DT 데이터셋이 차종(Type)의 알파벳 오름차순 기준으로 물리적으로 정렬(reordered, sorted)이 된 data.table이 됩니다. 이때 키를 참조(reference)하여 재정렬이 되기 때문에 data.table의 행의 수와 같은 길이의 한 개의 칼럼에 대한 추가 메모리만 있으면 되므로 메모리 효율적입니다.
# b) Set, get adn use keys on a data.table # How can we set the column 'Type' as key in the data.table 'DT'? library(data.table) library(MASS) DT <- data.table(Cars93[, c("Model", "Type", "Price", "MPG.highway", "DriveTrain")]) > str(DT) Classes 'data.table' and 'data.frame': 93 obs. of 5 variables: $ Model : Factor w/ 93 levels "100","190E","240",..: 49 56 9 1 6 24 54 74 73 35 ... $ Type : Factor w/ 6 levels "Compact","Large",..: 4 3 1 3 3 3 2 2 3 2 ... $ Price : num 15.9 33.9 29.1 37.7 30 15.7 20.8 23.7 26.3 34.7 ... $ MPG.highway: int 31 25 26 26 30 31 28 25 27 25 ... $ DriveTrain : Factor w/ 3 levels "4WD","Front",..: 2 2 2 2 3 2 2 3 2 2 ... - attr(*, ".internal.selfref")=<externalptr> # The data.table is now "reordered( or sorted)" by the column we provided - 'Type'. # Memory efficient, because we reorder by reference, we only require additional memory of # one column of length equal to the number of nrows in the data.table setkey(DT, Type) > head(DT) Model Type Price MPG.highway DriveTrain 1: 90 Compact 29.1 26 Front 2: Cavalier Compact 13.4 36 Front 3: Corsica Compact 11.4 34 Front 4: LeBaron Compact 15.8 28 Front 5: Spirit Compact 13.3 27 Front 6: Tempo Compact 11.3 27 Front # alternatively we can provide character vectors to the function 'setkeyv()' setkeyv(DT, "Type") # useful to program with |
(3-2) data.table에서 키 확인하기 (Get keys on a data.table)
Key 확인은 key() 함수로 합니다. 만약 키가 설정되어 있지 않다면 'NULL'을 반환합니다.
# How can we get the column(s) a data.table is keyed by? # if no key is set, it returns 'NULL'. > key(DT)[1] "Type" |
(3-3) data.table에서 키 사용하여 부분집합 가져오기 (Subset using keys on a data.table)
이렇게 키가 설정된 data.table에서 키의 특정 값과 일치하는 행의 부분집합을 가져오는 방법은 매우 쉽고 빠르며 (정렬된 상태에서 이진 탐색을 하므로 매우 빠름!), 여러가지 방법이 있습니다.
차종(Type) 중에서 "Van" 차종만을 가져오고 싶다면, DT[.("Van"), DT[J("Van")], DT[list("Van")], DT["Van"], DT[Type == "Van"] 중에서 아무거나 사용할 수 있습니다. (이게 좋을 수도 있는데요, 좀 헷갈리기도 합니다. ^^;)
# Subset all rows where the Type matches "Van" > DT[.("Van")] Model Type Price MPG.highway DriveTrain 1: Lumina_APV Van 16.3 23 Front 2: Astro Van 16.6 20 4WD 3: Caravan Van 19.0 21 4WD 4: Aerostar Van 19.9 20 4WD 5: MPV Van 19.1 24 4WD 6: Quest Van 19.1 23 Front 7: Silhouette Van 19.5 23 Front 8: Previa Van 22.7 22 4WD 9: Eurovan Van 19.7 21 Front # alternatively as below DT[J("Van")] DT[list("Van")] DT["Van"] DT[Type == "Van"]
|
만약 키를 설정한 칼럼에서 여러개의 값에 해당하는 모든 행을 부분집합으로 가져오고 싶다면 c() 의 concatenate() 를 이용하여 원하는 모든 값을 써주면 됩니다.
# We can subset any amount of values s required. # This returns all columns corresponding to those rows where Type column matches either "Compact" or "Van". DT[c("Compact", "Van")] DT[.(c("Compact", "Van"))]
|
(3-4) 여러개의 칼럼에 복수의 키를 설정하기 (Keys and multiple columns)
복수의 칼럼에 대해 키를 설정하려면 setkey(DT, Col_1, Col_2, ...) 또는 프로그래밍에 유용하도록 setkeyv(DT, c("Col_1", "Col_2", ...) 하는 형식으로 여러개 칼럼을 써주면 됩니다.
아래 예에서는 차종(Type), 동력전달장치(DriveTrain) 의 두 개 칼럼에 대해 키를 설정해보겠습니다.
# We can set key on multiple columns and they can be of multiple types. # How can I set keys on both 'Type' and 'Model' columns? setkey(DT, Type, DriveTrain) # or alternatively, provide a character vector of column names setkeyv(DT, c("Type", "DriveTrain")) # useful for programming > key(DT) [1] "Type" "DriveTrain" |
이러면 (a) 차종(Type)을 참조하여 먼저 정렬을 하고, (b) 동력전달장치(DriveTrain)를 참조하여 다음으로 정렬을 하게 됩니다.
> # It sorts the data.table by the column 'Type' and then by 'Model' by reference
|
이번에는 차종(Type)이 "Compact"이고, 동력전달장치(DriveTrain)이 "Rear"인 모든 행을 부분집합으로 가져와보겠습니다. 이때 (a) 첫번째 키인 차종(Type)을 참조하여 차종이 "Compact"인 행을 매칭하고, (b) 차종이 "Compact"인 행에 한정해서 두번째 키인 동력전달장치(DriveTrain)를 참조하여 동력전달장치가 "Rear"인 행을 가져옮으로써 속도가 매우 빠르게 됩니다.
(즉, 키 설정을 통해 재정렬 + 이진 탐색 알고리즘 + 복수 키 subset 시 첫번째 키의 부분집합에 한정해서 두번째 키 탐색함으로써 속도 획기적 향상)
> # Subset all rows using key columns where first key column 'Type' matches 'Compact' |
위에서 data.table DT에 차종(Type), 동력전달장치(DriveTrain) 의 두 개 칼럼에 키를 설정하였는데요, 첫번째 키인 차종(Type)을 참조하여 차종이 "Compact"인 모든 행의 부분집합을 가져오는 것은 DT[.("Compact")] 또는 간단하게 DT["Compact"] 하면 됩니다.
반면에 두번째 키인 동력전달장치(DriveTrain)를 참조하여 "Rear"(후륜)인 모든 행의 부분집합을 가져오고 싶으면 첫번째 키인 차종(Type)의 고유한 값들을 무시할 수 없으므로 첫번째 키인 차종(.(unique(Type)))의 고유한 값도 함께 가져와야 해서 DT[.(unique(Type), "Rear"] 처럼 써줘야 합니다.
아래의 두번째 예인 DT[.(unique(Type), "Rear"] 의 결과에서 보면 12번째, 18번째 결과행에 차종(Type)이 "Small"과 "Van"인 경우 <NA> 로서 관측치가 없음에도 불구하고 unique(Type)에 "Small", "Van"도 포함이 되어있으므로 <NA>라는 표기와 함께 결과가 반환되었습니다.
> key(DT) > > # Subset all rows where just the first key column 'Type' matches "Compact". > DT[.("Compact")] # or in this case simply DT["Compact"] > > > # Subset all rows where just the second key column 'DriveTrain' matches "Rear".
|
참고로, 설정되어 있는 키를 제거하려면 setkey(DT, NULL) 처럼 NULL 을 키로 설정해주면 됩니다.
(4) 느린 벡터 스캔(slow vector scan)과 빠른 이진 탐색(fast binary search) 속도 비교 |
data.table에서 벡터 스캔(Vector scan) 방식과 이진 탐색(Binary search) 방식의 subset 속도 차이를 비교하기 위해서 1억개의 행과 3개의 칼럼을 가진 data.table 샘플 데이터를 만들어보겠습니다. 데이터 크기가 1,907.4 Mb 이군요.
## -- Performance of binary search approach ## - Create a sample data.table with 100 million rows and 3 columns. set.seed(1) N = 1e8 DT = data.table(k1 = sample(LETTERS, N, replace = TRUE), k2 = sample(1000, N, replace = TRUE), val = rnorm(N, mean = 0, sd = 1)) ## - number of rows DT[, .N] # [1] 100000000 ## - size in Mb units print(object.size(DT), units = "Mb") # 1907.4 Mb
|
1억개 행을 가진 샘플 데이터가 준비되었으니,
(a) Key가 없는 상태에서 전체 행을 모조리 뒤져서 (k1 == "A" & k2 == 750) 를 만족하는 행에는 TRUE, 만족하지 않는 행에는 FALSE 논리벡터를 생성하고 (TRUE & TRUE) 인 행만 subset 해오는 벡터 스캔(vector scan) 과,
(b) Key가 있고, Key를 기준으로 정렬(sorted)이 된 data.table에서 (k1 == "A" & k2 == 750) 를 만족하는 행을 이진 탐색(binary search) 방식으로 subset 해오는 방식의 총 소요시간(elapsed time)을 비교해보겠습니다.
아래에 결과를 보면 벡터 스캔 방식은 2.850 초 vs. 이진 탐색 방식은 0.001 초 걸렸다고 나오네요. 이 결과로 보면 이진 탐색 방식이 벡터 스캔 방식보다 2,850배 더 빠른 셈이군요! 비교 불가일 정도로 data.table의 Key를 활용한 이진탐색 방식이 겁나게 빠릅니다.
벡터 스캔 방식은 subset 조건 만족 여부에 대한 논리 벡터 (TRUE, FALSE)를 행의 개수만큼 생성해야 하므로 메모리 효율 측면에서도 이진 탐색보다 비효율적입니다.
구분 |
(a) 느린 벡터 스캔 (slow vector scan) |
(b) 빠른 이진 탐색 (fast binary search) |
| key | setkey(DT, NULL) key(DT) | setkey(DT, k1, k2) key(DT) # [1] "k1" "k2" |
syntax |
t_vc <- system.time(vc <- DT[k1 == "A" & k2 == 750]) |
t_bs <- system.time(bs <- DT[.("A", 750)]) |
elapsed time |
t_vc # user system elapsed # 2.094 0.720 2.850 |
t_bs # user system elapsed # 0.001 0.000 0.001 |
head |
head(vc) # k1 k2 val # 1: A 750 1.11941277 # 2: A 750 -0.06405564 # 3: A 750 1.67845850 # 4: A 750 0.32760125 # 5: A 750 -0.08287104 # 6: A 750 -0.97940166 |
head(bs) # k1 k2 val # 1: A 750 1.11941277 # 2: A 750 -0.06405564 # 3: A 750 1.67845850 # 4: A 750 0.32760125 # 5: A 750 -0.08287104 # 6: A 750 -0.97940166 |
dimension |
dim(vc) # [1] 3849 3 |
dim(bs) # [1] 3849 3 |
[Reference]
* R data.table vignette: https://cran.r-project.org/web/packages/data.table/vignettes/datatable-keys-fast-subset.html
* Binary search algorithm: https://en.wikipedia.org/wiki/Binary_search_algorithm
많은 도움이 되었기를 바랍니다.
행복한 R 데이터 분석가 되세요.
