이번 포스팅에서는 PyTorch 에서 인덱싱(indexing)과 슬라이싱(slicing)을 이용해서 텐서 내 원하는 위치의 원소 부분집합을 가져오는 방법을 소개하겠습니다. PyTorch 로 딥러닝을 할 때 인풋으로 사용하는 데이테셋이 다차원의 행렬인 텐서인데요, 인덱싱과 슬라이싱을 자주 사용하기도 하고, 또 차원이 많아질 수록 헷갈리기도 하므로 정확하게 익혀놓을 필요가 있습니다. NumPy의 인덱싱, 슬라이싱을 이미 알고 있으면 그리 어렵지 않습니다. 

 

(1) 파이토치 텐서 인덱싱 (indexing of PyTorch tensor) 

(2) 파이토치 텐서 슬라이싱 (slicing of PyTorch tensor)

(3) 1개 값만 가지는 파이토치 텐서에서 숫자 가져오기 : tensor.item() 

(4) 파이토치 텐서 재구조화 (reshape)

 

 

PyTorch tensor indexing

 

 

(1) 파이토치 텐서 인덱싱 (indexing of PyTorch tensor)

 

먼저, 예제로 사용할 PyTorch tensor를 NumPy ndarray를 변환해서 만들어보겠습니다.

torch.Size([3, 5]) 의 형태를 가진 텐서를 만들었습니다. 

 

import torch
import numpy as np

## -- creating a tensor object
x = torch.tensor(
    np.arange(15).reshape(3, 5))

print(x)
# tensor([[ 0,  1,  2,  3,  4],
#         [ 5,  6,  7,  8,  9],
#         [10, 11, 12, 13, 14]])


## -- shape, size of a tensor

x.shape
# torch.Size([3, 5])

x.size(0)
# 3

x.size(1)
# 5

 

 

다양한 인덱싱 시나리오별로 예를 들어서 설명을 해보겠습니다. 

 

 

(1-1) 1번 행 전체를 인덱싱 해오기 

 

## indexing using position number
x[1]  # or equivalently x[1, :]
# tensor([5, 6, 7, 8, 9])

 

 

(1-2) 1번 행, 2번 열 원소 인덱싱 해오기

 

x[1, 2]
# tensor(7)

 

 

(1-3) 1번 열 전체를 인덱싱 해오기

 

x[:, 1]
# tensor([ 1,  6, 11])

 

 

(1-4) 1번 열, 블리언(Boolean) True 인 행만 인덱싱 해오기

 

## indexing using Boolean
x[1][[True, False, False, False, True]]
# tensor([5, 9])

 

 

(1-5) 1번 열, 텐서(tensor)의 값의 행만 인덱싱 해오기

 

## indexing using a tensor
x[1][torch.tensor([1, 3])]
# tensor([6,8])

 

 

(1-6) 1번 열을 가져오되, 행은 리스트의 위치 값 순서대로 바꾸어서 가져오기

 

## changing the position using indexing
x[1, [4,3,0,1,2]]
# tensor([9, 8, 5, 6, 7])

 

 

(1-7) 행 별로 열의 위치를 달리해서 값 가져오기

(예) 0번 행의 4번 열, 1번 행은 3번 열, 2번 행은 2번 열의 값 가져오기

 

## 행별로 인덱싱할 위치를 바뀌가면서 인덱싱하기
x[torch.arange(x.size(0)), [4,3,2]]
# tensor([ 4,  8, 12])

 

 

(1-8) 전체 행의 마지막 열(-1) 값 가져오기

 

## -1 : last elements
x[:, -1]
# tensor([ 4,  9, 14])

 

 

(1-9) 인덱싱한 위치에 특정 값을 재할당 하기

(예) 1번 행에 값 '0'을 재할당하기

 

## asinging new value using indexing
x[1] = 0


print(x)
# tensor([[ 0,  1,  2,  3,  4],
#         [ 0,  0,  0,  0,  0],   <----- '0' 으로 재할당 됨
#         [10, 11, 12, 13, 14]])

 

 

(2) 파이토치 텐서 슬라이싱 (slicing of PyTorch tensor)

 

 

(2-1) 1번 행 이후의 행의 모든 값 가져오기

 

x = torch.tensor(
    np.arange(15).reshape(3, 5))

print(x)
# tensor([[ 0,  1,  2,  3,  4],
#         [ 5,  6,  7,  8,  9],
#         [10, 11, 12, 13, 14]])


## -- slicing
x[1:]
# tensor([[ 5,  6,  7,  8,  9],
#         [10, 11, 12, 13, 14]])

 

 

