使用合并排序对具有1亿个数字的1GB大文件进行排序

#1 楼

不要这样做

using namespace std;

这是一个坏习惯，会使您陷入很多麻烦。请根除习惯。

请参阅：为什么“使用命名空间标准”被认为是不好的做法？

注意：“标准”库使用命名空间的原因std::使得使用它作为前缀不是很大的负担。问题是'\n'执行了流的刷新（除了添加std::endl之外），结果这使得使用流的效率非常低，因为您需要等待将每个值写入磁盘才能继续。

让系统在最佳时间冲洗自己的内部缓冲区。它会自动执行此操作，而无需您的任何帮助。

读取值

我看到您没有使用标准流到整数的转换。

long value;
stream >> value;

，但是使用行读取器而不是使用std::endl将字符串转换为数字。

我假设您已经进行了适当的速度测试，发现这样做更快在您使用的规模上，您不需要'\n'流提供的所有功能。

如果这是真的，那么我将结束该调用，以便您可以使用atol()和operator>>来使您的代码更具可读性。在循环中测试atol()

struct Number
{
    long value;
    static std::string  reusableBuffer;
    operator long() const {return value;}
    friend std::istream& operator>>(std::istream& str, Number& data) {
        std::getline(str, data.reusableBuffer);
        data.value = std::atol(data.reusableBuffer);
        return str;
    }
};

问题是，如果流上有错误，则最终会陷入无限循环（如果有错误从流中读取它进入坏状态，直到您将其重置。处于错误状态时，它将拒绝读取更多值，因此永远不会到达文件末尾。

而不是测试operator>>，您应该检查并确保流是operator>>（如果流达到atol()或eof，那么它将不再是eof()，因此您的循环仍将正确退出）。 good()的测试是简单地在布尔上下文（预期为bool的表达式）中使用流，编译器会将流转换为bool，从而导致对eof()的调用。 br />
我认为合并可以简化。

我认为我们可以大大简化合并算法。

while (!sorted_1.eof() ||!sorted_2.eof());}

将一个文件复制到另一个文件。

将所有值合并到一个文件中后。然后，将其他文件中的剩余编号简单地复制到目标位置。但是，无需花费额外的时间将这些数字从文本转换为整数然后再转换为文本。只需将原始数据从一个文件复制到另一个文件即可。

while(sorted_1 || sorted_2);

中间格式

所以中间文件不需要放在人类可读的形式。您花费大量时间在整数与文本之间进行转换。与其执行此操作，不如将数字的二进制表示形式写入中间文件，然后在合并时将其直接读回数字中。

文件。

当前您执行3次合并操作。一次将第1部分和第2部分合并到一个临时文件中。然后将3和4合并到另一个临时文件中，最后将这些临时文件合并到输出中。

从不同的流中合并不会占用大量内存。因此，您应该同时读取所有临时文件（原因是只要您的文件少于一千个）。

因此您应该打开所有4个临时文件并从中读取值他们。每次迭代都会从4个文件中找到最大值，然后将其写入输出并读取下一个值。

全球状态。

全球状态

Number number;
if (sorted1 >> number) {
    sorted1Value = number;
}
if (sorted2 >> number) {
    sorted2Value = number;
}
while (sorted1 && sorted2) {
    // Don't need to explicitly test if they are equal.
    // If they are equal always use the sorted1 file.
    // that way you get a stable sort (an important property for
    // sorted values in some situations).
    //
    // It also makes the code simpler.
    if (sorted1Value <= sorted2Value) {
        result << sorted1Value << "\n";
        sorted1 >> number;
        sorted1Value = number;
    }
    else {
        result << sorted2Value << "\n";
        sorted2 >> number;
        sorted2Value = number;
    }
}
// At this point one of the streams is empty.

一直被认为是一件坏事。永远不要使用它。您仍然可以通过在适当的地方使用局部值来获得相同的效率。

要提高error()的效率，您要做的一件事是保留其大小。这样一来，它就无需进行任何重新分配（这是很昂贵的）。 br />

