3

This is a very simple question, but unfortunately, I am stuck and do not know what to do. My program is a simple program that keeps on accepting 3 numbers and outputs the largest of the 3. The program keeps on running until the user inputs a character.

As the tittle says, my question is how I can make this execute faster ( There will be a large amount of input data ). Any sort of help which may include using a different algorithm or using different functions or changing the entire code is accepted.

I'm not very experienced in C++ Standard, and thus do not know about all the different functions available in the different libraries, so please do explain your reasons and if you're too busy, at least try and provide a link.

Here is my code

#include<stdio.h>
int main()
  {
    int a,b,c;
    while(scanf("%d %d %d",&a,&b,&c))
      {
         if(a>=b && a>=c) 
            printf("%d\n",a);
         else if(b>=a && b>=c) 
            printf("%d\n",b);
         else 
            printf("%d\n",c);
      }
    return 0;
  }

It's working is very simple. The while loop will continue to execute until the user inputs a character. As I've explained earlier, the program accepts 3 numbers and outputs the largest. There is no other part of this code, this is all. I've tried to explain it as much as I can. If you need anything more from my side, please ask, ( I'll try as much as I can ).

I am compiling on an internet platform using CPP 4.9.2 ( That's what is said over there )

Any sort of help will be highly appreciated. Thanks in advance

EDIT

The input is made by a computer, so there is no delay in input.

Also, I will accept answers in c and c++.

UPDATE

I would also like to ask if there are any general library functions or algorithms, or any other sort of advise ( certain things we must do and what we must not do ) to follow to speed up execution ( Not just for this code, but in general ). Any help would be appreciated. ( and sorry for asking such an awkward question without giving any reference material )

Community
  • 1
  • 1
Arun A S
  • 6,421
  • 4
  • 29
  • 43
  • 1
    First I would see if it NEEDS to be faster. It probably runs fast enough already. – Neil Kirk Feb 19 '15 at 14:19
  • The input is from a file, its an online programming website on which I run this program. – Arun A S Feb 19 '15 at 14:20
  • @Neil Kirk, the time limit for my program execution is 1 second and there are many test cases. – Arun A S Feb 19 '15 at 14:23
  • 3
    IO is your overhead. Avoid the "standard library" if you want performance. – dtech Feb 19 '15 at 14:24
  • 3
    Why the foobar is this question downvoted so much? It's reasonable and you can learn a lot from such tasks.... – UniversE Feb 19 '15 at 14:24
  • 1
    Have a look at this answer, http://stackoverflow.com/questions/9747419/which-is-the-fastest-method-of-input-in-c – Omer Farooq Feb 19 '15 at 14:25
  • Does this "online programming website" scan the numbers you output or can you create a file? – Floris Velleman Feb 19 '15 at 14:26
  • With which compiler, which compilation flag, and on which operating system, is your program running? – Basile Starynkevitch Feb 19 '15 at 14:27
  • @ddriver Isn't `scanf` in the standard library? – Neil Kirk Feb 19 '15 at 14:30
  • @Martin Dinov, the reason I say c++ is because I use a c++ compiler. The reason it looks like c code is because this is the fastest code I could think of. I will accept answers in c or c++.. The question was initially tagged both c and c++, but someone changed it. – Arun A S Feb 19 '15 at 14:37
  • 1
    @ArunA.S - try buffering both input and output. Read a larger chunk of the file before you process it from memory, output to memory before you `printf`. In both cases, focus on doing more work less frequently. – dtech Feb 19 '15 at 14:40
  • The online programming website has its input and output stored in a file. It does something due to which my program inputs data from the file and then converts my output into a file and compares it with its output file after program execution – Arun A S Feb 19 '15 at 14:43
  • @ddriver, can you please explain or give an example, I'm not too experienced, nor do I know how to implement what you have advised. – Arun A S Feb 19 '15 at 14:46
  • @ArunA.S instead of using `scanf` and `printf` for each step allocate some memory and read several multiples of 3 `int`s. Allocate another block of memory to put the output `int`. This way you minimize IO operations to disk. If your file is not very big, you can read the entire file into memory, and output the entire result into memory before you write it in a single operation. It will also be simpler to do the whole thing at once than to buffer it, as long as you have enough memory to do so. – dtech Feb 19 '15 at 14:51
  • @ddriver, I don't know the size of the Input file, It can be short, long or extremely long. So will your method still work ? ( I also do have a memory limit of 50000 Bytes, although I think that will be more than enough ). – Arun A S Feb 19 '15 at 15:20
  • 1
    scanf() and printf() already implement I/O buffering, so it's not clear that the program would speed up I/O very much by adding another layer of buffering. Perhaps making the stdio I/O buffer sizes larger would help a little ( http://www.gnu.org/software/libc/manual/html_node/Controlling-Buffering.html ) – Jeremy Friesner Feb 19 '15 at 16:11
  • 1
    It's likely being downvoted because the question has a premise that is likely false but definitely unsubstantiated -- that the program is the performance-limiting factor and thus there's some point to optimizing it. – David Schwartz Feb 20 '15 at 04:23
  • @David Schwartz, can you please explain what you mean – Arun A S Feb 20 '15 at 04:28
  • 1
    @ArunA.S You want to get to work faster, should you run faster to your car or find a shorter route to take in your car? Until you prove that the program is the bottleneck, there's no point in optimizing it. Punch "premature optimization" into your favorite search engine. – David Schwartz Feb 20 '15 at 08:55

2 Answers2

6

Your "algorithm" is very simple and I would write it with the use of the max() function, just because it is better style.

But anyway...

What will take the most time is the scanf. This is your bottleneck. You should write your own read function which reads a huge block with fread and processes it. You may consider doing this asynchronously - but I wouldn't recommend this as a first step (some async implementations are indeed slower than the synchronous implementations).

So basically you do the following:

  1. Read a huge block from file into memory (this is disk IO, so this is the bottleneck)
  2. Parse that block and find your three integers (watch out for the block borders! the first two integers may lie within one block and the third lies in the next - or the block border splits your integer in the middle, so let your parser just catch those things)
  3. Do your comparisions - that runs as hell compared to the disk IO, so no need to improve that
UniversE
  • 2,419
  • 17
  • 24
  • Depending on OS, there's likely some handy APIs for this, that don't come with all the icky overhead of the stdio functions. – Lundin Feb 19 '15 at 14:32
  • That's where the main problem occurs, I don't know how to use `max()` and `fwrite`. Can you please explain or provide a good link where I might find an explanation. ( Just reminding you that I can't understand complex stuff as I've only got programming experience from my school ) – Arun A S Feb 19 '15 at 14:34
  • 1
    @ArunA.S a good start is http://pubs.opengroup.org/onlinepubs/9699919799/idx/head.html (might be not the current version, but it's enough) - there you start with stdio.h and find `fwrite`. Read the documentation, try out some stuff and you learn and get better. Then come back to your original task. Don't try the other way round: it's always bad solving problems and THEN learn how you should have solved them ;-) – UniversE Feb 19 '15 at 14:39
  • 1
    cplusplus.com is also a good place to find information about the standard library. E.g. for `fwrite` check this page: http://www.cplusplus.com/reference/cstdio/fwrite/ – Morten Jensen Feb 19 '15 at 15:39
1

Unless you have a guarantee that the three input numbers are all different, I'd worry about making the program get the correct output. As noted, there's almost nothing to speed up, other than input and output buffering, and maybe speeding up decimal conversions by using custom parsing and formatting code, instead of the general-purpose scanf and printf.

Right now if you receive input values a=5, b=5, c=1, your code will report that 1 is the largest of those three values. Change the > comparisons to >= to fix that.

You can minimize the number of comparisons by remembering previous results. You can do this with:

int d;
if (a >= b)
    if (a >= c)
        d = a;
    else
        d = c;
else
    if (b >= c)
        d = b;
    else
        d = c;
[then output d as your maximum]

That does exactly 2 comparisons to find a value for d as max(a,b,c).

Your code uses at least two and maybe up to 4.

Mike Housky
  • 3,959
  • 1
  • 17
  • 31