(2-2) 1번 행 이후의 행 & 3번 열 이후의 열의 모든 값 가져오기

 

x[1:, 3:]
# tensor([[ 8,  9],
#         [13, 14]])

 

 

(2-3) 전체 행, 1번 열의 값 가져오기

 

x[:, 1]
# tensor([ 1,  6, 11])

 

 

(2-4) 1번 행, 전체 열의 값 가져오기

 

x[1, :]  # or equivalently x[1]
# tensor([5, 6, 7, 8, 9])

 

 

(2-5) 1번 행의, 1번과 4번 행의 값 가져오기

(생소한 코드예요. ^^;)

 

## tensor[1::3] ==> (1, None, None, 4)
x[1][1::3]
# tensor([6, 9])

 

 

 

(3) 1개 값만 가지는 파이토치 텐서에서 숫자 가져오기 : tensor.item()

 

## torch.tensor.item()
## : get a Python number from a tensor containing a single vlaue
y = torch.tensor([[5]])
print(y)
# tensor([[5]])

y.item()
# 5

 

 

만약 PyTorch tensor가 1개의 값(즉, 스칼라) 만을 가지는 것이 아니라 여러개의 값을 가지는 경우, tensor.item() 메소드를 사용하면 ValueError: only one element tensors can be converted to Python scalars 가 발생합니다. 

 

## ValueError
x.item()

# ValueError Traceback (most recent call last)
# <ipython-input-74-3396a1b2b617> in <module>
# ----> 1 x.item()

# ValueError: only one element tensors can be converted to Python scalars

 

 

 

(4) 파이토치 텐서 재구조화 (reshape)

 

NumPy의 reshape() 메소드와 동일하게 PyTorch tensor 도 reshape() 메소드를 이용해서 형태(shape)를 재구조화할 수 있습니다. 

 

torch.tensor([[0, 1, 2, 3, 4, 5]])
# tensor([[0, 1, 2, 3, 4, 5]])


## -- reshape
torch.tensor([[0, 1, 2, 3, 4, 5]]).reshape(2, 3)
# tensor([[0, 1, 2],
#         [3, 4, 5]])

 

 

 

이번 포스팅이 많은 도움이 되었기를 바랍니다. 

행복한 데이터 과학자 되세요!  :-)

 

728x90
반응형
Posted by Rfriend
,

지난 포스팅에서는 R data.table에서 := 를 사용한 참조에 의한 얕은 복사(shallow copy)의 부작용과 copy() 함수를 사용한 깊은 복사(deep copy)에 대하여 알아보았습니다. 


이번 포스팅에서는 R data.table 에서 melt() 와 dcast() 함수를 사용해서 효율적으로 재구조화 (efficient reshaping of R data.table) 하는 방법을 소개하겠습니다. 


R reshape 패키지의 melt(), cast() 함수와 유사하므로 활용법에 있어서 어렵거나 특별한 것은 없습니다. 다만 R data.table은 재구조화의 과정이 내부적으로 전부 C 언어로 수행되므로 매우 빠르고 또 메모리 효율적입니다. 


(1) data.table 을 녹여서 넓은 자료구조를 길게 (wide to long) 재구조화 해주는 melt() 함수

(2) data.table 을 주조하여 긴 자료구조를 넓게 (long to wide) 재구조화 해주는 dcast() 함수





  (1) melt() : data.table 을 녹여서 넓은 자료구조를 길게 (wide to long) 재구조화


data.table 패키지를 불러오고, MASS 패키지에 내장되어 있는 Cars93 데이터프레임에서 행 1~5번 까지, 그리고 6개 칼럼만 선별해와서 예제로 사용할 간단한 data.table을 만들어보겠습니다. 



library(data.table)

library(MASS)


DT <- data.table(Cars93[1:5, c("Model", "Type", "DriveTrain", "Length", "Width", "Weight")])

print(DT)

# Model    Type DriveTrain Length Width Weight

# 1: Integra   Small      Front    177    68   2705

# 2:  Legend Midsize      Front    195    71   3560

# 3:      90 Compact      Front    180    67   3375

# 4:     100 Midsize      Front    193    70   3405

# 5:    535i Midsize       Rear    186    69   3640




이제 위에서 만든 data.table DT를 melt() 함수를 사용하여 ID(id.vars) 변수는 모델("Model"), 차종("Type"), 동력전달장치("DriveTrain") 의 3개 변수로 하고, 측정값 변수(measure.vars)로는 길이("Length"), 폭("Width"), 무게("Weight")의 3개 변수를 variable, value 의 2개 변수로 녹여서(melting) 재구조화함으로써, 옆으로 넓은 형태를 세로로 긴 형태 (wide to long)의 data.table로 재구조화 해보겠습니다. 



