Tri plus rapide des données

11

J'ai besoin de trier un bedfichier au hasard 10000 fois et de prendre les 1000 premières lignes à chaque fois. Actuellement, j'utilise le code suivant:

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

Cela prend presque 6 heures pour cela pour chaque fichier. J'en ai environ 150 à régler. Existe-t-il une solution plus rapide pour cela?

Un échantillon des données (myfile.bed_sorted) que j'ai:

    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
la source
1
Quelle est la taille de votre fichier et dans quelle mesure votre notion de "aléatoire" est-elle stricte? splitpeut, euh, diviser un fichier en morceaux de 1000 lignes chacun, de sorte que vous obtiendrez plus de fichiers en un seul appel de sort. De plus, avez-vous vérifié s'il headest légèrement plus rapide que tailparce qu'il n'a pas besoin de lire l'intégralité du fichier?
Ulrich Schwarz
@UlrichSchwarz: L'exemple de fichier que j'ai collé ci-dessus contient environ 33000 lignes. En général, tous mes dossiers de lit auront plus ou moins le même nombre de rangées. Aussi, par exemple: à partir d'un fichier de 33 000 lignes, je ne souhaite pas obtenir 33 sous-ensembles (1 000 lignes chacun) en une seule fois. Je souhaite seulement prendre les 1000 premières lignes de chaque course. Je ferai également une queue du même fichier. Juste pour échantillon, je l'ai utilisé headici.
biobudhan
Selon la page de manuel, il sort -Rutilise un "hachage aléatoire des clés". La création du hachage est une perte de temps totale et prend probablement plus de temps que toute autre chose. Il serait préférable de lire les lignes dans un tableau, puis de mélanger celles-ci à l'aide d'index. Personnellement, j'utiliserais perlpour cela; vous pouvez le faire avec bashmais vous aurez besoin d'une fonction pour générer des nombres aléatoires.
goldilocks
@goldilocks: Je ne suis pas une perlpersonne! Pourriez-vous s'il vous plaît m'aider?
biobudhan
6
Essayez shufplutôt sort -R, c'est considérablement plus rapide. Bien sûr, le faire en mémoire (voir la réponse Perl) battra tout ce qui nécessite de relire le fichier entier dans le shell.
frostschutz

Réponses:

14

En supposant que vous disposez de suffisamment de mémoire pour récupérer le fichier, vous pouvez essayer

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

Puisque vous voulez faire cela 10000 fois, je recommanderais d'intégrer la répétition dans le script et de mélanger les index au lieu du tableau lui-même pour accélérer les choses:

$ 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

Ce qui précède a créé 10 000 fichiers de 1 000 lignes chacun à partir d'un fichier qui contenait 37 000 lignes (votre exemple de fichier s'est répété 1 000 fois). Comme vous pouvez le voir, cela a pris un peu plus de trois minutes sur mon système.

