Classificação mais rápida de dados

11

Preciso classificar um bedarquivo aleatoriamente 10000 vezes e ocupar as 1000 primeiras linhas de cada vez. Atualmente, estou usando o seguinte código:

for i in {1..100}; do
    for j in {1..100}; do
        sort -R myfile.bed_sorted | tail -n 1000 > myfile.bed.$i.$j.bed
    done
done

Demora quase 6 horas para fazer isso para cada arquivo. Eu tenho cerca de 150 deles para serem trabalhados. Existe uma solução mais rápida para isso?

Uma amostra dos dados (myfile.bed_sorted) que tenho:

    chr1    111763899   111766405   peak1424    1000    .   3224.030    -1  -1
    chr1    144533459   144534584   peak1537    998 .   3219.260    -1  -1
    chr8    42149384    42151246    peak30658   998 .   3217.620    -1  -1
    chr2    70369299    70370655    peak16886   996 .   3211.600    -1  -1
    chr8    11348914    11352994    peak30334   990 .   3194.180    -1  -1
    chr21   26828820    26830352    peak19503   988 .   3187.820    -1  -1
    chr16   68789901    68791150    peak11894   988 .   3187.360    -1  -1
    chr6    11458964    11462245    peak26362   983 .   3169.750    -1  -1
    chr1    235113793   235117308   peak2894    982 .   3166.000    -1  -1
    chr6    16419968    16422194    peak26522   979 .   3158.520    -1  -1
    chr6    315344  321339  peak26159   978 .   3156.320    -1  -1
    chr1    111756584   111759633   peak1421    964 .   3110.520    -1  -1
    chrX    12995098    12997685    peak33121   961 .   3100.000    -1  -1
    chr9    37408601    37410262    peak32066   961 .   3100.000    -1  -1
    chr9    132648603   132651523   peak32810   961 .   3100.000    -1  -1
    chr8    146103178   146104943   peak31706   961 .   3100.000    -1  -1
    chr8    135611963   135614649   peak31592   961 .   3100.000    -1  -1
    chr8    128312253   128315935   peak31469   961 .   3100.000    -1  -1
    chr8    128221486   128223644   peak31465   961 .   3100.000    -1  -1
    chr8    101510621   101514237   peak31185   961 .   3100.000    -1  -1
    chr8    101504210   101508005   peak31184   961 .   3100.000    -1  -1
    chr7    8173062 8174642 peak28743   961 .   3100.000    -1  -1
    chr7    5563424 5570618 peak28669   961 .   3100.000    -1  -1
    chr7    55600455    55603724    peak29192   961 .   3100.000    -1  -1
    chr7    35767878    35770820    peak28976   961 .   3100.000    -1  -1
    chr7    28518260    28519837    peak28923   961 .   3100.000    -1  -1
    chr7    104652502   104654747   peak29684   961 .   3100.000    -1  -1
    chr6    6586316 6590136 peak26279   961 .   3100.000    -1  -1
    chr6    52362185    52364270    peak27366   961 .   3100.000    -1  -1
    chr6    407805  413348  peak26180   961 .   3100.000    -1  -1
    chr6    32936987    32941352    peak26978   961 .   3100.000    -1  -1
    chr6    226477  229964  peak26144   961 .   3100.000    -1  -1
    chr6    157017923   157020836   peak28371   961 .   3100.000    -1  -1
    chr6    137422769   137425128   peak28064   961 .   3100.000    -1  -1
    chr5    149789084   149793727   peak25705   961 .   3100.000    -1  -1
    chr5    149778033   149783125   peak25702   961 .   3100.000    -1  -1
    chr5    149183766   149185906   peak25695   961 .   3100.000    -1  -1
