Szybsze sortowanie danych

11

Muszę posortować bedplik losowo 10000 razy i za każdym razem wziąć 1000 najlepszych wierszy. Obecnie używam następującego kodu:

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

Wykonanie tego dla każdego pliku zajmuje prawie 6 godzin. Mam około 150 do opracowania. Czy istnieje na to szybsze rozwiązanie?

Próbka danych (myfile.bed_sorted) Mam:

    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
źródło
1
Jak duży jest twój plik i jak surowe jest twoje pojęcie „losowości”? splitmożna, błędnie, podzielić plik na kawałki po 1000 linii każdy, aby uzyskać więcej plików za jednym wywołaniem sort. Czy również sprawdziłeś, czy headjest nieco szybszy niż taildlatego, że nie musi czytać całego pliku?
Ulrich Schwarz
@UlrichSchwarz: Przykładowy plik, który wkleiłem powyżej, zawiera około 33000 wierszy. Ogólnie rzecz biorąc, wszystkie moje pliki łóżek będą miały mniej więcej taką samą liczbę wierszy. Także na przykład: z pliku 33000 wierszy nie chcę uzyskać 33 podzbiorów (po 1000 wierszy w jednym). Chcę tylko wziąć 1000 najlepszych rzędów z każdego biegu. Będę również robił ogon tego samego pliku. Tylko dla próbki, użyłem headtutaj.
biobudhan
Według strony man sort -Rużywa „losowego skrótu kluczy”. Tworzenie skrótu jest całkowitą stratą czasu i prawdopodobnie zajmuje więcej czasu niż cokolwiek innego. Lepiej byłoby wczytać linie do tablicy, a następnie przetasować to za pomocą indeksów. Osobiście użyłbym perldo tego; możesz to zrobić, bashale potrzebujesz funkcji do generowania liczb losowych.
goldilocks
@goldilocks: Nie jestem perlosobą! Czy możesz mi pomóc?
biobudhan
6
Spróbuj shufzamiast sort -R, jest znacznie szybszy. Oczywiście, zrobienie tego w pamięci (patrz odpowiedź Perla) pobije wszystko, co wymaga ponownego odczytania całego pliku w powłoce.
frostschutz

Odpowiedzi:

14

Zakładając, że masz wystarczającą ilość pamięci, aby zrzucić plik, możesz spróbować

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

Ponieważ chcesz to zrobić 10000 razy, polecam zintegrowanie powtórzeń ze skryptem i przetasowanie indeksów zamiast samej tablicy, aby przyspieszyć:

$ 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

Powyżej utworzono 10000 plików po 1000 linii każdy z pliku zawierającego 37000 wierszy (przykładowy plik powtórzono 1000 razy). Jak widać, zajęło mi to nieco ponad trzy minuty.

