现代，C++兼容，合并排序

Question

这是对我以前的排序实现评论的一种后续，有一些特定的问题来合并排序，以及现代C++成语。

template<typename InputIt1,
         typename InputIt2,
         typename OutputIt,
         typename Comparator = std::less<typename std::iterator_traits<InputIt1>::value_type >>
void merge(InputIt1 first1,
           InputIt1 last1,
           InputIt2 first2,
           InputIt2 last2,
           OutputIt out,
           Comparator cmp = Comparator())
{
    while (first1 != last1 || first2 != last2)
    {
        if (first2 == last2 || first1 != last1 && cmp(*first1, *first2))
        {
            *out = *first1++;
        }
        else
        {
            *out = *first2++;
        }
        ++out;
    }
}

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef std::iterator_traits<BidirIt>::difference_type dt;
    typedef std::iterator_traits<BidirIt>::value_type vt;

    dt size = std::distance(first, last);
    if (size > dt(1))
    {
        auto middle = first + size / dt(2);

        std::vector<vt> left(first, middle);
        std::vector<vt> right(middle, last);

        auto left_begin = left.begin(), left_end = left.end();
        auto right_begin = right.begin(), right_end = right.end();

        sort_merge(left_begin, left_end);
        sort_merge(right_begin, right_end);

        ::merge(left_begin, left_end, right_begin, right_end, first);
    }
}

我正在寻找算法本身可能遗漏的任何性能优化，以及本例中可能没有遵守的现代C++结构。

我研究了就地合并，但是，我为就地合并找到的所有解决方案都执行得更糟。也就是说，用sort_insertion代替merge操作。然而，如果我要做一个就地的sort_merge，我将开始一个单独的主题，因为它被认为是一个完全独立的算法。

Answer 1

更喜欢使用移动而不是复制语义

如果您的对象是一个int，那么它就没有什么区别。但是有些对象的复制成本更高(比如std::string)。如果您可以移动而不是复制，您将获得更好的性能与更复杂的对象。

*out = *first1++;

// Just add a call to std::move
*out = std::move(*first1++);

太多的参数行

这是有点难说，这是必要的或完美的，你可以提出双方的论点。但是每行有一个参数似乎有点冗长。我更喜欢将参数分组为逻辑组(工具不喜欢这样，因为它们不能应用logical，因为它是特定的情况)。

但我个人认为，为了可读性，将参数放在逻辑组中是有意义的。

(见下文)

成员类型名称

从技术上讲，这是非法的：

typedef std::iterator_traits<BidirIt>::difference_type dt;

编译器无法判断difference_type是类型还是成员变量，直到它知道BidirIt的类型。所以，您需要告诉它，它是一个类型名称。

typedef typename std::iterator_traits<BidirIt>::difference_type dt;
 //     ^^^^^^^^  required for standards conformance

类名

类型在C++中很重要。尝试使用有助于识别类型的名称(有点冗长)。但是，用户定义的类型有一个初始大写字母(这样就可以很容易地从对象中发现)，这也是一种惯例。

typedef std::iterator_traits<BidirIt>::difference_type dt;

// Here I did not like the short name:
typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

不通过比较器按值

进行合并

合并操作不应该孤立地执行。它总是从sort_merge()函数中调用。因此，没有必要为每个对merge()的调用创建一个比较器，只需在sort_merge()中创建一次，然后通过const引用传递给对merge()的所有调用：

void merge(InputIt1 first1, InputIt1 last1,
           InputIt2 first2, InputIt2 last2,
           OutputIt out,
           Comparator const& cmp)

非最优实现

while (first1 != last1 || first2 != last2)
{
    if (first2 == last2 || first1 != last1 && cmp(*first1, *first2))
    {
        *out = *first1++;
    }
    else
    {
        *out = *first2++;
    }
    ++out;
}

最好这样写：

// Test your constraints here.
while (first1 != last1 && first2 != last2)
{
    // The comparison test then becomes much simpler.
    *out = std::move(cmp(*first1, *first2)
                         ? *first1++
                         : *first2++);
    ++out;
}
// Then the final optimized copy
// Only one of these loops will execute.
std::move(first1, last1, out);
std::move(first2, last2, out);

空间优化

在sort_merge()中创建副本

    std::vector<vt> left(first, middle);
    std::vector<vt> right(middle, last);

这意味着您使用更多的内存，因为您在这个迭代中有一个副本，然后在这个迭代下面的每个递归调用中创建一个副本，并且它们同时都是活动的。

如果您在适当的地方执行递归sort_merge()。然后，在merge()调用中，执行副本，然后得到更好的空间使用(因为在当前的迭代活动中只有一个副本)。

结果

你会注意到我稍微改变了合并。我们可以对输入做几个假设(因为它只从sort_merge()调用)：

• 只有一种类型的输入迭代器。
  • 因为我们知道我们要对同一容器的两半进行分类。

• 没有输出迭代器
  • 当合并完成的时候。

• 比较器不需要默认类型。
  • 这是作为sort_merge模板的一部分完成的。

• 我不超过两个范围。
  • 我使用开始/中间/结束

代码：merge

