Сортировка данных быстрее приближается

Если вы хотите, чтобы эталонный тест показал, как быстро это может быть сделано, скопируйте его в 10kshuffle.cpp и скомпилируйте g++ 10kshuffle.cpp -o 10kshuffle. Затем вы можете запустить его:

10kshuffle filename < inputfile

Где имя файла - базовый путь для использования выходных файлов; они будут иметь имена 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,5 ГГц это занимает ~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.txt было 37000 строк, продублированных из вопроса. Если вы хотите, чтобы вся тасовка в выходном файле вместо первых 1000 строк, измените строку 54 на:

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

Итак, в Вашем вопросе есть Unix аспект, но сначала стоит решить Вашу фундаментальную проблему, а затем попытаться найти Unix-y способ реализовать это решение.

Вам нужно создать 10,000 примеров размером 1000 каждый из файла с неизвестным, большим количеством строк. Это можно сделать в одном единственном проходе файла, если вы можете хранить в памяти 10,000 х 1000 строк. Если вы не можете удержать в памяти столько строк, вы все равно можете сделать это за один проход, если знаете, сколько строк содержит ваш файл. Если вы не знаете, сколько строк содержит ваш файл, вам потребуется один дополнительный проход для подсчета количества строк.

Алгоритм, в более сложном случае, когда Вы не знаете количество строк, должен сделать следующее для каждой выборки (параллельно, сохраняя выборки в памяти):

• включить первые 1000 строк в выборку
• для n-ой строки (где n > 1000), включить с вероятностью 1000 / n и отбросить случайную строку из уже выбранных Вами строк. (из-за вероятности отбрасывания некоторых строк нам нужно удерживать выборку в памяти до конца входа)

Элегантным способом реализации второго шага является генерация случайного целого k в [1, n]. Если k <= 1000, то включите эту строку и замените на нее существующую k-ю строку. Вот более стандартное описание алгоритма: http://en.wikipedia.org/wiki/Reservoir_sampling

Если известно количество строк, R, то:

• начинаем с размера выборки, s из 0
• включаем n-ю строку с вероятностью (1000 - с) / (R - n + 1) и сразу же выводим ее (и увеличиваем размер выборки s)

Как это сделать на Unix? awk кажется ответом на это сообщение в интернете (я не могу поручиться за его правильность, но код там) https://news.ycombinator.com/item? id=4840043