## -- 1. Melting data.tables (wide to long)

DT_melt_1 <- melt(DT, 

                  id.vars = c("Model", "Type", "DriveTrain"), 

                  measure.vars = c("Length", "Width", "Weight"))


## By default, the molten columns are automatically named 'variable' and 'value'.

print(DT_melt_1)

# Model    Type DriveTrain variable value

# 1: Integra   Small      Front   Length   177

# 2:  Legend Midsize      Front   Length   195

# 3:      90 Compact      Front   Length   180

# 4:     100 Midsize      Front   Length   193

# 5:    535i Midsize       Rear   Length   186

# 6: Integra   Small      Front    Width    68

# 7:  Legend Midsize      Front    Width    71

# 8:      90 Compact      Front    Width    67

# 9:     100 Midsize      Front    Width    70

# 10:    535i Midsize       Rear    Width    69

# 11: Integra   Small      Front   Weight  2705

# 12:  Legend Midsize      Front   Weight  3560

# 13:      90 Compact      Front   Weight  3375

# 14:     100 Midsize      Front   Weight  3405

# 15:    535i Midsize       Rear   Weight  3640


str(DT_melt_1)

# Classes 'data.table' and 'data.frame': 15 obs. of  5 variables:

#   $ Model     : Factor w/ 93 levels "100","190E","240",..: 49 56 9 1 6 49 56 9 1 6 ...

# $ Type      : Factor w/ 6 levels "Compact","Large",..: 4 3 1 3 3 4 3 1 3 3 ...

# $ DriveTrain: Factor w/ 3 levels "4WD","Front",..: 2 2 2 2 3 2 2 2 2 3 ...

# $ variable  : Factor w/ 3 levels "Length","Width",..: 1 1 1 1 1 2 2 2 2 2 ...

# $ value     : int  177 195 180 193 186 68 71 67 70 69 ...

# - attr(*, ".internal.selfref")=<externalptr>




위의 str()함수로 각 변수의 데이터 형태를 보면 "variable" 변수는 요인형(Factor) 입니다. melt() 함수로 재구조화 시 "variable" 칼럼의 기본 설정값은 요인형(Factor) 인데요, 만약 요인형 말고 문자형(charactor) 으로 하고 싶다면 variable.factor = FALSE 로 매개변수를 설정해주면 됩니다. 



## By default, 'variable' column is of type factor. 

## Set variable.factor argument to FALSE if you like to return a character vector. 

DT_melt_2 <- melt(DT, 

                  id.vars = c("Model", "Type", "DriveTrain"), 

                  measure.vars = c("Length", "Width", "Weight"), 

                  variable.factor = FALSE)


str(DT_melt_2)

# Classes 'data.table' and 'data.frame': 15 obs. of  5 variables:

#   $ Model     : Factor w/ 93 levels "100","190E","240",..: 49 56 9 1 6 49 56 9 1 6 ...

# $ Type      : Factor w/ 6 levels "Compact","Large",..: 4 3 1 3 3 4 3 1 3 3 ...

# $ DriveTrain: Factor w/ 3 levels "4WD","Front",..: 2 2 2 2 3 2 2 2 2 3 ...

# $ variable  : chr  "Length" "Length" "Length" "Length" ...  # <--- charactr vector

# $ value     : int  177 195 180 193 186 68 71 67 70 69 ...

# - attr(*, ".internal.selfref")=<externalptr>




만약 녹여서(melting) 길게(wide to long) 재구조화한 후의 "variable", "value" 변수 이름을 사용자가 지정해서 다른 이름으로 부여를 하고 싶다면 variable.name = "new_variable_name", value.name = "new_value_name" 처럼 매개변수에 새로운 칼럼 이름을 부여해주면 됩니다. 



## Name the 'variable' and 'value' columns to 'measure' and 'val' respectively.

DT_melt_3 <- melt(DT, 

                  id.vars = c("Model", "Type", "DriveTrain"), 

                  measures.vars = c("Length", "Width", "Weight"), 

                  variable.name = "measure"

                  value.name = "val")


head(DT_melt_3)

# Model    Type DriveTrain measure val

# 1: Integra   Small      Front  Length 177

# 2:  Legend Midsize      Front  Length 195

# 3:      90 Compact      Front  Length 180

# 4:     100 Midsize      Front  Length 193

# 5:    535i Midsize       Rear  Length 186

