R Language
Hashmapy

Środowiska jako mapy skrótów

Uwaga: w kolejnych fragmentach terminy mapa skrótów i tabela skrótów są używane zamiennie i odnoszą się do tej samej koncepcji , a mianowicie struktury danych zapewniającej skuteczne wyszukiwanie klucza za pomocą wewnętrznej funkcji skrótu.

Wprowadzenie

Chociaż R nie zapewnia natywnej struktury tabeli skrótów, podobną funkcjonalność można uzyskać, wykorzystując fakt, że obiekt environment zwrócony z new.env (domyślnie) zapewnia wyszukiwanie new.env klucza. Poniższe dwie instrukcje są równoważne, ponieważ parametr hash domyślną wartość TRUE :

H <- new.env(hash = TRUE)
H <- new.env() 

Dodatkowo można sprecyzować, że do wewnętrznej tabeli skrótów przypisany jest określony rozmiar za pomocą parametru size , który ma domyślną wartość 29. Podobnie jak wszystkie inne obiekty R, environment zarządza własną pamięcią i w razie potrzeby zwiększy pojemność , więc chociaż nie jest wymagane żądanie wartości domyślnej dla size , może to być niewielka przewaga wydajnościowa, jeśli obiekt będzie (ostatecznie) zawierał bardzo dużą liczbę elementów. Warto zauważyć, że przydzielenie dodatkowej przestrzeni według size samo w sobie nie powoduje powstania obiektu o większej powierzchni pamięci:

object.size(new.env())
# 56 bytes

object.size(new.env(size = 10e4))
# 56 bytes 

Wprowadzenie