biobudhan
fonte
1
Qual é o tamanho do seu arquivo e quão estrita é a sua noção de "aleatório"? splitpode, errar, dividir um arquivo em partes de 1000 linhas cada, para obter mais arquivos em uma única chamada de sort. Além disso, você verificou se headé um pouco mais rápido do que tailporque não precisa ler o arquivo inteiro?
Ulrich Schwarz
@UlrichSchwarz: O arquivo de amostra que colei acima contém cerca de 33000 linhas. Em geral, todos os meus arquivos de cama terão mais ou menos o mesmo número de linhas. Também por exemplo: de um arquivo de linha 33000, não desejo obter 33 subconjuntos (1000 linhas em cada) em uma única execução. Eu só quero tirar as 1000 primeiras linhas de cada execução. Eu também estarei fazendo um rabo do mesmo arquivo. Apenas por amostra, eu usei headaqui.
biobudhan
De acordo com a página do manual, sort -Rutiliza um "hash aleatório de chaves". Criar o hash é uma total perda de tempo e provavelmente leva mais tempo do que qualquer outra coisa. Seria melhor ler as linhas em uma matriz e depois embaralhar isso usando índices. Pessoalmente, eu usaria perlpara isso; você poderia fazê-lo, bashmas precisará de uma função para gerar números aleatórios.
Goldilocks
@ goldilocks: Eu não sou uma perlpessoa! Você poderia me ajudar?
biobudhan
6
Tente em shufvez de sort -R, é consideravelmente mais rápido. Obviamente, fazê-lo na memória (consulte a resposta Perl) superará qualquer coisa que exija reler o arquivo inteiro no shell.
frostschutz 30/06

Respostas:

14

Supondo que você tenha memória suficiente para absorver o arquivo, tente

perl -e 'use List::Util 'shuffle'; @k=shuffle(<>); print @k[0..999]' file.bed

Como você deseja fazer isso 10000 vezes, recomendo integrar a repetição ao script e embaralhar os índices em vez da própria matriz para acelerar as coisas:

