4
\$\begingroup\$

I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:

{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0}  → 4
{1, -2, 0, -1} → 1

I wrote a function:

unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
    unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

    for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
        if (SIGN(a[i]) != SIGN(a[i - 1])) {
            maxlen = std::max(maxlen, len);
            len = 0;
        } else {
            if (i == a.size() - 1)
                return std::max(maxlen, len + 1);
        }
    }

#undef SIGN

    return maxlen;
}

Can you please give me tips to improve my code?

\$\endgroup\$
  • 4
    \$\begingroup\$ This only merits a comment (not a full answer) but since I just read the essay by Bob Nystrom it behooves me to note that your function name is too long. Shorten it to make it more readable. \$\endgroup\$ – Konrad Rudolph Mar 5 at 15:29
  • 3
    \$\begingroup\$ Naming things is often described as one of the Two Hard Problems in Programming (along with Cache Invalidation and Off-by-One Errors). "Shorten it" is easier said than done! We can obviously remove the get prefix, but after that, it gets more difficult. My best effort is maxSameSignRunLength() but that's still not very concise... \$\endgroup\$ – Toby Speight Mar 5 at 16:25
  • 4
    \$\begingroup\$ Realistically, this is a toy function; in the context of particular business domain, the values likely have meaning beyond "positive/negative number" and so the function would similarly be named based on those higher-level semantics. Something like "maxTemperatureSpan", for example. \$\endgroup\$ – dlev Mar 5 at 18:59
9
\$\begingroup\$

A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).

No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.

When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.

(More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).

Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iterator>

template<typename ForwardIt>
std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
{
    auto const signdiff =
        [](auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
        ForwardIt change = std::adjacent_find(first, last, signdiff);
        if (change != last) { ++change; }

        std::size_t len = std::distance(first, change);
        if (len > maxlen) { maxlen = len; }

        first = change;
    }

    return maxlen;
}

// tests:

#include <vector>

int main()
{
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
        {
         {0, {}},
         {1, {1}},
         {1, {1, -2}},
         {1, {1, -2,  3}},
         {1, {-1, 2, -3}},
         {2, {1,  2}},
         {2, {1,  2, -3}},
         {2, {-1, -2, 3}},
         {2, {-1, 2,  3}},
         {2, {-1, 2,  3, -4}},
        };

    int failures = 0;
    for (auto const& [e, v]: tests) {
        failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
}
\$\endgroup\$
  • \$\begingroup\$ std::size_t is not defined in <cstdint>. Your test should at least cover sequences in which there are more negatives than positives (\$\{-1\}, \{1, -2, -3\}\$). \$\endgroup\$ – Snowhawk Mar 5 at 23:39
  • \$\begingroup\$ You should be using std::signbit. \$\endgroup\$ – Cody Gray Mar 6 at 6:28
  • \$\begingroup\$ @Cody, yes. For the original code, visiting only integers, there's no real advantage to std::signbit. But having made the code generic, then that is a sensible choice (because we might now be seeing NaN or -0). \$\endgroup\$ – Toby Speight Mar 6 at 9:33
  • \$\begingroup\$ @Snowhawk - right on both counts; I've edited. I made sure that the tests had longest run at beginning and at end, but never considered varying the sign of the longest run. \$\endgroup\$ – Toby Speight Mar 6 at 10:21
  • \$\begingroup\$ The advantages are increased readability and a potential for better optimization. Clang and ICC generate the same code, but GCC's is slightly better for std::signbit (it rearranges the code, and thus is able to reduce one of the shifts to a bitwise-AND). The major disadvantage is, as far as I can tell, no support for std::signbit on MSVC. I'm not sure if it's non-compliant, or the version for integer types is a non-standard extension. \$\endgroup\$ – Cody Gray Mar 6 at 17:51
7
\$\begingroup\$

I would raise at least the following points:

  • Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.

  • To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = [](int v) { return v >= 0; }; and use this instead of SIGN.

  • You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.

\$\endgroup\$
5
\$\begingroup\$

Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.

If you are going to use a macro define it before the function (outside the function) and undefine it after the function.

The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.

\$\endgroup\$
  • 2
    \$\begingroup\$ It's obviously a personal preference, but I see no need to enclose the entire function between #define and #undef; indeed, on the rare occasions I need macros like this, I prefer to keep them local to a block as in the original code. I agree that in this case, a function or lambda expression is more appropriate. \$\endgroup\$ – Toby Speight Mar 5 at 16:28
  • 3
    \$\begingroup\$ I think I would recommend (if not eliminating the macro) to fully parenthesize the macro arguments in the expansion, i.e. ((a) >= 0). Even though the usages here are safe without that, it still causes a slowdown every time I read it and have to check. \$\endgroup\$ – Toby Speight Mar 5 at 16:32

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.