相关疑难解决方法(0)

我试图理解外部合并排序算法是如何工作的(我看到了相同问题的一些答案,但没有找到我需要的东西).我正在阅读Jeffrey McConnell撰写的"分析算法"一书,我正在尝试实现那里描述的算法.

例如,我有输入数据:3,5,1,2,4,6,9,8,7,我只能将4个数字加载到内存中.

我的第一步是读取4个数字块的输入文件,在内存中对它们进行排序,然后将一个写入文件A,然后写入文件B.

我有:

A:[1,2,3,5][7]  
B:[4,6,8,9]

现在我的问题是,如果它们不适合内存,我如何将这些文件中的块合并到较大的文件中呢？杰弗里麦康奈尔写道,我需要阅读半块并将它们合并到下一个文件C和D.

但我得错了序列:

C:[1,2,4,6,3,8,5,9]
D:[7]

有人可以提供分步说明的例子吗？

PS:我理解如何通过读取文件来合并数字,但是如何使用内存缓冲区来减少I/O操作呢？

我想在 C++ 中生成大量有序且均匀分布的随机数，n, （即n >= 1,000,000,000）。

一首我认为，简单的方法是

1. n使用std::uniform_real_distribution<double>,顺序生成均匀分布的数字，
2. 然后使用std::sort.

但是，这需要几分钟时间。

一个第二和更先进的方法是做并行的两个步骤为：

template <typename T>
void computeUniformDistribution(std::vector<T>& elements)
{
    #pragma omp parallel
    {
        std::seed_seq seed{distribution_seed, static_cast<size_t>(omp_get_thread_num())};
        std::mt19937 prng = std::mt19937(seed);
        std::uniform_real_distribution<double> uniform_dist(0, std::numeric_limits<T>::max());

        #pragma omp for
        for (size_t i = 0; i < elements.size(); ++i)
        {
            elements[i] = static_cast<T>(uniform_dist(prng));
        }
    }

    std::sort(std::execution::par_unseq, elements.begin(), elements.end());
}

但是，即使这样也需要大约30秒。鉴于均匀分布数字的生成只需要大约1.5秒，瓶颈仍然是排序阶段。

因此，我想问以下问题：如何以排序的方式有效地生成均匀分布的数据？