隨機數外部排序

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

標準庫有一個歸併排序，但你需要使用隨機訪問迭代器。如果你可以使用mmap（或同等學歷），你有隨機訪問迭代器（是的，我知道你需要採取COUNT命令行）：

#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調用不實際需要。我真的很驚訝，這有不俗的表現。