乱数外部ソート

Question

N個の乱数を生成し、降順でバイナリファイルに書き込むプログラムを書く必要があります。メインメモリを使用するソートアルゴリズムを使用せずに実行する必要があります。

#include <iostream> 
#include <fstream> 
#include <ctime> 
#include <cstdlib> 

using namespace std; 
int main() { 
    srand(time(0)); 
    rand(); 
    int N; 
    do{ 
    cout << "Unesite N: "; 
    cin >> N; 
    } while(N<=0); 

    ofstream br("broj.dat", ios::binary | ios::trunc); 

    for(int i = 0; i<N; i++){ 
    int a = rand(); 
    br.write((char *)&a, sizeof(a)); 
    } 
    br.close(); 

    return 0; 
} 

だから、私が生成した乱数を、バイナリファイルに書きましたが、私はそれをソートする方法がわからない：これは私がこれまで行ってきたものです。

Answer 1

私はそれをどうやって行うのか疑似コードです。

for i in 1..N: 
    write rand() to new file 
    push onto file stack (new file, size=1) 
    while 2 < len(file stack) and size of top two files the same: 
     pop top two and merge them 
     push onto file stack (merged file, size=new size) 

while 2 < len(file stack): 
    pop top two and merge them 
    push onto file stack (merged file, size=new size) 

The top of the file stack is your new sorted file. 

Answer 2

番号を線形時間でソート順に生成できます。これを行う方法を記述した論文がある：ベントレー&サックス

https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf

/** 
* Generate an sorted list of random numbers sorted from 1 to 0, given the size 
* of the list being requested. 
* 
* This is an implementation of an algorithm developed by Bentley and Sax, and 
* published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on 
* 'Generating Sorted Lists of Random Numbers'. 
*/ 
public class SortedRandomDoubleGenerator { 
    private long  valsFound; 
    private double  curMax; 
    private final long numVals; 

    /** 
    * Instantiate a generator of sorted random doubles. 
    * 
    * @param numVals the size of the list of sorted random doubles to be 
    *  generated 
    */ 
    public SortedRandomDoubleGenerator(long numVals) { 
     curMax = 1.0; 
     valsFound = 0; 
     this.numVals = numVals; 
    } 

    /** 
    * @return the next random number, in descending order. 
    */ 
    public double getNext() { 
     curMax = curMax 
       * Math.pow(Math.E, Math.log(RandomNumbers.nextDouble()) 
         /(numVals - valsFound)); 
     valsFound++; 
     return curMax; 
    } 
} 

Answer 3

によって乱数の生成ソートリストは、標準ライブラリには、マージソートがありますが、ランダムアクセスイテレータを使用する必要があります。

#include <algorithm> 
#include <cstdio> 
#include <random> 
#include <fcntl.h> 
#include <sys/mman.h> 
#include <unistd.h> 

const size_t COUNT = 4096 * 4096; 

int main() 
{ 
    // create file (using mmap for simplicity) 
    int fd = open("out.dat", O_RDWR | O_TRUNC | O_CREAT, S_IRUSR | S_IWUSR); 
    if (fd < 0) { 
     std::perror("open failed"); 
     return 1; 
    } 
    if (ftruncate(fd, COUNT * sizeof(unsigned)) != 0) { 
     std::perror("ftruncate failed"); 
     close(fd); 
     return 1; 
    } 
    void* mm = mmap(nullptr, COUNT * sizeof(unsigned), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); 
    if (mm == MAP_FAILED) { 
     std::perror("mmap failed"); 
     close(fd); 
     return 1; 
    } 
    close(fd); 

    // populate file 
    unsigned* begin = static_cast<unsigned*>(mm); 
    std::default_random_engine rng((std::random_device())()); 
    std::generate_n(begin, COUNT, rng); 
    msync(mm, COUNT * sizeof(unsigned), MS_SYNC); 
    std::puts("file written"); 

    // sort file 
    std::stable_sort(begin, begin + COUNT); 
    msync(mm, COUNT * sizeof(unsigned), MS_SYNC); 
    std::puts("file sorted"); 

    if (std::is_sorted(begin, begin + COUNT)) { 
     std::puts("it's properly sorted"); 
    } 

    // close file 
    munmap(mm, COUNT * sizeof(unsigned)); 
    return 0; 
} 

msync通話が実際に必要されていません：あなたはmmap（またはそれに相当）を使用することができます場合は、（はい、私はあなたがコマンドラインからCOUNTを取る必要があることを知っている）、ランダムアクセスイテレータを持っています。私は正直言って、これはまともなパフォーマンスを持っていることに驚いています。