Perché è in esecuzione “unico” più veloce su un frame di dati di una matrice in R?

Question

ho cominciato a credere che i frame di dati in possesso di alcun vantaggi rispetto matrici, tranne che per convenienza di notazione. Tuttavia, ho notato questa stranezza quando si esegue unique su matrici e frame di dati:. Sembra correre più veloce su un frame di dati

a   = matrix(sample(2,10^6,replace = TRUE), ncol = 10)
b   = as.data.frame(a)

system.time({
    u1 = unique(a)
})
 user  system elapsed
1.840   0.000   1.846


system.time({
    u2 = unique(b)
})
 user  system elapsed
0.380   0.000   0.379

I risultati di temporizzazione divergono ancora più sostanzialmente come aumenta il numero di righe. Quindi, ci sono due parti a questa domanda.

1. Perché questo è più lento per una matrice? Sembra più veloce per convertire in un frame di dati, unique correre, e poi convertire indietro.

2. C'è qualche motivo per non solo unique involucro in myUnique, che fa le conversioni in parte # 1?

---

Nota 1. Dato che una matrice è atomico, sembra che unique dovrebbe essere più veloce per una matrice, piuttosto che più lento. Essere in grado di iterare di dimensioni fisse, blocchi contigui di memoria dovrebbe essere generalmente più veloce di esecuzione blocchi sopra separati di liste collegate (suppongo che è come vengono implementati i frame di dati ...).

Nota 2. Come dimostrato dalla performance di data.table, in esecuzione unique su un frame di dati o di una matrice è un relativamente cattiva idea - vedere la risposta da Matthew Dowle ed i commenti per tempi relativi. Ho migrato un sacco di oggetti a tabelle di dati, e questo risultato è un altro motivo per farlo. Quindi, anche se gli utenti dovrebbero essere ben serviti ad adottare tabelle di dati, per motivi pedagogici / comunità Lascio aperta la questione per il momento per quanto riguarda la perché fa questo richiederà più tempo sugli oggetti della matrice. Le risposte di seguito l'indirizzo , dove va il tempo, e in quale altro modo possiamo ottenere prestazioni migliori (cioè tabelle di dati). La risposta a perché è a portata di mano - il codice può essere trovati tramite unique.data.frame e unique.matrix. :) Un inglese spiegazione di ciò che sta facendo e perché è tutto ciò che manca.

Answer 1

1. In questa implementazione, unique.matrix è uguale unique.array

   > identical(unique.array, unique.matrix)

   [1] TRUE

2. unique.array deve gestire array multidimensionali che richiede un'elaborazione aggiuntiva per ‘collasso’ le dimensioni extra (quelle chiamate aggiuntive al paste()) che non sono necessari nel caso 2-dimensionale. La sezione chiave del codice è:

   collapse <- (ndim > 1L) && (prod(dx[-MARGIN]) > 1L)

   temp <- if (collapse) apply(x, MARGIN, function(x) paste(x, collapse = "\r"))

3. unique.data.frame è ottimizzato per il caso 2D, unique.matrix non è. Potrebbe essere, come lei suggerisce, semplicemente non è nell'implementazione corrente.

Si noti che in tutti i casi (unica. {Array, matrice, data.table}) dove v'è più di una dimensione che è la rappresentazione stringa che viene confrontato per unicità. Per il galleggiamento numeri in virgola questi mezzi 15 cifre decimali così

NROW(unique(a <- matrix(rep(c(1, 1+4e-15), 2), nrow = 2)))

è 1 mentre

NROW(unique(a <- matrix(rep(c(1, 1+5e-15), 2), nrow = 2)))

e

NROW(unique(a <- matrix(rep(c(1, 1+4e-15), 1), nrow = 2)))

sono entrambi 2. Sei che unique è ciò che si vuole?

Answer 2

1. Non sono sicuro ma credo che a causa matrix è un vettore contigua, R copia nella vettori colonna prime (come un data.frame) perché paste ha bisogno di un elenco di vettori. Si noti che entrambi sono lento a causa sia l'uso paste.

