Szybka konkatenacja danych.kolumny tabeli w jedną kolumnę łańcuchową

Biorąc pod uwagę dowolną listę nazw kolumn w data.table, chcę połączyć zawartość tych kolumn w pojedynczy łańcuch przechowywany w nowej kolumnie. Kolumny, które muszę konkatenować, nie zawsze są takie same, więc muszę wygenerować wyrażenie, aby to zrobić w locie.

Mam podejrzenie, że w ten sposób używam eval(parse(...)) wywołanie może zostać zastąpione czymś nieco bardziej eleganckim, ale metoda poniżej jest najszybsza, jaką udało mi się uzyskać do tej pory.

Z 10 milion wierszy, to trwa około 21.7 sekund na tej przykładowej danych (Baza R paste0 trwa nieco dłużej -- 23.6 sekund) . Moje rzeczywiste dane mają 18-20 kolumn konkatenowanych i do 100 milionów wierszy, więc spowolnienie staje się trochę bardziej niepraktyczne.

Jakieś pomysły, żeby to przyspieszyć?


Obecne metody

library(data.table)
library(stringi)

RowCount <- 1e7
DT <- data.table(x = "foo",
                 y = "bar",
                 a = sample.int(9, RowCount, TRUE),
                 b = sample.int(9, RowCount, TRUE),
                 c = sample.int(9, RowCount, TRUE),
                 d = sample.int(9, RowCount, TRUE),
                 e = sample.int(9, RowCount, TRUE),
                 f = sample.int(9, RowCount, TRUE))

## Generate an expression to paste an arbitrary list of columns together
ConcatCols <- c("x","a","b","c","d","e","f","y")
PasteStatement <- stri_c('stri_c(',stri_c(ConcatCols,collapse = ","),')')
print(PasteStatement)

Daje

[1] "stri_c(x,a,b,c,d,e,f,y)"

Który jest następnie używany do łączenia kolumn z następującymi wyrażenie:

DT[,State := eval(parse(text = PasteStatement))]

Próbka wyjścia:

     x   y a b c d e f        State
1: foo bar 4 8 3 6 9 2 foo483692bar
2: foo bar 8 4 8 7 8 4 foo848784bar
3: foo bar 2 6 2 4 3 5 foo262435bar
4: foo bar 2 4 2 4 9 9 foo242499bar
5: foo bar 5 9 8 7 2 7 foo598727bar

Wyniki Profilowania

Wykres Płomienia Dane


Update 1: fread, fwrite, oraz sed

Podążając za sugestią @ Gregor, spróbowałem użyć sed, aby wykonać konkatenację na dysku. Dzięki data.table ' s blazing fast fread and fwrite functions, byłem w stanie wypisać kolumny na dysk, wyeliminować przecinki za pomocą sed ,a następnie odczytać z powrotem w post-przetworzonym wyjściu w o 18.3 sekund -- nie dość szybko, aby dokonać przełącznika, ale ciekawe tangent mimo wszystko!

ConcatCols <- c("x","a","b","c","d","e","f","y")
fwrite(DT[,..ConcatCols],"/home/xxx/DT.csv")
system("sed 's/,//g' /home/xxx/DT.csv > /home/xxx/DT_Post.csv ")
Post <- fread("/home/xxx/DT_Post.csv")
DT[,State := Post[[1]]]
W przeciwieństwie do innych systemów, w których nie można używać profvis, jest on niewidoczny dla R profilera.]}
  • data.table::fwrite() - 0.5 sekundy
  • sed - 14,8 sekundy
  • data.table::fread() - 3.0 sekundy
  • := - 0.0 sekundy

Jeśli nic innego, jest to świadectwo rozległej pracy danych.autorzy tabeli na optymalizacja wydajności dysków IO. (Używam wersji rozwojowej 1.10.5, która dodaje wielowątkowość do fread, fwrite jest wielowątkowy od jakiegoś czasu).

Jedno zastrzeżenie: jeśli istnieje obejście zapisu pliku za pomocą fwrite i pustego separatora, zgodnie z sugestią @Gregor w innym komentarzu poniżej, to ta metoda może być prawdopodobnie skrócona do ~3,5 sekundy!

Aktualizacja tej stycznej: rozwidlone dane.tabela i skomentował linię wymagającą separator większy niż długość 0, zamiast tego masz jakieś spacje? Po spowodowaniu kilku segfaultów próbujących zadzierać z wewnętrznymi C, umieściłem ten na razie w lodzie. Idealne rozwiÄ ... zanie nie wymagaĹ 'oby zapisu na dysk i zachowaĹ' oby wszystko w pamiÄ ™ ci.


