Can I possibly make this piece of code faster:
I am trying to get a way to implement the divisibility test using bit manipulations but haven't got around it.Code:#include <iostream> int main() { int n, k, read_int, divisible = 0; std :: cin >> n >> k; while (std :: cin >> read_int) { if ((read_int % k) == 0) ++divisible; } std :: cout <<divisible; }
> while (std :: cin >> read_int)
This is an elephant
> if ((read_int % k) == 0)
This is a mouse
> ++divisible;
This is a flea on the mouse.
The I/O operation is monstrously expensive compared to the body of the loop.
Try timing an empty loop, then see how much it increases by when you add the loop body back in.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
It seems to me that the time will be dominated by the input, so you do not have to worry so much about the modulo.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
.
> while (std :: cin >> read_int)
This is an elephant
> if ((read_int % k) == 0)
This is a mouse
> ++divisible;
This is a flea on the mouse.
The I/O operation is monstrously expensive compared to the body of the loop.
Try timing an empty loop, then see how much it increases by when you add the loop body back inHmm, thanks, I see.It seems to me that the time will be dominated by the input, so you do not have to worry so much about the modulo.
Is there any way to get around input bottleneck?
Input is a bottleneck. There is no way to prevent it. The trouble is that it (usually) involves waiting for hardware and/or a person to provide that input.
What can this strange device be?
When I touch it, it gives forth a sound
It's got wires that vibrate and give music
What can this thing be that I found?
Well, yea I mean could I get some speed turbo, using some other technique(It seems like std :: istream in particular is slower compared to other input methods(not that am sure about).I will investigate ;-).
Last edited by Aslaville; 10-17-2014 at 11:21 AM.
Anyway pretty basic stuff:
Input file 10000000 numbers.The first value is the no of numbers and the second is the dividend.
TimeCode:/* test.cc g++ test.cc */ #include <cstdio> int main() { int x, b, k, divisible; scanf("%d", &x); scanf("%d", &b); while(x--) { scanf("%d", &k); if ((k % b) == 0) ++divisible; } printf("%d\n", divisible); }
Code:128312 real 0m0.828s user 0m0.812s sys 0m0.015sTimeCode:/* g++ cin.cc */ #include <iostream> int main() { int n, k, read_int, divisible = 0; std :: cin >> n; std :: cin >> k; while (n--) { std :: cin >> read_int; if ((read_int % k) == 0) ++divisible; } std :: cout <<divisible; }
Code:real 0m2.707s user 0m2.692s sys 0m0.014s
I guess the real question is why you care about the speed of this code in the first place.
It seems to me you're indulging in premature optimisation (any programmer who claims to have never done it is a liar).
Compiler optimisation and debugging settings will often have a significant effect that varies for different I/O methods (as well as between compilers and libraries).
Since your code is reading from stdin and reading user (keyboard) input, the actual run time will be dominated the user - humans are slow like that. If you are redirecting input to come from a file, then the method of redirection will probably be a significant contributor to your various measures of time (what caching is done by the operating system, command shell, etc). And, of course, relative performance of devices on your computer (hard drive versus bus versus CPU etc).
try compiling both with -O3, and see if it changes anything. Much of the iostream portion of the C++ standard library is header-based, and as such, its performance will depend on your level of optimization. The C library is generally a precompiled binary library, and is already optimized when you link it with unoptimized user code.
What can this strange device be?
When I touch it, it gives forth a sound
It's got wires that vibrate and give music
What can this thing be that I found?
Try reimplementing the input part using cstdio functions to see if it is any faster. Sometimes the iostreams library is slower than necessary, so doing this part using cstdio may be significantly faster. Or if you want to use iostreams check this thread for suggestions on speeding it up c++ - Why is istream/ostream slow - Stack Overflow
O_o
Haven't seen this one in a while...
Using a random 10000000 value file and same code from post (#7):
Code:/* CIO */ real 0m0.986s user 0m0.970s sys 0m0.013sCode:/* iostreams */ real 0m2.727s user 0m2.720s sys 0m0.007sSomaCode:/* iostreams without standard mandated sync using `sync_with_stdio' */ real 0m0.679s user 0m0.673s sys 0m0.003s
“Salem Was Wrong!” -- Pedant Necromancer
“Four isn't random!” -- Gibbering Mouther
The absolute fastest way to process some stuff from a file (i.e. with I/O) is just to cache the file in memory and then process the stuff. Every I/O call is expensive. It's ridiculously expensive if it has to transition to kernel mode (i.e. do some actual reading from disk).
[/QUOTE]
This is interesting. So with std::sync_with_stdio(false) iostreams beats cstdio. Which libstdc++ implementation / os?
You should reduce number of I/O operations. Add an array of int's and read your integers into array. You may to experiment with size of array.
For example - if size of your array is 1024, then number of access to kernel will reduce for 1024 times.
P.S. sorry for my english, i just study it
Nevermind, Its not production code, I just stumbled over something that was testing I/O speed :-) and didn't realize until Laserlight and Salem pointed that out.
Last edited by Aslaville; 10-19-2014 at 08:10 AM.
