5
\$\begingroup\$

I want to find if 'N' numbers are even or odd in the fastest way possible.

Here's the following code which produces the desired output, but I do not know how efficient it is.

int main() {
int N,x;
scanf("%d",&N);
while(N--){
   scanf("%d",&x);
    x&1 ? cout << "No" << endl : cout << "Yes" << endl;
}
return 0;

Can this code be improved in any way to get faster results?

\$\endgroup\$
6
  • \$\begingroup\$ Is the input guaranteed to be integers? \$\endgroup\$ Sep 12, 2016 at 17:08
  • \$\begingroup\$ The code reads from stdin. Is the input is coming from a human, or is stdin redirected from a file? \$\endgroup\$
    – Moby Disk
    Sep 12, 2016 at 19:41
  • \$\begingroup\$ @IgnacioVazquez-Abrams Yes, they are guaranteed to be integers. \$\endgroup\$
    – Raghav
    Sep 13, 2016 at 4:26
  • \$\begingroup\$ @MobyDisk They are redirected to a file. \$\endgroup\$
    – Raghav
    Sep 13, 2016 at 4:26
  • \$\begingroup\$ Converting string to integer and then testing the integer by ANDing it has got to be slower than just testing the last byte of the string (if the input is guaranteed to be integers). Ofcourse, it gives rise to ugly code. \$\endgroup\$
    – blackpen
    Sep 13, 2016 at 7:08

3 Answers 3

19
\$\begingroup\$

Given that 99.9% of time is spent in scanf, cout and waiting for user input then there isn't much you can do about performance (but see notes).

What it may be improved is readability of your code. First of all your're mixing C style I/O (scanf) with C++ I/O (std::cout). Let's move to C++ std::cin.

Do not ever add using namespace std; (Why is “using namespace std” considered bad practice?)

In C++ there is no need to declare all variables at the top of your method.

I think ternary operator ?: is usually used for its result, not for side-effects of called code (here you're ignoring returned values). At first this usage is confusing for caller.

If you have a loop I think for is more clear (in intent) than while. Do not worry about extra variable, compiler will optimize it for you.

int main()
{
    int numbersToRead;
    std::cin >> numbersToRead;

    for (int i=0; i < numbersToRead; ++i)
    {
       int number;
       std::cin >> number;

       bool isEven = (number & 1) == 0;
       std::cout << (isEven  ? "Yes" : "No") << std::endl;
    }

    return 0;
}

This example is pretty small but for more complex code you may want to extract some functions:

int main()
{
    for (int i=readNumberOfValuesToRead(); i > 0; --i)
       std::cout << (isEven(readValue()) ? "No" : "Yes") << std::endl;

    return 0;
}

If you're already using Boost you may use boost::irange (let me also show that you may/should move formatting to a proper manipulator (for simplicity in this example I use standard one which prints true/false instead of Yes/No):

int main()
{
    std::cout << std::boolalpha;
    for (auto i : boost::irange(0, readNumberOfValuesToRead()))
       std::cout << isEven(readValue()) << std::endl;

    return 0;
}

I'd stop here (but read notes) for this code however if your scenario is (or it will be) more complex you will probably need to introduce more classes: ValuesReader base class (with a StandardInputValuesReader concrete class) to read values from an input stream and ValuesWriter (same...) to write output somewhere (using a ValueProcessor or ValueConverter and a custom stream manipulator?) Also remember that proper classes will make your life incredibly more easy during testing (because an abstract base class can be easily mocked while to read from std::cin you need much more code in your tests - and they can't be well-tested in isolation.)

EDIT

Few notes:

  • As Snowhawk04 noted I/O synchronization (between C and C++ functions) may slow down execution (or it may even not).
  • (number & 1) == 0 and (number % 2) == 0 seem to have the same performance (and generated assembly output), at least on GCC. Pick the one you feel more comfortable with.
  • Flushing output buffer (because of newline) may make it slower (but again consider that you're waiting user input). A different approach may help (concatenate results into std::string or std::stringstream and then write just once to std::cout). It's not a good approach if your application is interactive but it may be viable if it's intended to be used from command line with I/O redirection.

Just a proof of concept:

int main() 
{
    std::ostringstream output;
    output << std::boolalpha;
    for (int i : boost::irange(0, readNumberOfValuesToRead(), 0))
        output << isEven(readValue()) << std::endl;

    std::cout << output.str();

    return 0;
}
  • Someone noted '\n' instead of std::endl will prevent flushing. '\n' has some performance benefits but you won't have a single flush because we're also reading from std::cin. The use of std::stringstream is the way to avoid flushing. Note that it is implementation dependent if this useless flush() will impact performance or not for std::cout (when std::cout.sync_with_stdio(false) is called.) In general I'd suggest to use it (measure...) but still stay on std::stringstream if you want to avoid multiple flushes (not for interactive use.)
  • I am just half joking but for a non-interactive use if you really need to squeeze maximum performance from this program then you may want to write it in C (in practice dropping C++ I/O and strings...)
\$\endgroup\$
4
  • \$\begingroup\$ I first started out with 'cin' but then found out that scanf() is a lot faster than cin. Hence the edit. +1 for the comment on readability of the code. \$\endgroup\$
    – Raghav
    Sep 12, 2016 at 8:47
  • 1
    \$\begingroup\$ @Raghav C++'s iostreams are set up to sync with themselves and the underlying C IO, so there is a cost to using them. You can disable synchronization between C/C++ IO and between std::cin/std::cout (std::cin.tie(nullptr);). \$\endgroup\$
    – Snowhawk
    Sep 12, 2016 at 9:22
  • \$\begingroup\$ "concatenate results into std::string or std::stringstream and then write just once to std::cout" - why not simply cout << "\n" instead of cout << endl? It wouldn't flush. \$\endgroup\$ Sep 13, 2016 at 10:53
  • \$\begingroup\$ @MarianSpanik no, we're also reading from std::cin the we're already flushing std::cout. To avoid std::endl may increase performance because you won't call flush() twice (with second call without data to write) The use of std::stringstream is (here) only to do it in-memory (with a possibly better buffering implementation) and less OS dependent performance \$\endgroup\$ Sep 13, 2016 at 11:03
2
\$\begingroup\$

Don't use std::endl, use a "\n" character. endl not only prints a new line, but it also flushes the buffers. This ensures that you see the text immediately after the endl is printed. However, in this case you don't need that. If you want speed, use "\n". It will buffer as much as it feels like internally.

\$\endgroup\$
0
1
\$\begingroup\$

You'd probably be faster asking for a single user input than in each iteration.

E.g. ask "list of values: " 1,54,42,67,123,69 (you can either recalculate N, or ask N to be the first number).

For example, in C,

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 128

int main(void)
{
  char input[SIZE];
  char value[SIZE];
  int a,b;
  int v, isOdd;

  printf("Enter the list of numbers separated by a comma: ");
  scanf("%s",&input);

  a = 0;

  do
  {
    b = strcspn(&input[a],",\n");

    if (b<a)
    {
      v = atoi(&input[a]);
    }
    else
    {
      memcpy(value,&input[a],b);
      v = atoi(value);
    }

    isOdd = (v&1);
    printf("%d: %s\n",v,(isOdd==0)?"yes":"no");
    a += b+1;
  } while (input[a] != '\n');

  return 0;
}

which gives

Enter the list of numbers separated by a comma: 1,2,3,4
1: no
2: yes
3: no
4: yes
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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