// At this point one of the streams is empty.
if (stream1) {
    result << sorted1Value;
    result << stream1.rdbuf()
}
if (stream2) {
    result << sorted2Value;
    result << stream2.rdbuf()
}

通常这样写：

// writing
result.write(reinterpret_cast<char*>(&sorted1Value), sizeof(sorted1Value));

// reading
stream1.read(reinterpret_cast<char*>(&sorted1Value), sizeof(sorted1Value));

这是因为数组（向量）的索引始终从零开始。 br />

#2 楼

避免std::endl



乍一看，似乎您在C ++中就文件I / O速度犯下了最大的罪过：我真正想要的是换行符（std::endl）。

我还没有测试您的特定代码，但是过去的经验表明，只写'\ n'而不是'\n'来结束一行，

最大化运行大小

一旦摆脱了过早的悲观化，下一步使合并排序尽可能快地运行是为了最大化您创建的单个运行的大小（其中“运行”是中间文件之一，按排序顺序保存部分输入，然后将其合并以生成最终输出）。 >
要最大化运行大小，通常首先从分配的内存中读取尽可能多的数据。然后，您没有进行完全排序，而是创建了一个堆（例如，使用endl）。然后是棘手的部分：每次将值写入输出时，都会从输入中读取另一个值。然后，您检查它是否大于您刚刚写出的值。如果它更大，它仍然可以进入当前运行，因此将其插入到堆中并继续。将其写入当前运行），则将值保留在内存顶部，并且当前堆将缩小一倍。读取并保留在内存顶部的值，然后开始写下一次运行，读取下一个值，并在可能的情况下将其插入，等等。

假设您的输入是随机的，这通常会使您大约将中间行程的长度加倍，因此您只需执行大约一半的合并步骤。

但是，输入已经包含一些按排序顺序排列的数字是很普遍的。当/如果发生这种情况，这可以让您利用预先存在的顺序来提高性能（以至于如果输入已经被完全排序，那么它将“识别”出来，并在单个复制周期中产生完全排序的输出。

您真的需要合并排序吗？

1亿个4字节的整数每个都占用不到400兆字节的RAM。一台相当陈旧的机器现在通常将至少具有4 GB的RAM，因此，如果您仅将整个输入读入内存，对其进行排序并写出，则仅会使用大约10％的可用内存。 -过时（3岁）的手机具有3 GB的RAM，因此即使在这种情况下，这种策略也是完全合理的。一个更通用的排序程序，实际上可以在超出可用内存的输入上使用。如果您确实需要合并排序，我的adv如果要坚持一次只在内存中存储2500万个项目，那是可以的，但至少要进行处理，直到到达输入结束为止，而不是盲目地假设那里可以只能是其中的4个。

#3 楼

不要在全球范围内使用using namespace std;，这是一个不好的习惯。如果您真的不喜欢一遍又一遍地编写std::，则将其放在需要的函数作用域中。但是即使那样，也要避免导入整个名称空间，而只导入特定的标识符。
缩进不一致，这可能是复制粘贴错误，但会分散注意力。
检查数字的上限。如果小于20亿（2,000,000,000），则可以使用int作为向量类型，将内存需求减半。
为什么对向量，行，文件名等使用全局变量？完全没有必要。
reserve()向量，因此不需要重新分配。
不要将临时文件中的数字存储为文本。解析文本比读取字节要慢。
不要使用endl;不需要时将强制刷新到输出。相反，只需编写\n即可。

#4 楼

利用您对域的了解
通过使用字符串，您可以无需解析就可以比较数字。首先比较符号字符（如果存在），然后跳过前导零，然后比较有效部分的长度，然后再执行（字符串）比较。
如果以下情况，您可以省略一些步骤您知道数字永远不会有前导零或始终是相同的符号-利用已知的约束！
如果知道行的最大长度，则可以读取固定大小的行在合并阶段使用char数组而不是字符串。
了解标准库
而不是重新实现合并，为什么不使用std::merge()中的<algorithm>呢？您需要合适的输入和输出迭代器，但这些迭代器很容易安排。

#5 楼

由于许多违法行为已经在其他答案中得到了很好的描述
[1]
[2]
，因此我将仅列举那些立即打击我的行为：