Update 2: sprintf for Integer Specific Cases

Druga aktualizacja tutaj: podczas gdy dodałem ciągi w moim oryginalnym przykładzie użycia, mój rzeczywisty przypadek użycia łączy wyłącznie liczbę całkowitą wartości (które zawsze można przyjąć jako inne niż null na podstawie kroków czyszczenia).

Ponieważ przypadek użycia jest bardzo specyficzny i różni się od oryginalnego pytania, Nie będę bezpośrednio porównywał czasów do wcześniej opublikowanych. Jednak jednym z przykładów jest to, że chociaż stringi ładnie obsługuje wiele formatów kodowania znaków, mieszane typy wektorowe bez konieczności ich określania, i robi kilka błędów obsługi po wyjęciu z pudełka, to dodaje trochę czasu (co prawdopodobnie jest tego warte dla większości przypadki) .

Używając podstawowej funkcji R sprintf i informując z góry, że wszystkie wejścia będą liczbami całkowitymi, możemy zmniejszyć o około 30% Czas wykonania dla 5 milionów wierszy z 18 liczbami całkowitymi do obliczenia. (20,3 sekundy zamiast 28,9)

library(data.table)
library(stringi)
RowCount <- 5e6
DT <- data.table(x = "foo",
                 y = "bar",
                 a = sample.int(9, RowCount, TRUE),
                 b = sample.int(9, RowCount, TRUE),
                 c = sample.int(9, RowCount, TRUE),
                 d = sample.int(9, RowCount, TRUE),
                 e = sample.int(9, RowCount, TRUE),
                 f = sample.int(9, RowCount, TRUE))

## Generate an expression to paste an arbitrary list of columns together
ConcatCols <- list("a","b","c","d","e","f")
## Do it 3x as many times
ConcatCols <- c(ConcatCols,ConcatCols,ConcatCols)

## Using stringi::stri_c ---------------------------------------------------
stri_joinStatement <- stri_c('stri_join(',stri_c(ConcatCols,collapse = ","),', sep="", collapse=NULL, ignore_null=TRUE)')
DT[, State := eval(parse(text = stri_joinStatement))]

## Using sprintf -----------------------------------------------------------
sprintfStatement <- stri_c("sprintf('",stri_flatten(rep("%i",length(ConcatCols))),"', ",stri_c(ConcatCols,collapse = ","),")")
DT[,State_sprintf_i := eval(parse(text = sprintfStatement))]

Wygenerowane instrukcje są następujące:

> cat(stri_joinStatement)
stri_join(a,b,c,d,e,f,a,b,c,d,e,f,a,b,c,d,e,f, sep="", collapse=NULL, ignore_null=TRUE)
> cat(sprintfStatement)
sprintf('%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i%i', a,b,c,d,e,f,a,b,c,d,e,f,a,b,c,d,e,f)

sprintf


Aktualizacja 3: R nie musi być powolna.

Na podstawie odpowiedzi @ Martin Modrák, dodałem razem jeden trick pony pakiet oparty na niektórych data.table wewnętrzne wyspecjalizowane dla wyspecjalizowanej" jednocyfrowej liczby całkowitej " przypadku: fastConcat. Nie szukaj go na CRAN, ale możesz go używać na własne ryzyko, instalując z github repo, msummersgill/fastConcat.)

To prawdopodobnie może być poprawione znacznie dalej przez kogoś, kto rozumie c lepiej, ale na razie działa to tak samo jak w aktualizacji 2 w 2.5 sekund -- około 8X szybciej niż sprintf() i 11,5 x szybciej niż metoda stringi::stri_c(), której używałem pierwotnie.

Dla mnie to podkreśla ogromną szansę na poprawę wydajności niektórych najprostszych operacji w R podobnie jak podstawowa konkatenacja strunowo-wektorowa Z lepiej dostrojonym c. Myślę, że ludzie tacy jak @ Matt Dowle widzieli to od lat. gdyby tylko miał czas na ponowne napisanie wszystkich R, a nie tylko data.rama.

fastConcat


Author: smci, 2018-01-12

3 answers

C na ratunek!

Kradzież kodu z danych.tabela możemy napisać funkcję C, która działa o wiele szybciej (i może być równoległa, aby być jeszcze szybsza).

Najpierw upewnij się, że masz działający łańcuch narzędzi C++ z:

library(inline)

fx <- inline::cfunction( signature(x = "integer", y = "numeric" ) , '
    return ScalarReal( INTEGER(x)[0] * REAL(y)[0] ) ;
' )
fx( 2L, 5 ) #Should return 10

To powinno zadziałać (zakładając, że dane są tylko liczbami całkowitymi, ale kod można rozszerzyć na inne typy):

library(inline)
library(data.table)
library(stringi)

header <- "

//Taken from https://github.com/Rdatatable/data.table/blob/master/src/fwrite.c
static inline void reverse(char *upp, char *low)
{
  upp--;
  while (upp>low) {
  char tmp = *upp;
  *upp = *low;
  *low = tmp;
  upp--;
  low++;
  }
}

void writeInt32(int *col, size_t row, char **pch)
{
  char *ch = *pch;
  int x = col[row];
  if (x == INT_MIN) {
  *ch++ = 'N';
  *ch++ = 'A';
  } else {
  if (x<0) { *ch++ = '-'; x=-x; }
  // Avoid log() for speed. Write backwards then reverse when we know how long.
  char *low = ch;
  do { *ch++ = '0'+x%10; x/=10; } while (x>0);
  reverse(ch, low);
  }
  *pch = ch;
}

//end of copied code 

"



 worker_fun <- inline::cfunction( signature(x = "list", preallocated_target = "character", columns = "integer", start_row = "integer", end_row = "integer"), includes = header , "
  const size_t _start_row = INTEGER(start_row)[0] - 1;
  const size_t _end_row = INTEGER(end_row)[0];

  const int max_out_len = 256 * 256; //max length of the final string
  char buffer[max_out_len];
  const size_t num_elements = _end_row - _start_row;
  const size_t num_columns = LENGTH(columns);
  const int * _columns = INTEGER(columns);

  for(size_t i = _start_row; i < _end_row; ++i) {
    char *buf_pos = buffer;
    for(size_t c = 0; c < num_columns; ++c) {
      if(c > 0) {
        buf_pos[0] = ',';
        ++buf_pos;
      }
      writeInt32(INTEGER(VECTOR_ELT(x, _columns[c] - 1)), i, &buf_pos);
    }
    SET_STRING_ELT(preallocated_target,i, mkCharLen(buffer, buf_pos - buffer));
  }
return preallocated_target;
" )

#Test with the same data

RowCount <- 5e6
DT <- data.table(x = "foo",
                 y = "bar",
                 a = sample.int(9, RowCount, TRUE),
                 b = sample.int(9, RowCount, TRUE),
                 c = sample.int(9, RowCount, TRUE),
                 d = sample.int(9, RowCount, TRUE),
                 e = sample.int(9, RowCount, TRUE),
                 f = sample.int(9, RowCount, TRUE))

## Generate an expression to paste an arbitrary list of columns together
ConcatCols <- list("a","b","c","d","e","f")
## Do it 3x as many times
ConcatCols <- c(ConcatCols,ConcatCols,ConcatCols)


ptm <- proc.time()
preallocated_target <- character(RowCount)
column_indices <- sapply(ConcatCols, FUN = function(x) { which(colnames(DT) == x )})
x <- worker_fun(DT, preallocated_target, column_indices, as.integer(1), as.integer(RowCount))
DT[, State := preallocated_target]
proc.time() - ptm

Podczas gdy twój (tylko integer) przykład działa w około 20s na moim komputerze, to działa w ~5s i może być łatwo / align = "left" /

Kilka rzeczy do zapamiętania:

  • kod nie jest gotowy do produkcji - na wejściach funkcji należy wykonać wiele testów rozsądności (zwłaszcza sprawdzenie, czy wszystkie kolumny są tej samej długości, sprawdzenie typów kolumn, preallocated_target size itp.)
  • funkcja umieszcza swoje wyjście w prealokowanym wektorze znaków, jest to niestandardowe i brzydkie (r zwykle nie ma semantyki pass-by-reference), ale pozwala na równoległe (patrz poniżej).
  • The ostatnie dwa parametry to wiersze start i end, które mają być przetworzone, po raz kolejny jest to dla paralelizacji
  • funkcja przyjmuje indeksy kolumn, a nie nazwy kolumn. Wszystkie kolumny muszą być typu integer.
  • z wyjątkiem danych wejściowych.table and preallocated_target wejścia muszą być liczbami całkowitymi
  • czas kompilacji funkcji nie jest wliczony w cenę (ponieważ powinieneś ją wcześniej skompilować-może nawet zrobić pakiet)

Paralelizacja

EDIT: poniższe podejście faktycznie zawiedzie ze względu na sposób działania clusterExport i R string storage. Paralelizacja musi więc być wykonana również w C, podobnie jak w przypadku danych.stolik.

Ponieważ nie można przekazać funkcji kompilowanych w linii między procesami R, paralelizacja wymaga więcej pracy. Aby móc korzystać z powyższej funkcji równolegle, musisz albo skompilować ją osobno z R kompilator i uĺźywaj dyn.load lub zawijaj go w pakiet lub uĺźywaj backendu forkingowego dla parallel (nie mam takiego, forking dziaĹ ' a tylko na Uniksie).

Bieganie równolegle wyglądałoby wtedy jak (nie testowane):

no_cores <- detectCores()

# Initiate cluster
cl <- makeCluster(no_cores)

#Preallocated target and prepare params
num_elements <- length(DT[[1]])
preallocated_target <- character(num_elements)
block_size <- 4096 #No of rows processed at once. Adjust for best performance
column_indices <- sapply(ConcatCols, FUN = function(x) { which(colnames(DT) == x )})

num_blocks <- ceiling(num_elements / block_size)

clusterExport(cl, 
   c("DT","preallocated_target","column_indices","num_elements", "block_size"))
clusterEvalQ(cl, <CODE TO LOAD THE NATIVE FUNCTION HERE>)

parLapply(cl, 1:num_blocks ,
          function(block_id)
          {
            throw_away <- 
              worker_fun(DT, preallocated_target, columns, 
              (block_id - 1) * block_size + 1, min(num_elements, block_id * block_size - 1))
            return(NULL)
          })



stopCluster(cl)
 12
Author: Martin Modrák,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-01-22 08:38:45

Nie wiem, jak reprezentatywne są dane przykładowe dla rzeczywistych danych, ale w przypadku próbek danych można osiągnąć znaczną poprawę wydajności, łącząc tylko jedną unikalną kombinację ConcatCols raz zamiast wiele razy.

Oznacza to, że dla przykładowych danych, Będziesz patrzył na ~ 500K konkatenacji vs 10 milionów, jeśli zrobisz wszystkie duplikaty zbyt.

Zobacz następujący kod i przykład pomiaru czasu:

system.time({
  setkeyv(DT, ConcatCols)
  DTunique <- unique(DT[, ConcatCols, with=FALSE], by = key(DT))
  DTunique[, State :=  do.call(paste, c(DTunique, sep = ""))]
  DT[DTunique, State := i.State, on = ConcatCols]
})
#       user      system     elapsed 
#      7.448       0.462       4.618 

Około połowy czasu spędza się na część setkey. W przypadku, gdy dane są już kluczowane, czas jest jeszcze krótszy do nieco ponad 2 sekund.

setkeyv(DT, ConcatCols)
system.time({
  DTunique <- unique(DT[, ConcatCols, with=FALSE], by = key(DT))
  DTunique[, State :=  do.call(paste, c(DTunique, sep = ""))]
  DT[DTunique, State := i.State, on = ConcatCols]
})
#       user      system     elapsed 
#      2.526       0.280       2.181 
 7
Author: docendo discimus,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-01-19 14:12:02

Używa {[1] } z pakietu tidyr. Może nie jest najszybszy, ale prawdopodobnie jest szybszy niż ręcznie kodowany kod R.

library(tidyr)
system.time(
  DNew <- DT %>% unite(State, ConcatCols, sep = "", remove = FALSE)
)
# user  system elapsed 
# 14.974   0.183  15.343 

DNew[1:10]
# State   x   y a b c d e f
# 1: foo211621bar foo bar 2 1 1 6 2 1
# 2: foo532735bar foo bar 5 3 2 7 3 5
# 3: foo965776bar foo bar 9 6 5 7 7 6
# 4: foo221284bar foo bar 2 2 1 2 8 4
# 5: foo485976bar foo bar 4 8 5 9 7 6
# 6: foo566778bar foo bar 5 6 6 7 7 8
# 7: foo892636bar foo bar 8 9 2 6 3 6
# 8: foo836672bar foo bar 8 3 6 6 7 2
# 9: foo963926bar foo bar 9 6 3 9 2 6
# 10: foo385216bar foo bar 3 8 5 2 1 6
 0
Author: Andrew Lavers,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-01-22 23:16:00