Wstawianie elementów można wykonać przy użyciu jednej z metod [[<- lub $<- przewidzianych dla klasy environment , ale nie przy użyciu przypisania „pojedynczego nawiasu” ( [<- ) :

H <- new.env()

H[["key"]] <- rnorm(1)

key2 <- "xyz"
H[[key2]] <- data.frame(x = 1:3, y = letters[1:3])

H$another_key <- matrix(rbinom(9, 1, 0.5) > 0, nrow = 3)

H["error"] <- 42
#Error in H["error"] <- 42 : 
#  object of type 'environment' is not subsettable 

Podobnie jak inne aspekty R, pierwsza metoda ( object[[key]] <- value ) jest ogólnie preferowana niż druga ( object$key <- value ), ponieważ w pierwszym przypadku można użyć zmiennej zamiast wartości dosłownej (np. key2 w powyższym przykładzie).

Jak to zwykle ma miejsce w przypadku implementacji mapy skrótu, obiekt environment nie będzie przechowywać duplikatów kluczy. Próba wstawienia pary klucz-wartość dla istniejącego klucza zastąpi wcześniej zapisaną wartość:

H[["key3"]] <- "original value"

H[["key3"]] <- "new value"

H[["key3"]]
#[1] "new value"

Wyszukiwanie klucza

Podobnie do elementów można uzyskać dostęp za pomocą [[ lub $ , ale nie za pomocą [ :

H[["key"]]
#[1] 1.630631
 
H[[key2]]   ## assuming key2 <- "xyz"
#   x y
# 1 1 a
# 2 2 b
# 3 3 c

H$another_key
#       [,1]  [,2]  [,3]
# [1,]  TRUE  TRUE  TRUE
# [2,] FALSE FALSE FALSE
# [3,]  TRUE  TRUE  TRUE

H[1]
#Error in H[1] : object of type 'environment' is not subsettable

Sprawdzanie mapy skrótów

Będąc zwykłym environment , mapę skrótu można sprawdzić typowymi metodami:

names(H)
#[1] "another_key" "xyz"         "key"         "key3"       

ls(H)
#[1] "another_key" "key"         "key3"        "xyz"        
 
str(H)
#<environment: 0x7828228> 
 
ls.str(H)
# another_key :  logi [1:3, 1:3] TRUE FALSE TRUE TRUE FALSE TRUE ...
# key :  num 1.63
# key3 :  chr "new value"
# xyz : 'data.frame':    3 obs. of  2 variables:
#  $ x: int  1 2 3
#  $ y: chr  "a" "b" "c"

Elementy można usunąć za pomocą rm :

rm(list = c("key", "key3"), envir = H)

ls.str(H)
# another_key :  logi [1:3, 1:3] TRUE FALSE TRUE TRUE FALSE TRUE ...
# xyz : 'data.frame':    3 obs. of  2 variables:
#  $ x: int  1 2 3
#  $ y: chr  "a" "b" "c"

Elastyczność

Jedną z głównych zalet używania obiektów environment jako tabel skrótów jest ich zdolność do przechowywania praktycznie dowolnego typu obiektu jako wartości, nawet innych environment :

H2 <- new.env()

H2[["a"]] <- LETTERS
H2[["b"]] <- as.list(x = 1:5, y = matrix(rnorm(10), 2))
H2[["c"]] <- head(mtcars, 3)
H2[["d"]] <- Sys.Date()
H2[["e"]] <- Sys.time()
H2[["f"]] <- (function() {
    H3 <- new.env()
    for (i in seq_along(names(H2))) {
        H3[[names(H2)[i]]] <- H2[[names(H2)[i]]]
    }
    H3
})()

ls.str(H2)
# a :  chr [1:26] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" ...
# b : List of 5
#  $ : int 1
#  $ : int 2
#  $ : int 3
#  $ : int 4
#  $ : int 5
# c : 'data.frame':    3 obs. of  11 variables:
#  $ mpg : num  21 21 22.8
#  $ cyl : num  6 6 4
#  $ disp: num  160 160 108
#  $ hp  : num  110 110 93
#  $ drat: num  3.9 3.9 3.85
#  $ wt  : num  2.62 2.88 2.32
#  $ qsec: num  16.5 17 18.6
#  $ vs  : num  0 0 1
#  $ am  : num  1 1 1
#  $ gear: num  4 4 4
#  $ carb: num  4 4 1
# d :  Date[1:1], format: "2016-08-03"
# e :  POSIXct[1:1], format: "2016-08-03 19:25:14"
# f : <environment: 0x91a7cb8> 

ls.str(H2$f)
# a :  chr [1:26] "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" ...
# b : List of 5
#  $ : int 1
#  $ : int 2
#  $ : int 3
#  $ : int 4
#  $ : int 5
# c : 'data.frame':    3 obs. of  11 variables:
#  $ mpg : num  21 21 22.8
#  $ cyl : num  6 6 4
#  $ disp: num  160 160 108
#  $ hp  : num  110 110 93
#  $ drat: num  3.9 3.9 3.85
#  $ wt  : num  2.62 2.88 2.32
#  $ qsec: num  16.5 17 18.6
#  $ vs  : num  0 0 1
#  $ am  : num  1 1 1
#  $ gear: num  4 4 4
#  $ carb: num  4 4 1
# d :  Date[1:1], format: "2016-08-03"
# e :  POSIXct[1:1], format: "2016-08-03 19:25:14"

Ograniczenia

Jednym z głównych ograniczeń używania obiektów environment jako map skrótu jest to, że w przeciwieństwie do wielu aspektów R, wektoryzacja nie jest obsługiwana dla wyszukiwania / wstawiania elementów:

names(H2)
#[1] "a" "b" "c" "d" "e" "f"

H2[[c("a", "b")]]
#Error in H2[[c("a", "b")]] : 
#  wrong arguments for subsetting an environment
 
Keys <- c("a", "b")
H2[[Keys]]
#Error in H2[[Keys]] : wrong arguments for subsetting an environment

W zależności od charakteru danych przechowywanych w obiekcie może być możliwe użycie vapply lub list2env do przypisania wielu elementów jednocześnie:

E1 <- new.env()
invisible({
    vapply(letters, function(x) {
        E1[[x]] <- rnorm(1)
        logical(0)
    }, FUN.VALUE = logical(0))
})

all.equal(sort(names(E1)), letters)
#[1] TRUE

Keys <- letters
E2 <- list2env(
    setNames(
        as.list(rnorm(26)),
        nm = Keys), 
    envir = NULL,
    hash = TRUE
)

all.equal(sort(names(E2)), letters)
#[1] TRUE

Żadna z powyższych nie jest szczególnie zwięzła, ale może być lepsza niż użycie pętli for itp., Gdy liczba par klucz-wartość jest duża.

pakiet: skrót

Pakiet skrótu oferuje strukturę skrótu w języku R. Jednak termin synchronizacji obu wstawek i odczytów jest niekorzystny w porównaniu do używania środowisk jako skrótu. Ta dokumentacja po prostu potwierdza jego istnienie i podaje przykładowy kod czasowy poniżej z wyżej wymienionych powodów. Nie ma zidentyfikowanego przypadku, w którym skrót jest właściwym rozwiązaniem w kodzie R.

Rozważać:

# Generic unique string generator
unique_strings <- function(n){
    string_i <- 1
    string_len <- 1
    ans <- character(n)
    chars <- c(letters,LETTERS)
    new_strings <- function(len,pfx){
    for(i in 1:length(chars)){
        if (len == 1){
        ans[string_i] <<- paste(pfx,chars[i],sep='')
        string_i <<- string_i + 1
        } else {
        new_strings(len-1,pfx=paste(pfx,chars[i],sep=''))
        }
        if (string_i > n) return ()
    }
    }
    while(string_i <= n){
    new_strings(string_len,'')
    string_len <- string_len + 1
    }
    sample(ans)
}

# Generate timings using an enviornment
timingsEnv <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    ht1 <- new.env(hash=TRUE)
    lapply(strings, function(s){ ht1[[s]] <<- 0L})
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (j in 1:i) ht1[[strings[j]]]==0L)[3]),
    type = c('1_hashedEnv')
    )
})

timingsHash <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    ht <- hash::hash()
    lapply(strings, function(s) ht[[s]] <<- 0L)
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (j in 1:i) ht[[strings[j]]]==0L)[3]),
    type = c('3_stringHash')
    )
})

pakiet: listenv

Mimo że package:listenv implementuje interfejs podobny do listy, jego wydajność w stosunku do środowisk do celów podobnych do haszowania jest niska przy pobieraniu haszowania . Jednak jeśli indeksy są liczbowe, pobieranie może być dość szybkie. Mają jednak inne zalety, np. Kompatybilność z package:future . Pokrycie tego pakietu w tym celu wykracza poza zakres bieżącego tematu. Jednak podany tutaj kod taktowania może być używany w połączeniu z przykładem dla pakietu: hash dla taktowania zapisu.

timingsListEnv <- plyr::adply(2^(10:15),.mar=1,.fun=function(i){
    strings <- unique_strings(i)
    le <- listenv::listenv()
    lapply(strings, function(s) le[[s]] <<- 0L)
    data.frame(
    size=c(i,i),
    seconds=c(
        system.time(for (k in 1:i) le[[k]]==0L)[3]),
    type = c('2_numericListEnv')
    )
})