由于未包含使用的所有内容而无法在某些平台上编译（在这种情况下为string标头）
由于未引用numbersSorted，1_sorted_piece和2_sorted_piece而未编译

using namespace std;
不必要的全局变量
不必要的按值传递参数
缩进和不一致的缩进

函数和参数名称选择不当。例如我希望使用类似

void merge_files(std::string const& src1_filename
    , std::string const& src2_filename
    , std::string const& result_filename)

代码结构差，重用少，重复很多，功能太复杂的功能。
不必要地使用eof

即使您知道前面的大小，也不要std::endl-对向量进行编码
魔术数（例如reserve）-如果我们对此进行硬编码以期望1亿个数字，我希望将某个常数25000000设置为期望的数量，而不是魔幻数字，而是使用该常数的表达式。为人类解析-我更喜欢将此值写为VALUE_COUNT，因为它立即很明显是2500万，并且任何不错的编译器都会在编译时执行该计算，因此性能没有差异。
<就是说，让我们看一下问题陈述：


我的任务是使用合并对具有1亿个数字的1GB文件进行排序排序无重复离子。


这看起来像是一种锻炼，所以看来我们应该遵守要求。 />对具有1亿个数字的1GB文件进行排序


它缺少一些细节，但是我们可以假设它是文本，每个数字平均10个字符。至少一个字符作为分隔符，每个数字平均为9个数字，因此假设它们在32位整数范围内似乎很安全。

到目前为止，尽管您输入的内容很好代码可能具有更好的错误处理能力，并在输入未能满足您的期望时提供有意义的错误消息。 ，1亿个32位整数大约需要380 MiB，因此，在当前大多数硬件上，将其与地址空间中的临时缓冲区配合使用不是什么大问题。在这种情况下，我将使事情保持简单，并坚持3个步骤-输入，排序和输出。

这样，我希望至少看到3个功能，一个对于每个步骤。



使用无递归的合并排序


对我来说，这是要求迭代实现合并排序和恕我直言，即使您尝试进行两次顶级合并也很失败，但由于在2500万个值上使用了标准(25 * 1000 * 1000)，您在这里惨遭失败。排序工作：


从概念上讲，合并排序的工作方式如下：


将未排序的列表划分为n个子列表，每个子列表包含1个元素（ 1个元素的列表被视为已排序）。
重复合并子列表以产生新的已排序子列表，直到仅剩1个子列表为止。这将是排序列表。




为了迭代地执行此操作，我们采用自下而上的方法。从概念上讲，我们可以将整数向量视为已排序子序列的序列（初始长度为1，最后一个子序列可能比其余子序列短）。我们执行许多合并过程，合并成对的相邻子序列：


1次通过后，我们有一个长度为2的已排序子序列的列表
2次通过后，我们有一个长度为4的已排序子序列的列表长度为8的...
...

这里我希望至少看到一个函数，该函数使用给定的子序列长度执行一次合并传递，以及迭代该函数的main sort函数。通过。使用sort似乎是一种合法的方法-如果没有，那么我相信已经对实现进行了充分的讨论，因此没有必要深入探讨。合并过程可能看起来像

template<typename InputIt, typename OutputIt>
void merge_pass(InputIt const& src_begin
    , InputIt const& src_end
    , OutputIt const& tgt_begin
    , std::size_t step_size)
{
    InputIt input(src_begin);
    OutputIt output(tgt_begin);

    std::size_t const iter_count(std::distance(src_begin, src_end) / (step_size * 2));
    for (std::size_t i(0); i < iter_count; ++i) {
        InputIt const midpoint(std::next(input, step_size));
        InputIt const endpoint(std::next(midpoint, step_size));

        std::merge(input, midpoint, midpoint, endpoint, output);

        std::advance(input, step_size * 2);
        std::advance(output, step_size * 2);
    }

    // Handle the remainder
    std::size_t const remaining(std::distance(input, src_end));
    if (remaining > step_size) {
        // Second block is incomplete
        InputIt const midpoint(std::next(input, step_size));

        std::merge(input, midpoint, midpoint, src_end, output);
    } else if (remaining > 0) {
        // Second block is missing, the rest is already sorted
        std::copy(input, src_end, output);
    }
}