$ time perl -e 'use List::Util 'shuffle'; 
            @l=<>; for $i (1..10000){
               open(my $fh, ">","file.$i.bed"); 
               @r=shuffle(0..$#l); 
               print $fh @l[@r[0..999]]
            }' file.bed

real    1m12.444s
user    1m8.536s
sys     0m3.244s

O acima criado 10000 arquivos de 1000 linhas cada um de um arquivo que continha 37000 linhas (seu arquivo de exemplo repetido 1000 vezes). Como você pode ver, demorou um pouco mais de três minutos no meu sistema.

Explicação

  • use List::Util 'shuffle';: isso importa um módulo Perl que fornece a shuffle()função que randomiza uma matriz.
  • @l=<>;: carrega o arquivo de entrada ( <>) na matriz @l.
  • for $i (1..10000){} : execute isso 10000 vezes.
  • @r=shuffle(0..$#l);: $#lé o número de elementos em @lque @ragora é uma lista aleatória dos números de índice da matriz @l(as linhas do arquivo de entrada).
  • open(my $fh, ">","file.$i.bed");: abre um arquivo chamado file.$i.bedpara gravação. $iassumirá valores de 1 a 10000.
  • print $fh @l[@r[0..999]]: pegue os primeiros 1000 índices na matriz aleatória e imprima as linhas correspondentes (elementos de @l).

Outra abordagem é usar shuf( obrigado @frostschutz ):

$ time for i in {1..10000}; do shuf -n 1000 file.bed > file.$i.abed; done

real    1m9.743s
user    0m23.732s
sys     0m31.764s
terdon
fonte
Uau!! Isso é incrível!! Funcionou em 2 minutos :-) Só tenho mais uma pergunta. Que tal também recuperar as últimas 1000 linhas do arquivo? Porque precisamos saber o comprimento (número de linhas) no arquivo para conseguir isso? Por favor ajude!
biobudhan
1
@biobudhan não considero shufcomo sugerido por frostschutz: for i in {1..10000}; do shuf -n 1000 file.bed > file.$i.bed; done. Isso levou ~ 1 minuto no meu sistema. Quanto às últimas 1000 linhas, tudo o que você precisa é tail -n 1000.
terdon
1
O @biobudhan também vê a resposta atualizada para uma versão perl 3x mais rápida.
terdon
Sim, eu tentei e agora funciona mais rápido !! Muito obrigado!!! :-)
biobudhan 30/06
Você checou os arquivos de saída da versão perl? Parece-me estranho que ele tenha tão pouco systempo, que seria a E / S do arquivo - isso não deve ser tão totalmente diferente do que shufaquele que tem ~ 30s sys. Então, eu testei o perl aqui (corte n' colar) e O_O criou 1000 arquivos, mas todos os arquivos estavam vazios ...
Goldilocks
9

Se você deseja que um benchmark veja com que rapidez isso pode ser feito, copie e cole-o 10kshuffle.cppe compile g++ 10kshuffle.cpp -o 10kshuffle. Você pode executá-lo:

10kshuffle filename < inputfile

Onde filenameé um caminho base a ser usado para os arquivos de saída; eles serão nomeados filename.0, filename.1etc., e cada um contém as primeiras 1000 linhas de uma reprodução aleatória. Ele escreve o nome de cada arquivo à medida que avança.

#include <cerrno>
#include <cstdlib>
#include <cstring>
#include <fcntl.h>
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <unistd.h>
#include <vector>

using namespace std;

unsigned int randomSeed () {
    int in = open("/dev/urandom", O_RDONLY);
    if (!in) {
        cerr << strerror(errno);
        exit(1);
    }
    unsigned int x;
    read(in, &x, sizeof(x));
    close(in);
    return x;
}

int main (int argc, const char *argv[]) {
    char basepath[1024];
    strcpy(basepath,argv[1]);
    char *pathend = &basepath[strlen(basepath)];
// Read in.
    vector<char*> data;
    data.reserve(1<<16);
    while (!cin.eof()) {
        char *buf = new char[1024];
        cin.getline(buf,1023);
        data.push_back(buf);
    }

    srand(randomSeed());
    for (int n = 0; n < 10000; n++) {
        vector<char*> copy(data);
    // Fisher-Yates shuffle.
        int last = copy.size() - 1;
        for (int i = last; i > 0; i--) {
            int r = rand() % i;
            if (r == i) continue;
            char *t = copy[i];
            copy[i] = copy[r];
            copy[r] = t;
        }
    // Write out.
        sprintf(pathend, ".%d", n);
        ofstream file(basepath);
        for (int j = 0; j < 1000; j++) file << copy[j] << endl;
        cout << basepath << endl;
        file.close();
    }

    return 0;
}  

Em um único núcleo de 3,5 Ghz, isso é executado em ~ 20 segundos:

   time ./10kshuffle tmp/test < data.txt
   tmp/test.0
   [...]
   tmp/test.9999
   real 19.95, user 9.46, sys 9.86, RSS 39408

data.txt37.000 linhas duplicadas da pergunta. Se você deseja que o shuffle inteiro no arquivo de saída seja substituído pelas primeiras 1000 linhas, altere a linha 54 para:

for (int j = 0; j < copy.size(); j++) file << copy[j] << endl; 
Cachinhos Dourados
fonte
3

Portanto, há um aspecto do Unix na sua pergunta, mas vale a pena resolver o seu problema fundamental primeiro e depois tentar encontrar uma maneira do Unix-y de implementar essa solução.

Você precisa criar 10.000 amostras de tamanho 1.000 cada, a partir de um arquivo com um número grande e desconhecido de linhas. É possível fazer isso em uma única passagem do arquivo se você puder conter 10.000 x 1.000 linhas na memória. Se você não conseguir armazenar tantas linhas na memória, ainda poderá fazê-lo em uma única passagem se souber quantas linhas seu arquivo contém. Se você não souber quantas linhas seu arquivo contém, precisará de uma passagem adicional para contar o número de linhas.

O algoritmo, no caso mais difícil, quando você não sabe o número de linhas, é o seguinte para cada amostra (em paralelo, mantendo as amostras na memória):

  • inclua as primeiras 1.000 linhas na amostra
  • para a n-ésima linha (onde n > 1000), inclua-a com probabilidade 1000 / ne descarte uma linha aleatória das linhas que você já selecionou. (devido à probabilidade de descartar algumas linhas, precisamos manter a amostra na memória até o final da entrada)

Uma maneira elegante de implementar a segunda etapa é gerar um número inteiro aleatório kem [1, n]. Se, em k <= 1000seguida, inclua a linha e substitua a k-a linha existente por ela. Aqui está uma descrição mais padrão do algoritmo: http://en.wikipedia.org/wiki/Reservoir_sampling

Se você souber o número de linhas R, então:

  • comece com tamanho de amostra, sde 0
  • inclua a n-ésima linha com probabilidade (1000 - s) / (R - n + 1)e a produza imediatamente (e aumente o tamanho da amostra s)

Como fazer isso no Unix? awkparece ser a resposta para esta postagem na Internet (não posso garantir sua correção, mas o código está lá) https://news.ycombinator.com/item?id=4840043

necromante
fonte