Explication

  • use List::Util 'shuffle';: ceci importe un module Perl qui fournit la shuffle()fonction qui randomise un tableau.
  • @l=<>;: charge le fichier d'entrée ( <>) dans le tableau @l.
  • for $i (1..10000){} : exécutez ce 10000 fois.
  • @r=shuffle(0..$#l);: $#lest le nombre d'éléments dans est @ldonc @rmaintenant une liste aléatoire des numéros d'index du tableau @l(les lignes du fichier d'entrée).
  • open(my $fh, ">","file.$i.bed");: ouvre un fichier appelé file.$i.beden écriture. $iprendra des valeurs de 1 à 10000.
  • print $fh @l[@r[0..999]]: prenez les 1000 premiers indices du tableau mélangé et imprimez les lignes correspondantes (éléments de @l).

Une autre approche consiste à utiliser shuf( merci @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
la source
Sensationnel!! C'est génial!! Cela a fonctionné en 2 minutes :-) J'ai encore une question. Que diriez-vous également de récupérer les 1000 dernières lignes du fichier? Parce que nous devons connaître la longueur (nombre de lignes) du fichier pour y parvenir? Aidez-moi!
biobudhan
1
@biobudhan ne considèrent shufcomme suggéré par Frostschutz: for i in {1..10000}; do shuf -n 1000 file.bed > file.$i.bed; done. Cela a pris environ 1 minute sur mon système. Quant aux 1000 dernières lignes, tout ce dont vous avez besoin est tail -n 1000.
terdon
1
@biobudhan voit également la réponse mise à jour pour une version Perl 3 fois plus rapide.
terdon
Oui, je l'ai essayé et ça marche plus vite maintenant !! Merci beaucoup!!! :-)
biobudhan
Avez-vous revérifié les fichiers de sortie de la version Perl? Il me semble étrange qu'il y ait si peu de systemps, ce qui serait des E / S de fichiers - cela ne devrait pas être si totalement différent de shufcelui qui a ~ 30s sys. J'ai donc testé le Perl ici (couper et coller) et O_O il a créé 1000 fichiers mais tous les fichiers étaient vides ...
goldilocks
9

Si vous voulez qu'un benchmark voie à quelle vitesse il peut être fait, copiez-collez-le dans 10kshuffle.cppet compilez g++ 10kshuffle.cpp -o 10kshuffle. Vous pouvez ensuite l'exécuter:

10kshuffle filename < inputfile

filenameest un chemin de base à utiliser pour les fichiers de sortie; ils seront nommés filename.0, filename.1etc. et chacun contient les 1000 premières lignes d'un shuffle. Il écrit le nom de chaque fichier au fur et à mesure.

#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;
}  

Sur un seul cœur de 3,5 GHz, cela s'exécute en ~ 20 secondes:

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

data.txtétait 37000 lignes dupliquées de la question. Si vous voulez le shuffle entier dans le fichier de sortie au lieu des 1000 premières lignes, changez la ligne 54 en:

for (int j = 0; j < copy.size(); j++) file << copy[j] << endl; 
boucle d'or
la source
3

Il y a donc un aspect Unix dans votre question, mais cela vaut la peine de résoudre d'abord votre problème fondamental, puis d'essayer de trouver un moyen Unix-y pour implémenter cette solution.

Vous devez créer 10 000 échantillons de taille 1 000 chacun à partir d'un fichier avec un grand nombre de lignes inconnu. Il est possible de le faire en un seul passage du fichier si vous pouvez conserver 10 000 x 1 000 lignes en mémoire. Si vous ne pouvez pas conserver autant de lignes en mémoire, vous pouvez toujours le faire en une seule passe si vous savez combien de lignes contient votre fichier. Si vous ne savez pas combien de lignes votre fichier contient, vous avez besoin d'une passe supplémentaire pour compter le nombre de lignes.

L'algorithme, dans le cas le plus difficile lorsque vous ne connaissez pas le nombre de lignes, consiste à effectuer les opérations suivantes pour chaque échantillon (en parallèle, conserver les échantillons en mémoire):

  • inclure les 1 000 premières lignes de l'échantillon
  • pour la nième ligne (où n > 1000), incluez-la avec la probabilité 1000 / net supprimez une ligne aléatoire parmi les lignes que vous avez déjà sélectionnées. (en raison de la probabilité de supprimer certaines lignes, nous devons conserver l'échantillon en mémoire jusqu'à la fin de l'entrée)

Une manière élégante d'implémenter la deuxième étape consiste à générer un entier aléatoire kdans [1, n]. Si k <= 1000alors incluez la ligne et remplacez la k-ième ligne existante par elle. Voici une description plus standard de l'algorithme: http://en.wikipedia.org/wiki/Reservoir_sampling

Si vous connaissez le nombre de lignes R, alors:

  • commencer par la taille de l'échantillon, sde 0
  • inclure la nième ligne avec probabilité (1000 - s) / (R - n + 1)et la sortir immédiatement (et incrémenter la taille de l'échantillon s)

Comment faire ça sous Unix? awksemble être la réponse par ce post sur Internet (je ne peux pas garantir son exactitude, mais le code est là) https://news.ycombinator.com/item?id=4840043

nécromancien
la source