template<typename I, typename Comparator>
void merge(I first, I mid, I last, Comparator const& cmp)
{
    typedef typename std::iterator_traits<I>::difference_type DiffType;
    typedef typename std::iterator_traits<I>::value_type      ValueType;

    DiffType                size1 = std::distance(first, mid);
    DiffType                size2 = std::distance(mid, last);

    std::vector<ValueType>  hold1;
    std::vector<ValueType>  hold2;
    hold1.reserve(size1);
    hold2.reserve(size2);

    std::move(first, mid,  std::back_inserter(hold1));
    std::move(mid,   last, std::back_inserter(hold2));

    auto first1 = std::begin(hold1);
    auto last1  = std::end(hold1);
    auto first2 = std::begin(hold2);
    auto last2  = std::end(hold2);
    auto out    = first;

    while (first1 != last1 && first2 != last2)
    {
        *out = std::move(cmp(*first1, *first2)
                             ? *first1++
                             : *first2++);
        ++out;
    }
    std::move(first1, last1, out);
    std::move(first2, last2, out);
}

代码：sort_merge

template<typename I,
         typename Comparator = std::less<typename std::iterator_traits<I>::value_type>>
void sort_merge(I first,
                I last,
                Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type DiffType;

    DiffType size = std::distance(first, last);
    if (size > DiffType(1))
    {
        auto middle = first + size / 2;
        auto midIter = begin;
        std::advance(midIter, middle);

        sort_merge(first, midIter, cmp);
        sort_merge(midIter, last,  cmp);

        merge(first, midIter, end, cmp);
    }
}

Answer 2

由于我是一个初学者C++程序员，所以我不能评论您使用这种语言的方式，但我可以建议性能改进:在合并函数中创建一个向量来保存合并范围，将两个运行合并到它，然后将向量复制回原始输入数组，这并不酷:在对合并排序的最顶层调用中，您可以创建一个缓冲区数组，然后传递给所有后续的合并排序函数。这里的要点是两个数组(缓冲区和原始输入数组)交替它们的角色；在一次合并传递中，您从缓冲区合并到原始数据；在下一次合并传递时，您从原始数据合并到缓冲区。当然，您可以安排一些事情，以便排序的东西神奇地在原始输入数组中结束。与您的实现相比，这种方法使我的速度不断提高3。

以下是小型示范计划：

#include <algorithm>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>

using namespace std;

template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge(BidirIt first,
                BidirIt last,
                Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;
    typedef typename std::iterator_traits<BidirIt>::value_type vt;

    dt size = std::distance(first, last);
    if (size > dt(1))
    {
        auto middle = first + size / dt(2);

        std::vector<vt> left(first, middle);
        std::vector<vt> right(middle, last);

        auto left_begin = left.begin(), left_end = left.end();
        auto right_begin = right.begin(), right_end = right.end();

        sort_merge(left_begin, left_end);
        sort_merge(right_begin, right_end);

        ::merge(left_begin, left_end, right_begin, right_end, first);
    }
}

// 'first' is the begin of the target array
// 'last' is the end of the target array
// 'buffer' is the source array
template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type>>
void sort_merge2_impl(BidirIt first, BidirIt last, BidirIt buffer, Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::value_type vt;
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;

    dt size = std::distance(first, last);

    if (size < 2) {
        // Trivially sorted.
        return;
    }

    sort_merge2_impl(buffer, buffer + size / 2, first, cmp);
    sort_merge2_impl(buffer + size / 2, buffer + size, first + size / 2, cmp);

    std::merge(buffer, 
               buffer + size / 2, 
               buffer + size / 2, 
               buffer + size, 
               first,
               cmp);
}

// The entry point into optimized merge sort.
template<typename BidirIt,
         typename Comparator = std::less<typename std::iterator_traits<BidirIt>::value_type >>
void sort_merge2(BidirIt first,
                 BidirIt last,
                 Comparator cmp = Comparator())
{
    typedef typename std::iterator_traits<BidirIt>::difference_type dt;
    typedef typename std::iterator_traits<BidirIt>::value_type vt;
    dt size = std::distance(first, last);

    if (size > dt(1))
    {
        vt* buffer = new vt[size];
        std::copy(first, last, buffer);
        sort_merge2_impl(first, last, buffer, cmp);
    }
}

static int* get_random_int_array(const size_t length,
                                 const int minimum,
                                 const int maximum,
                                 const unsigned int seed)
{
    std::default_random_engine generator(seed);
    std::uniform_int_distribution<int> distribution(minimum, maximum);

    int* array = new int[length];

    for (size_t i = 0; i < length; ++i)
    {
        array[i] = distribution(generator);
    }

    return array;
}

static unsigned long long get_milliseconds()
{
    return std::chrono::duration_cast<std::chrono::milliseconds>(
           std::chrono::system_clock::now().time_since_epoch()).count();
}

int main(int argc, char** argv) {
    constexpr size_t length = 1000000;

    unsigned long long seed = get_milliseconds();

    int* arr1 = get_random_int_array(length, -10000, 100000, seed);
    int* arr2 = get_random_int_array(length, -10000, 100000, seed);
    int* arr3 = get_random_int_array(length, -10000, 100000, seed);

    unsigned long long ta = get_milliseconds();
    sort_merge(arr1, arr1 + length);
    unsigned long long tb = get_milliseconds();

    cout << "sort_merge in " << (tb - ta) << " ms." << endl;

    ta = get_milliseconds();
    sort_merge2(arr2, arr2 + length);
    tb = get_milliseconds();

    cout << "sort_merge2 in " << (tb - ta) << " ms." << endl;

    ta = get_milliseconds();
    std::stable_sort(arr3, arr3 + length);
    tb = get_milliseconds();

    cout << "std::stable_sort in " << (tb - ta) << " ms." << endl;

    cout << std::boolalpha;

    cout << "Equal: " 
         << (std::equal(arr1, arr1 + length, arr2) &&
             std::equal(arr1, arr1 + length, arr3)) << endl;

    return 0;
}