5
\$\begingroup\$

Introduction

The function divides a range given by a begin_iterator and an end_iterator into n sub-ranges of the same format, where the sub-ranges must be as equally sized as possible.

Example

Consider a set of size 10:

\$\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}\$

The output would be is a set of n = 3 sub-ranges:

\$\{ \{ 0, 3 \}, \{ 4, 6 \}, \{ 7, 9 \} \}\$

Where each sub-set is as even as possible, in the previous example the sets have sizes 4, 3, and 3, respectively; that is the most even way to distribute 10 elements into 3 sub-sets.

Review goals

  • Efficiency
  • Correctness

Implementation

The oringinal code contained an issue which I missed by pure luck. Here is the fixed working code; the changes do not invalidate the present answer.

#include <vector>   // std::vector<T>
#include <iterator> // std::distance(), std::next()

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n )
{
    using size_type = std::size_t;

    auto sz = std::distance( begin, end );
    auto element_per_group_count = sz / n;
    auto remaining_element_count = sz % n;

    std::vector<std::pair<Iterator, Iterator>> ranges;
    ranges.reserve( n );

    if ( remaining_element_count == 0 )
    {
        --element_per_group_count;

        ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

        for ( auto i = 1U; i < n; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }
    }
    else
    {
        ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

        for ( auto i = 1U; i < remaining_element_count; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }

        --element_per_group_count;

        for ( auto i = ranges.size(); i < n; ++i )
        {
            auto first = std::next( ranges[ i - 1 ].second, 1 );
            ranges.emplace_back( std::make_pair( first,
                std::next( first, element_per_group_count ) ) );
        }
    }
    return ranges;
}

Output

enter image description here

\$\endgroup\$
0
9
\$\begingroup\$

Misleading Return Type

You have:

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n )

The difference between auto and decltype(auto) is that the latter can deduce reference types as well. But you're returning a value, always, regardless of Iterator. This choice makes it seem as if you could be returning a reference. If you are going to use a placeholder return type here, use simply auto.

Even better, the return type for this function is not a complicated expression that's difficult to spell. It's simply std::vector<std::pair<Iterator, Iterator>>, so let's just use that:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )

emplace_back

The advantage of emplace_back is not having to actually construct the object to pass in. So when you write:

ranges.emplace_back( std::make_pair( std::next( begin, 0 ),
            std::next( begin, element_per_group_count ) ) );

That's inefficient (you're copy constructing a pair instead of in-place constructing it) and just a bunch of extra typing. Also next(iter, 0) is iter, so the above line is logically exactly equivalent to:

ranges.emplace_back(begin, std::next(begin, element_per_group_count));

Overly Complicated Algorithm!

I'm not sure why you have three for loops or why even division is a special case of the algorithm... Also I'm pretty sure that special case is wrong. Consider a range of size 15 dividing into 3 chunks, so it divides evenly. We'd start with element_per_group_count == 5, but then we decrement it to 4, and add the first range of:

[0, 4)

Then the next two ranges will be:

[5, 9)
[10, 14)

We successfully divided into three chunks, but we're actually missing elements! 4, 9, and 14 will not appear in any of the three chunks. The correct division would be [[0, 5), [5, 10), [10, 15)].


We're just chunking the range (begin, end) into n pieces. That implies a simple for-loop. We need n things. Each one is approximately of size distance(begin, end)/n. There will be distance(begin, end)%n remainder, which we will allocate one at a time as we go until we run out of remainder. When we already added n-1 things, we just can add the rest as the last chunk (since there's nothing else to do at that point).

This is all you need:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )
{
    std::vector<std::pair<Iterator, Iterator>> ranges;
    ranges.reserve(n);

    auto dist = std::distance(begin, end);
    auto chunk = dist / n;
    auto remainder = dist % n;

    for (size_t i = 0; i < n-1; ++i) {
        auto next_end = std::next(begin, chunk + (remainder ? 1 : 0));
        ranges.emplace_back(begin, next_end);

        begin = next_end;
        if (remainder) remainder -= 1;
    }

    // last chunk
    ranges.emplace_back(begin, end);
    return ranges;
}

Dividing up the remainder one at a time means that if we have 15 elements into 6 chunks, we end up with sizes of [3, 3, 3, 2, 2, 2] instead of any other weird alternative like the naive [2, 2, 2, 2, 2, 5].

Too many chunks? None?

What do you do in the case where n > distance(begin, end) or n == 0? I guess we should probably add some error checks:

template <typename Iterator>
std::vector<std::pair<Iterator, Iterator>>
divide_work( Iterator begin, Iterator end, std::size_t n )
{
    std::vector<std::pair<Iterator, Iterator>> ranges;
    if (n == 0) return ranges;
    ranges.reserve(n);

    auto dist = std::distance(begin, end);
    n = std::min<size_t>(n, dist);
    auto chunk = dist / n;
    auto remainder = dist % n;

    for (size_t i = 0; i < n-1; ++i) {
        auto next_end = std::next(begin, chunk + (remainder ? 1 : 0));
        ranges.emplace_back(begin, next_end);

        begin = next_end;
        if (remainder) remainder -= 1;
    }

    // last chunk
    ranges.emplace_back(begin, end);
    return ranges;
}
\$\endgroup\$
4
  • \$\begingroup\$ Thank you for taking time to look at my code. While your code is vastly simpler (and therefore easier to understand and maintain), I've timed the execution times of both algorithms and yours seems to be about 55% slower, possibly because you have many if conditions in your for loop and I have none. That was the reason for such a long 3 loop algorithm. \$\endgroup\$
    – cr_oag
    Oct 7 '15 at 14:55
  • \$\begingroup\$ You were right and your code was actually faster once reserve was added. Thanks for the help! \$\endgroup\$
    – cr_oag
    Oct 7 '15 at 15:15
  • \$\begingroup\$ The last chunk emplace_back is seems to be redundant. It could be inside the for loop that would iterate all n iterations. Since we share the reminder among the first chunks the least chunk will have size of exactly dist/n and it will end exactly at end. Right? ։) \$\endgroup\$
    – Vahagn
    Dec 14 '17 at 8:29
  • \$\begingroup\$ Furthermore, thus the check for n == 0 will be eliminated and the loop can be over the iterators while begin != end and the check for n > distance(begin, end) will also be eliminated automatically. \$\endgroup\$
    – Vahagn
    Dec 14 '17 at 8:39
5
\$\begingroup\$
#include <vector>   // std::vector<T>
#include <iterator> // std::distance(), std::next()

Not a big fan of those comments, they tend to go stale pretty fast, e.g. here you're also "importing" std::cbegin and std::cend in main from that indirect include. If you want to (or have to) explicitly list all you're importing, you're missing those two. And it would be better if you included <iterator> in main rather than relying on that indirect include.

template <typename Iterator>
decltype( auto ) divide_work( Iterator begin, Iterator end, std::size_t n ) ...

Why decltype(auto)? You know exactly the nature (value category/"referenceness") of what you're returning and you better not return any sort of reference since you're returning a local variable. auto is enough.

using size_type = std::size_t;

You're not using that alias, you can drop it.

You might want to pull the two loops into a separate function template. The div_sz loop variable is a bit odd since it is always equal to n. Drop it too.


I changed your main to take n as a command line parameter and ran it. Works for your test case, but:

$ ./a.out 0
Floating point exception
$ ./a.out 1
Segmentation fault
$ ./a.out 15
Segmentation fault

Going for n greater than the size of the list gives strange results too.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your review. I was misunderstanding decltype( auto ). The redundant code is an excellent point. In relation to getting segmentation faults for invalid values of n, I simply decided to make the function unchecked to squeeze out performance. \$\endgroup\$
    – cr_oag
    Oct 7 '15 at 6:05
  • \$\begingroup\$ It seems that we both overlooked the most obvious test case, when the remainder is 0. I've fixed the bug without invalidating your review points. If you've got the time, maybe you can check it out and see if your review requires any updates. \$\endgroup\$
    – cr_oag
    Oct 7 '15 at 6:41
3
\$\begingroup\$

Barry's points on correctness are good ones. It's also possible to implement the algorithm using STL algorithms rather than a loop. Whether that's an improvement in this case is a matter of taste but here's one way to do it. This could be made even simpler and more general with Eric Niebler's range-v3 library which is being proposed for standardization in C++17.

template<typename It>
auto divide_work(It first, const It last, const std::size_t n) {
    std::vector<std::pair<It, It>> ranges;
    ranges.reserve(n);
    std::generate_n(back_inserter(ranges), n, [&, size = std::distance(first, last)]{
        const auto curr = first;
        std::advance(first, size / n + (ranges.size() < size % n));
        return std::make_pair(curr, first);
    });
    return ranges;
}
\$\endgroup\$
2
\$\begingroup\$

At least in theory, rather than returning a vector of ranges, I'd rather this functioned like other algorithms, so the signature would be something like this:

template <class InIt, class OutIt>
void divide_work(InIt b, InIt e, OutIt d, std::size_t n)

Then you'd probably want to do a static_assert (or similar) to assure that the output iterator's value_type is a pair of the input iterators.

For better or worse, however, this can complicate client code considerably. Instead of a simple: auto divs = divide_work(...); the client is stuck with figuring out a fairly complex type like std::pair<std::container<T>::iterator, std::container<T>::iterator>, and defining a container (or other recipient) of that kind of objects. As much as I like it philosophically, it's probably not very practical.

Nonetheless, depending on how the result is used, it might be worth reconsidering this decision--especially if it's not a situation where you can depend on using auto for all (or at least most) code that has to deal with that result container.

As far as computing the sizes goes, rather than a single loop that computes the correct sizes each iteration, (e.g., std::next(begin, chunk + (remainder ? 1 : 0));) I'd rather just use two loops:

auto gen = [&](size_t s) {
    auto it = std::next(begin, s);
    *dest = { begin, it };
    ++dest;
    begin = it;
};

size_t i;
for (i = 0; i < remainder; i++)
    gen(size + 1);

for (; i < n; i++)
    gen(size);

I, for one, find the intent considerably easier to understand this way.

\$\endgroup\$
1
  • \$\begingroup\$ The two loop version is originally what I had (very incorrectly) written. It is in fact the fastest way to do this (I've measured). The speed differences are negligible (100-200 ms for 10 million runs), but it's still good to have the faster one in the end. I think that returning the vector of ranges is clearer. Thanks for your review. \$\endgroup\$
    – cr_oag
    Oct 9 '15 at 14:21

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.