데이터를 더 빠르게 정렬하는 방법

파일을 읽을 수 있는 충분한 메모리가 있다고 가정하면 시도해 볼 수 있습니다.

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

10000번 하고 싶기 때문에 반복을 스크립트에 통합하고셔플링 인덱스속도를 높이기 위해 배열 자체 대신:

$ 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

위의 코드는 37,000줄이 포함된 파일에서 각각 1,000줄로 구성된 10,000개의 파일을 생성합니다(예제 파일은 1,000번 반복됩니다). 보시다시피 제 시스템에서는 3분 조금 넘게 걸렸습니다.

설명하다

• use List::Util 'shuffle';: 배열을 무작위화하는 기능을 제공하는 Perl 모듈을 가져옵니다 shuffle().
• @l=<>;: <>입력 파일( )을 배열에 로드합니다 @l.
• for $i (1..10000){}: 10,000번 실행합니다.
• @r=shuffle(0..$#l);: $#l는 요소의 수이므로 이제 배열 인덱스 번호(입력 파일의 행)의 임의 목록입니다.@l@r@l
• open(my $fh, ">","file.$i.bed");: 쓸 파일을 엽니다 file.$i.bed. $i값 범위는 1~10000입니다.
• print $fh @l[@r[0..999]]: 섞인 배열에서 처음 1000개의 인덱스를 가져오고 해당 행(의 요소 @l)을 인쇄합니다.

---

또 다른 방법은 shuf(@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

벤치마크를 통해 얼마나 빨리 수행될 수 있는지 확인하려면 이를 복사하여 10kshuffle.cpp붙여넣고 g++ 10kshuffle.cpp -o 10kshuffle. 그런 다음 실행할 수 있습니다.

10kshuffle filename < inputfile

filename출력 파일의 기본 경로는 어디에 있습니까? 등의 이름이 지정 filename.0되며 filename.1각각 셔플의 처음 1000줄을 포함합니다. 언제든지 각 파일의 이름을 씁니다.

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

단일 3.5Ghz 코어에서 실행 시간은 약 20초입니다.

   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행에 대해 문제가 반복됩니다. 출력 파일에 처음 1000줄 대신 전체 셔플을 포함하려면 54줄을 다음과 같이 변경합니다.

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

따라서 귀하의 질문은 Unix에 관한 것입니다. 그러나 먼저 기본적인 문제를 해결한 다음 Unix-y 방식으로 솔루션을 구현하는 방법을 찾는 것이 좋습니다.

행 수를 알 수 없는 파일에서 각각 크기가 1,000인 샘플 10,000개를 생성해야 합니다. 다음에서 이 작업을 수행할 수 있습니다.일단 통과10,000 x 1,000 라인이 메모리에 들어갈 수 있으면 파일 내용을 볼 수 있습니다. 메모리에 그렇게 많은 줄을 저장할 수 없고 파일에 포함된 줄 수를 알고 있는 경우에도 한 번에 처리할 수 있습니다. 파일에 포함된 줄 수를 모르는 경우 줄 수를 한 번 더 세어야 합니다.

더 어려운 경우, 행 수를 모르는 경우 알고리즘은 각 샘플에 대해 다음을 수행합니다(샘플을 메모리에 병렬로 유지).

• 샘플에 처음 1,000개 행 포함
• n번째 행( )의 경우 n > 1000이를 확률에 포함시키고 1000 / n선택한 행에서 임의의 행을 버립니다. (일부 라인은 폐기될 수 있으므로 입력이 끝날 때까지 샘플을 메모리에 보관해야 합니다.)

두 번째 단계를 구현하는 우아한 방법은 k에서 임의의 정수를 생성하는 것 입니다 [1, n]. 그런 k <= 1000다음 해당 줄을 포함하고 k기존 줄을 그 줄로 바꿉니다. 다음은 알고리즘에 대한 보다 표준적인 설명입니다.http://en.wikipedia.org/wiki/Reservoir_sampling

행 수를 알고 있는 경우 R다음을 수행합니다.

• 표본 크기 s0 으로 시작
• n번째 확률 행을 포함 (1000 - s) / (R - n + 1)하고 즉시 출력합니다(그리고 표본 크기를 늘립니다 s).

유닉스에서 이 작업을 수행하는 방법은 무엇입니까? awk인터넷에 있는 이 게시물에 대한 답변인 것 같습니다(정확성을 보장할 수는 없지만 코드는 있습니다).https://news.ycombinator.com/item?id=4840043