データをより早くソートする方法

ファイルを読み取るのに十分なメモリがあると仮定すると、試してみることができます。

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選択した行からランダムな行を捨てます。 （一部のラインは廃棄される可能性があるため、入力が終了するまでサンプルをメモリに保存する必要があります。）

2番目のステップを実装するエレガントな方法は、からk任意の整数を生成することです[1, n]。次にk <= 1000、その行を含め、k既存の行をその行に置き換えます。以下はアルゴリズムのより標準的な説明です。http://en.wikipedia.org/wiki/Reservoir_sampling

行数がわかっている場合は、R次の操作を行います。

• サンプルサイズs0で始まる
• n番目の確率行を含めて(1000 - s) / (R - n + 1)すぐに出力します（そしてサンプルサイズを増やしますs）。

Unixでこれを行う方法は？awkインターネット上のこの投稿に対する答えのようです（正確さを保証することはできませんが、コードはあります）。https://news.ycombinator.com/item?id=4840043