# 6: Integra   Small      Front   Width  68





  (2) dcast() : data.table 을 주조하여 긴 자료구조를 넓게 (long to wide) 재구조화


위의 (1)번에서 세로로 길게 재구조화한 data.table을 원래의 옆으로 넓은 형태로 역으로 재구조화를 하고 싶으면 dcast() 함수를 사용하면 됩니다. 


dcast(DT, ID1 + ID2 + ID3 ~ variable) 처럼 함수 형태의 구문을 사용합니다. 



## -- 2. dcasting data.tables (long to wide)

## reverse operation of melting

## dcast uses formula interface.

dcast(DT_melt_1, Model + Type + DriveTrain ~ variable)

# Model    Type DriveTrain Length Width Weight

# 1:     100 Midsize      Front    193    70   3405

# 2:    535i Midsize       Rear    186    69   3640

# 3:      90 Compact      Front    180    67   3375

# 4: Integra   Small      Front    177    68   2705

# 5:  Legend Midsize      Front    195    71   3560




만약 위의 (1)번에서 "variable"과 "value" 칼럼이름을 사용자가 지정해서 melt()를 수행했다면 dcast() 를 하여 역으로 넓게 재구조화하려고 할 때 사용자가 지정한 변수(variable)와 값(value)의 칼럼 이름을 사용해주면 됩니다. 


위의 (1-3) 예에서 만든 DT_melt_3 이름의 data.table을 dcast()로 재구조화하려면 

dcast(DT_melt_3, Model + Type + DriveTrain ~ measure, value.var = "val"

처럼 위 (1-3)에서 지정했던 변수(variable) 이름인 'measure', 값(value) 이름인 value.var = "val" 을 써주면 됩니다. 



## 'value.var' denotes the column to be filled in with while casting to wide format. 

dcast(DT_melt_3, Model + Type + DriveTrain ~ measure

      value.var = "val")

# Model    Type DriveTrain Length Width Weight

# 1:     100 Midsize      Front    193    70   3405

# 2:    535i Midsize       Rear    186    69   3640

# 3:      90 Compact      Front    180    67   3375

# 4: Integra   Small      Front    177    68   2705

# 5:  Legend Midsize      Front    195    71   3560

 



dcast() 함수에 집계함수(aggregation function)를 사용하여 ID 그룹별로 요약통계량을 계산한 결과를 재구조화하여 반환할 수도 있습니다.


위의 (1)에서 data.table을 길게 녹여서 재구조화했던 DT_melt_1에 대해서 차종(Type)을 기준으로 녹여서 만든 변수(variable)에 대해 평균(fun.aggregate = mean)을 집계하여 역으로 옆으로 넓게 재구조화한 data.table을 반환해보겠스니다. 



## You can pass a function to aggregate by in dcast with the argument 'fun.aggregate. 

dcast(DT_melt_1, Type ~ variable, fun.aggregate = mean)

# Type   Length Width Weight

# 1: Compact 180.0000    67   3375

# 2: Midsize 191.3333    70   3535

# 3:   Small 177.0000    68   2705




fun.aggregate 는 fun.agg 로 줄여서 쓸 수 있으며, fun.agg 뒤에는 function(x) 로 해서 어떠한 R 함수도 써줄 수 있습니다. 아래 예에서는 x가 결측값인지(1) 아닌지(0) 여부에 대해서 합(sum)을 구하는 집계함수로서 fun.agg = function(x) sum(!is.na(x)) 를 써주었습니다. (즉, 결측값이 아닌 행의 개수)


그리고 subset 매개변수를 사용하면 dcast()의 대상이 되는 data.table에서 특정 조건을 만족하는 부분집합만 필터링해와서 dcast() 재구조화를 할 수도 있습니다. 



## 'fun.agg' is the same with 'fun.aggregate'

## subset: Specified if casting should be done on a subset of the data.

dcast(DT_melt_1, Type ~ variable, 

      fun.agg = function(x) sum(!is.na(x))

      subset = .(variable != "Length"))

# Type Width Weight

# 1: Compact     1      1

# 2: Midsize     3      3

# 3:   Small     1      1



[Reference]

* R data.table vignette
: https://cran.r-project.org/web/packages/data.table/vignettes/datatable-reshape.html



다음번 포스팅에서는 특정 패턴이 있는 data.table의 러개 칼럼을 동시에 녹이고 주조하여 재구조화하는 방법을 소개하겠습니다. (https://rfriend.tistory.com/576)



이번 포스팅이 많은 도움이 되었기를 바랍니다. 

행복한 데이터 과학자 되세요!



728x90
반응형
Posted by Rfriend
,

이전 포스팅에서는 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
,