然后驱动程序函数看起来像

template<typename T>
void merge_sort(std::vector<T>& v)
{
    uint32_t const PASS_COUNT(static_cast<uint32_t>(std::ceil(std::log2(v.size()))));

    std::vector<T> temp(v.size());
    for (uint32_t pass(0); pass < PASS_COUNT; ++pass) {
        merge_pass(v.begin(), v.end(), temp.begin(), 1 << pass);
        temp.swap(v); // NB: Swap is cheap
        // Now v contains sorted sub-sequences of double the size
        // and temp contains the old state, which we no longer care about
        // so we can overwrite it in the next iteration
    }
}

对此进行基准测试，您会发现此算法比标准排序慢大约2-3倍。考虑到简单性，这很好，我认为它可以接受。


Coliru上的实时示例

#6 楼

您的主体应分解为较小的功能。您将详细了解如何完成一个步骤，然后完成另一个完全不同的步骤。在这个级别上，我想要执行此步骤的摘要，而不是详细的细节。我感觉到，使sort_merge成为函数的唯一原因是可以多次调用它-否则，您也需要认真研究该实现。的抽象。您在头脑上想出了不同的步骤。因此，使代码反映出来。这很难解释，但这是最重要的一课。

void sort_merge(string result, string file1, string file2){ 

为什么要按值传递字符串？无需复制它们。 const string& result等。

已被告知不要在全局范围内使用using指令。但是也不要在每个函数中都这样做！而是在#includes后面列出该cpp文件（而不是.h文件）中将经常使用的内容。例如，

using std::string;
using std::cout;

s2=atol(line2.c_str());

请使用更现代的功能lexical_cast！

auto s2= lexical_cast<long>(line2);

，您还会看到在声明的位置进行初始化！不要将本地变量long s1,s2;放在顶部，然后稍后再使用。并且，每个语句只定义一个变量。 br />

if (file.good() == true )

不要对string进行明确测试！已经是long了，那么为什么还要再进行一次测试以确保fstream呢？那真是愚蠢。该条件采用bool值-语法中不需要顶级比较。

if ((file.good() == true ) == true)

这没有止境！只是

if (file.good())

或者更好的是，使用提供的内置真值测试简化这种确切的情况： br />这种情况下的eof是不同的，但请考虑一下：这是正常的方式。您尝试阅读，但失败。阅读前无需检查eof。

#7 楼

您的基本想法是完全错误的。将文件拆分为4，然后合并为2，然后合并为1，则完全没有任何效果，除非对这些部分进行了排序，而您可能无法利用内存中的数据量在内存中完成这些操作。双向合并是合并的最不高效方法。

这主要不是邻接编码。这是关于最小化通过外部数据的次数。在过去的60年中，这是一个经过深入研究的主题。唐纳德·克努斯（Donald Knuth）专为《计算机编程的艺术》第三卷而作。我强烈建议您阅读，

在光头摘要中，您应该：


通过替换选择分配初始运行。
执行平衡或为此目的，使用已存在的标准算法，多相将重复地合并到那些文件上。查找它们。

#8 楼

您看过STXXL库吗？由于使用stxxl::sort(...)支持内核外，这将使您更轻松地进行排序。除了将大量文件加载到适当的容器中之外，您无需执行任何其他操作。

#9 楼

如果数字都是唯一的32位正整数，则可以轻松地对内存中的数字进行排序：

1）分配2 ^ 32项的内存中位数组：（2 ^ 32 / 8）字节，然后将其清除为零

2）将每个输入数字转换为位数组索引，并在数组中设置相应的位

3）一旦所有输入数字已处理，请从数组开始按顺序输出与所设置的位数组元素对应的数字

，但这可能是问题的过分简化！ （严格来说，以上是“分布/存储桶排序”）

#10 楼

Z-Tree是一种基于位拆分和分支的新数据结构。使用Z-Tree，您可以以O（n）的时间复杂度对内存中1GB的文件进行排序。比合并排序要快得多。