2
\$\begingroup\$

This is a follow up question to the one I asked a couple of days ago.


I reviewed the suggestions & did some research (specifically, read relevant info on CLRS). The new version is 3 times faster (210ms vs 71ms on 100,000 numbers) & looks cleaner.

One thing I still feel weird about is not using iterators except than to init the sub-vectors. However, any attempt in using them causes a drop in performance (down to 120ms).

I'm also curious if my code is good in terms of code style. Is this idiomatic C++?

void merge(std::vector<int>& a, int p, int q, int r)
{
    std::vector<int> l(a.begin() + p, a.begin() + q + 1);
    std::vector<int> ri(a.begin() + q + 1, a.begin() + r + 1);

    int n1 = q - p + 1;
    int n2 = r - q;

    int i, j; i = j = 0;

    while (i < n1 && j < n2) {
        if (l[i] < ri[j]) {
            a[p++] = l[i++];
        } else {
            a[p++] = ri[j++];
        }
    }

    while (i < n1) {
        a[p++] = l[i++];
    }

    while (j < n2) {
        a[p++] = ri[j++];
    }
}

void merge_sort(std::vector<int>& a, int p, int r)
{
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Like the @tinstaafl said, your code is unreadable, not everyone has the ability to read other people's mind. Please edit this and I'll comment.. \$\endgroup\$ – matheussilvapb May 14 '14 at 21:45
  • \$\begingroup\$ Not sure what you measured, but on my machine, using iterators is faster, not slower (by almost 20%). Can you provide a test case? I used 1E6 uniformly distributed PRNGd integers and compiled with heavy optimizations. \$\endgroup\$ – dyp May 14 '14 at 21:52
  • 1
    \$\begingroup\$ If you want to compare times we really need both pieces of code. To make sure you are doing a valid comparison. Also make sure optimizations are turned on in both cases. \$\endgroup\$ – Martin York May 15 '14 at 5:45
  • \$\begingroup\$ @LokiAstari link to previous version is in first sentence. \$\endgroup\$ – Inoryy May 15 '14 at 8:23
  • 1
    \$\begingroup\$ I understand, but ideally you should strive to give your merge routine an STL type of iterator interface, and remove the vector dependence. \$\endgroup\$ – TemplateRex Jun 2 '14 at 4:30
3
\$\begingroup\$

Let's do this in steps. This is going to be a longer answer, but I'll try this experiment at least once. The original version takes about 400 ms to sort 1E6 integers on my machine (virtual machine, g++4.8.1, libstc++, -O3 -march=native -fwhole-program -ftree-vectorize).

Variable names

void merge(std::vector<int>& a, int p, int q, int r)

As others have mentioned, many people prefer a bit more meaningful variable names. A larger issue I see in these signatures is that they don't tell me whether it's an half-open or closed range.

Const correctness

If you don't intend to modify a variable / parameter, make it const.

Passing containers and offsets

Don't pass containers unless you need to modify the container itself. Using iterators typically leads to better performance, though using pointers might even be faster (my measurements of this algorithm, libstdc++, g++4.8.1).

If we apply those points, but don't change anything related to the algorithm itself:

void merge(int* beg, int* const med, int* const end)
{
    std::vector<int> l(beg, med+1);
    std::vector<int> ri(med+1, end+1);

    int const n1 = med - beg + 1;
    int const n2 = end - med;

    int i, j; i = j = 0;

    while (i < n1 && j < n2) {
        if (l[i] < ri[j]) {
            *beg++ = l[i++];
        } else {
            *beg++ = ri[j++];
        }
    }

    while (i < n1) {
        *beg++ = l[i++];
    }

    while (j < n2) {
        *beg++ = ri[j++];
    }
}

void merge_sort(int* const p, int* const r)
{
    if (p < r) {
        int* const q = p + (r - p) / 2;
        merge_sort(p, q);
        merge_sort(q + 1, r);
        merge(p, q, r);
    }
}

Takes about 330 ms to sort 1E6 integers.


Usage of closed ranges

Use half-open ranges if possible. You can more easily express the concept of an empty range as a half-open range [x, x) than with closed ranges.

Two allocations instead of one

You create two temporary vectors, but you only need some temporary storage. A first improvement is to use one vector. It might also be interesting to try std::get_temporary_buffer instead of std::vector.

Stability

While merging, you should use the left element first even if it's equivalent to the right:

        if (l[i] < ri[j]) { // not stable
            *beg++ = l[i++];
        } else {
            *beg++ = ri[j++];
        }

Simply invert this check to ri[j] < l[i] and invert the branches accordingly. This doesn't matter for ints, but I think it's a good habit since it guarantees stability for e.g. classes, where we use only some part of the value for the order relation.

If we apply those points and also change the algorithm to use pointers instead of offsets internally (not just in the interface):

void merge(int* beg, int const* const med, int const* const end)
{
    std::vector<int> l(beg, end);

    int const* cur1 = &l[0];
    int const* cur2 = &l[0] + (med-beg);

    int const* const end1 = cur2;
    int const* const end2 = std::next(&l.back());

    while (cur1 != end1 && cur2 != end2) {
        if (*cur2 < *cur1) {
            *beg++ = *cur2++;
        } else {
            *beg++ = *cur1++;
        }
    }

    while (cur1 != end1) {
        *beg++ = *cur1++;
    }

    while (cur2 != end2) {
        *beg++ = *cur2++;
    }
}

void merge_sort(int* const beg, int* const end)
{
    if (beg != end) {
        int* const med = beg + (end - beg) / 2;
        if(end - med > 1) // check required for half-open ranges
        {
            merge_sort(beg, med);
            merge_sort(med, end);
        }
        merge(beg, med, end);
    }
}

Takes about 270 ms to sort 1E6 integers.


We can now templatize the algorithm, but, as I said, using pointers turned out to be faster than using iterators:

template<class RaIt>
void merge(RaIt beg, RaIt med, RaIt end)
{
    using value_type = typename std::iterator_traits<RaIt>::value_type;
    std::vector<value_type> tmp(std::make_move_iterator(beg),
                                std::make_move_iterator(end));

    auto cur1 = &tmp.front();
    auto cur2 = &tmp.front() + (med-beg);

    auto const end1 = cur2;
    auto const end2 = std::next(&tmp.back()); // UB? don't think so..

    while (cur1 != end1 && cur2 != end2) {
        if (*cur2 < *cur1) {
            *beg++ = std::move(*cur2++);
        } else {
            *beg++ = std::move(*cur1++);
        }
    }

    while (cur1 != end1) {
        *beg++ = std::move(*cur1++);
    }

    while (cur2 != end2) {
        *beg++ = std::move(*cur2++);
    }
}

template<class RaIt>
void merge_sort(RaIt beg, RaIt end)
{
    if (beg != end) {
        auto const med = beg + (end - beg) / 2;
        if(end - med > 1)
        {
            merge_sort(beg, med);
            merge_sort(med, end);
        }
        merge(beg, med, end);
    }
}

Standard algorithms

Ok, this is probably beside the point, but you can use standard algorithms here:

  • std::copy inside the merge algorithm instead of manual loops, or rather std::move (the algorithm on ranges, not the cast)
  • std::merge
  • std::inplace_merge (215 ms, which tells us that the allocation or the copying still is a bottleneck)
  • std::sort (90 ms)
\$\endgroup\$
3
\$\begingroup\$

The first thing I would suggest is using better names for your variables. It's very hard for someone else looking at or using your code to determine what those variables are supposed to represent.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.