이전 포스팅에서는 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)은 다음과 같습니다. 


  1. 키를 여러개의 칼럼에 설정할 수 있고, 칼럼은 다른 데이터 유형(예: 정수형, 실수형, 문자형, 요인형, 정수64형 등. 단, 리스트와 복소수형은 미지원) 을 사용할 수 있다. 
  2. 유일성(Uniqueness) 약이 없으며, 중복 키 값을 허용한다. 행은 키를 기준으로 정렬되므로, 키 칼럼의 어떤 중복값도 연속적으로 나타날 것이다. 
  3. 키를 설정하는 것은 두가지 일을 한다. 
    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) 의 두 개 칼럼에 대해 키를 설정해보겠습니다.



# c) Keys and multiple columns
# 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
> head(DT)
      Model    Type Price MPG.highway DriveTrain
1:   Legacy Compact  19.5          30        4WD
2:       90 Compact  29.1          26      Front
3: Cavalier Compact  13.4          36      Front
4:  Corsica Compact  11.4          34      Front
5:  LeBaron Compact  15.8          28      Front
6:   Spirit Compact  13.3          27      Front

 



이번에는 차종(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'
> # and second key column 'DriveTrain' matches 'Rear'
> # -- "Compact" is first matched against the first key column 'Type',
> # and within those matching rows, "Rear" is mached against the second key columns 'DriveTrain'
> # to obtain row indices where both 'Type' and 'DriveTrain' match the given values. --
> DT[.("Compact", "Rear")]
   Model    Type Price MPG.highway DriveTrain
1:  190E Compact  31.9          29       Rear
2:   240 Compact  22.7          28       Rear




위에서 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)
[1] "Type"       "DriveTrain"

>

> # Subset all rows where just the first key column 'Type' matches "Compact".

> DT[.("Compact")] # or in this case simply DT["Compact"]
       Model    Type Price MPG.highway DriveTrain
 1:   Legacy Compact  19.5          30        4WD
 2:       90 Compact  29.1          26      Front
 3: Cavalier Compact  13.4          36      Front
 4:  Corsica Compact  11.4          34      Front
 5:  LeBaron Compact  15.8          28      Front
 6:   Spirit Compact  13.3          27      Front
 7:    Tempo Compact  11.3          27      Front
 8:   Accord Compact  17.5          31      Front
 9:      626 Compact  16.5          34      Front
10:   Altima Compact  15.7          30      Front
11:  Achieva Compact  13.5          31      Front
12:  Sunbird Compact  11.1          31      Front
13:      900 Compact  28.7          26      Front
14:   Passat Compact  20.0          30      Front
15:     190E Compact  31.9          29       Rear
16:      240 Compact  22.7          28       Rear

>

>

> # Subset all rows where just the second key column 'DriveTrain' matches "Rear".
> DT[.(unique(Type), "Rear")]
             Model    Type Price MPG.highway DriveTrain
 1:           190E Compact  31.9          29       Rear
 2:            240 Compact  22.7          28       Rear
 3:     Roadmaster   Large  23.7          25       Rear
 4:        Caprice   Large  18.8          26       Rear
 5: Crown_Victoria   Large  20.9          26       Rear
 6:       Town_Car   Large  36.1          26       Rear
 7:           535i Midsize  30.0          30       Rear
 8:            Q45 Midsize  47.9          22       Rear
 9:          SC300 Midsize  35.2          23       Rear
10:           300E Midsize  61.9          25       Rear
11:         Cougar Midsize  14.9          26       Rear
12:           <NA>   Small    NA          NA       Rear
13:         Camaro  Sporty  15.1          28       Rear
14:       Corvette  Sporty  38.0          25       Rear
15:        Mustang  Sporty  15.9          29       Rear
16:           RX-7  Sporty  32.5          25       Rear
17:       Firebird  Sporty  17.7          28       Rear
18:           <NA>     Van    NA          NA       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)
# NULL

 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 algorithmhttps://en.wikipedia.org/wiki/Binary_search_algorithm



많은 도움이 되었기를 바랍니다. 

행복한 R 데이터 분석가 되세요.



728x90
반응형
Posted by Rfriend
,