Wyjaśnienie

  • use List::Util 'shuffle';: importuje moduł Perla, który udostępnia shuffle()funkcję losową tablicę.
  • @l=<>;: załaduj plik wejściowy ( <>) do tablicy @l.
  • for $i (1..10000){} : uruchom to 10000 razy.
  • @r=shuffle(0..$#l);: $#ljest liczbą elementów, @lwięc @rteraz jest losową listą numerów indeksów tablicy @l(linii pliku wejściowego).
  • open(my $fh, ">","file.$i.bed");: otwórz plik file.$i.beddo zapisania. $iprzyjmie wartości od 1 do 10000.
  • print $fh @l[@r[0..999]]: weź pierwsze 1000 indeksów z przetasowanej tablicy i wydrukuj odpowiednie linie (elementy @l).

Innym podejściem jest użycie shuf( dzięki @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
źródło
Łał!! To jest niesamowite!! Działa w 2 minuty :-) Mam tylko jedno pytanie. Co powiesz na odzyskanie ostatnich 1000 wierszy pliku? Ponieważ potrzebujemy znać długość (liczbę linii) w pliku, aby to osiągnąć? Proszę pomóż!
biobudhan
1
@biobudhan uważają shufjak sugeruje Frostschutz: for i in {1..10000}; do shuf -n 1000 file.bed > file.$i.bed; done. To zajęło ~ 1 minutę w moim systemie. Jeśli chodzi o ostatnie 1000 linii, wszystko czego potrzebujesz to tail -n 1000.
terdon
1
@biobudhan zobacz także zaktualizowaną odpowiedź na 3-krotnie szybszą wersję perla.
terdon
Tak, próbowałem i działa teraz szybciej !! Dziękuję Ci bardzo!!! :-)
biobudhan
Czy dokładnie sprawdziłeś pliki wyjściowe wersji perla? Wydaje mi się dziwne, że ma tak mało sysczasu, który byłby plikiem we / wy - nie powinno być tak zupełnie inne niż ten shuf, który ma ~ 30s sys. Przetestowałem tutaj perl jeden (cut n 'paste) i O_O utworzyło 1000 plików, ale wszystkie pliki były puste ...
goldilocks
9

Jeśli chcesz, aby test porównawczy pokazał, jak szybko można to zrobić, skopiuj go 10kshuffle.cppi wkompiluj g++ 10kshuffle.cpp -o 10kshuffle. Następnie możesz go uruchomić:

10kshuffle filename < inputfile

Gdzie filenamejest podstawowa ścieżka do plików wyjściowych; zostaną one nazwane filename.0, filename.1itd, a każdy z nich zawiera pierwsze 1000 linii w shuffle. Zapisuje nazwę każdego pliku na bieżąco.

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

Na pojedynczym rdzeniu 3,5 Ghz działa to w ~ 20 sekund:

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

data.txt37000 linii zostało zduplikowanych z pytania. Jeśli chcesz cały losowy plik wyjściowy zamiast pierwszych 1000 wierszy, zmień wiersz 54 na:

for (int j = 0; j < copy.size(); j++) file << copy[j] << endl; 
Złotowłosa
źródło
3

Pytanie ma aspekt uniksowy, ale warto najpierw rozwiązać podstawowy problem, a następnie spróbować znaleźć sposób na wdrożenie tego rozwiązania.

Musisz utworzyć 10 000 próbek o wielkości 1000 każda z pliku o nieznanej dużej liczbie wierszy. Można to zrobić w jednym przejściu pliku, jeśli możesz przechowywać w pamięci 10 000 x 1 000 wierszy. Jeśli nie możesz przechowywać tylu wierszy w pamięci, możesz to zrobić w jednym przebiegu, jeśli wiesz, ile wierszy zawiera Twój plik. Jeśli nie wiesz, ile wierszy zawiera Twój plik, potrzebujesz jednego dodatkowego przejścia, aby policzyć liczbę wierszy.

Algorytm, w trudniejszym przypadku, gdy nie znasz liczby wierszy, wykonuje następujące czynności dla każdej próbki (równolegle, zachowując próbki w pamięci):

  • uwzględnij pierwsze 1000 wierszy w próbce
  • dla n-tego rzędu (gdzie n > 1000), dołącz go z prawdopodobieństwem 1000 / ni odrzuć losowy wiersz z już wybranych wierszy. (ze względu na prawdopodobieństwo odrzucenia niektórych wierszy musimy przechowywać próbkę w pamięci do końca wprowadzania)

Elegancki sposób na wdrożenie drugiego kroku to wygenerowanie losowej liczby całkowitej kw [1, n]. Jeśli k <= 1000następnie dołącz wiersz i zastąp go istniejącym k-tym wierszem. Oto bardziej standardowy opis algorytmu: http://en.wikipedia.org/wiki/Reservoir_sampling

Jeśli znasz liczbę wierszy R, to:

  • zacznij od wielkości próby srównej 0
  • dołącz n-ty rząd z prawdopodobieństwem (1000 - s) / (R - n + 1)i wypisz go natychmiast (i zwiększ wielkość próbki s)

Jak to zrobić na Uniksie? awkwydaje się być odpowiedzią na ten post w Internecie (nie mogę ręczyć za jego poprawność, ale kod tam jest) https://news.ycombinator.com/item?id=4840043

nekromanta
źródło