2. Forse perché unique.data.table è già molte volte più veloce. Si prega di effettuare l'aggiornamento a v1.6.7 scaricandolo dal repository R-Forge perché ha la correzione per unique lei ha sollevato in questa domanda . data.table non usa paste fare unique.

a = matrix(sample(2,10^6,replace = TRUE), ncol = 10)
b = as.data.frame(a)
system.time(u1<-unique(a))
   user  system elapsed 
   2.98    0.00    2.99 
system.time(u2<-unique(b))
   user  system elapsed 
   0.99    0.00    0.99 
c = as.data.table(b)
system.time(u3<-unique(c))
   user  system elapsed 
   0.03    0.02    0.05  # 60 times faster than u1, 20 times faster than u2
identical(as.data.table(u2),u3)
[1] TRUE

Answer 3

Nel tentativo di rispondere alla mia domanda, in particolare parte 1, siamo in grado di vedere dove il tempo viene speso guardando i risultati di Rprof. Mi sono imbattuto di nuovo questo, con elementi 5M.

Ecco i risultati della prima operazione unica (per la matrice):

> summaryRprof("u1.txt")
$by.self
                     self.time self.pct total.time total.pct
"paste"                   5.70    52.58       5.96     54.98
"apply"                   2.70    24.91      10.68     98.52
"FUN"                     0.86     7.93       6.82     62.92
"lapply"                  0.82     7.56       1.00      9.23
"list"                    0.30     2.77       0.30      2.77
"!"                       0.14     1.29       0.14      1.29
"c"                       0.10     0.92       0.10      0.92
"unlist"                  0.08     0.74       1.08      9.96
"aperm.default"           0.06     0.55       0.06      0.55
"is.null"                 0.06     0.55       0.06      0.55
"duplicated.default"      0.02     0.18       0.02      0.18

$by.total
                     total.time total.pct self.time self.pct
"unique"                  10.84    100.00      0.00     0.00
"unique.matrix"           10.84    100.00      0.00     0.00
"apply"                   10.68     98.52      2.70    24.91
"FUN"                      6.82     62.92      0.86     7.93
"paste"                    5.96     54.98      5.70    52.58
"unlist"                   1.08      9.96      0.08     0.74
"lapply"                   1.00      9.23      0.82     7.56
"list"                     0.30      2.77      0.30     2.77
"!"                        0.14      1.29      0.14     1.29
"do.call"                  0.14      1.29      0.00     0.00
"c"                        0.10      0.92      0.10     0.92
"aperm.default"            0.06      0.55      0.06     0.55
"is.null"                  0.06      0.55      0.06     0.55
"aperm"                    0.06      0.55      0.00     0.00
"duplicated.default"       0.02      0.18      0.02     0.18

$sample.interval
[1] 0.02

$sampling.time
[1] 10.84

E per il frame di dati:

> summaryRprof("u2.txt")
$by.self
                     self.time self.pct total.time total.pct
"paste"                   1.72    94.51       1.72     94.51
"[.data.frame"            0.06     3.30       1.82    100.00
"duplicated.default"      0.04     2.20       0.04      2.20

$by.total
                        total.time total.pct self.time self.pct
"[.data.frame"                1.82    100.00      0.06     3.30
"["                           1.82    100.00      0.00     0.00
"unique"                      1.82    100.00      0.00     0.00
"unique.data.frame"           1.82    100.00      0.00     0.00
"duplicated"                  1.76     96.70      0.00     0.00
"duplicated.data.frame"       1.76     96.70      0.00     0.00
"paste"                       1.72     94.51      1.72    94.51
"do.call"                     1.72     94.51      0.00     0.00
"duplicated.default"          0.04      2.20      0.04     2.20

$sample.interval
[1] 0.02

$sampling.time
[1] 1.82

Quello che notiamo è che la versione di matrice spende un sacco di tempo su apply, paste e lapply. Al contrario, le piste versione trama di dati semplici duplicated.data.frame e la maggior parte del tempo è trascorso in paste, presumibilmente aggregando i risultati.

Anche se questo spiega , dove il tempo sta andando, ma non spiega perché questi hanno diverse implementazioni, né gli effetti del semplice passaggio da un tipo di oggetto a un altro.