2

I am attempting the following SPOJ problem. I'd like to clarify that I do not need solution for this problem which is why I have not tagged this question as 'algorithm'.

Multiply the given numbers. 

Input
n [the number of multiplications <= 1000]
l1 l2 [numbers to multiply (at most 10000 decimal digits each)]

Output
The results of multiplications.

Time Limit: 2 seconds.

I have a naïve solution O(n^2) which is the way we were taught in school (read input as string and do character-wise multiplication). I know I can optimize it further through Karatsuba method.

Question: My present code is in C++. I have read on the internet that reading through scanf is faster than cin. Given the input size is so large, does it make a significant difference in such cases?

Given a choice I would not like to mix C with C++, so any ideas on how I can improve my input streaming shall be very helpful.

Thanks

Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • 1
    The thing to remember that the problems on sites like SPOJ are very seldom applicable to real-world problems. And that to successfully make programs for these site you have to make some "hacks" that will be looked down upon if used in real-world applications. – Some programmer dude Oct 28 '13 at 07:26
  • 1
    As for this specific case, are you sure it's the input that's the bottleneck, and not the actual calculations? – Some programmer dude Oct 28 '13 at 07:28
  • Relevant: [Fast text-file reading in C++](http://stackoverflow.com/a/17925143/85371) and [How to parse space-separated floats in C++ quickly?](http://stackoverflow.com/questions/17465061/how-to-parse-space-separated-floats-in-c-quickly/17479702#17479702) – sehe Oct 28 '13 at 07:30
  • @JoachimPileborg Honestly, I'm not sure about that. However, I posted this question to help me for future reference as well. – Abhishek Bansal Oct 28 '13 at 07:30

3 Answers3

4

Use sync_with_stdio:

cin.sync_with_stdio(false);

This will turn off synchronization with cstdio stream and will improve the speed.

Demo

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
falsetru
  • 357,413
  • 63
  • 732
  • 636
  • I am interested to see if this works for someone else, because it has never seemed to make a difference for me. – Paul Draper Oct 28 '13 at 07:27
  • @falsetru: note, your screencast does not demonstrate much because of caching effects. The first time a file is read is always slower (not in cache yet). For a complete demonstration you would need to alternate the measures between with/without a couple times and then take the median or best of each category and compare those. *OT: nice tool!* – Matthieu M. Oct 28 '13 at 08:24
  • @MatthieuM., Thank you for comment and correction. BTW, I ran multiple times with the same input file before I recorded. – falsetru Oct 28 '13 at 08:27
  • @falsetru: good :) Then caching should not have affected the result! – Matthieu M. Oct 28 '13 at 08:29
  • see also https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull – Jonas Stein Dec 06 '19 at 22:45
0

While I would never give a blanket statement of performance, on SPOJ (particularly with the Pyramid cluster) I have noticed significant differences between cin and scanf.

I would use scanf if you think I/O is limiting you.

And don't disregard something just because it is available in C (that would be quite a few things!)

Paul Draper
  • 78,542
  • 46
  • 206
  • 285
-1

scanf() and printf() can be used in C++ too. It's not going to mix C with C++.
Just include the <cstdio> header file.

And of course scanf() and printf() is a lot faster than cin and cout respectively.

aniskhan001
  • 7,981
  • 8
  • 36
  • 57
  • 1
    Yes, it will mix C and C++ (remember, their standard libraries are part of the language specs). In particular, not using `sync_with_stdio` (as the other answer rightly suggests) will lead to undeterministic results, because of that. – sehe Oct 28 '13 at 07:31
  • As C++ library includes all of the header files of C library, so we can use them with C++. Yeah, in this case that's a mix. – aniskhan001 Oct 28 '13 at 07:39
  • To be clear, I didn't say you "can't mix". You can. Your answer, however, falsely claims "this is not going to mix". – sehe Oct 28 '13 at 08:05
  • The problem is not so much using `scanf` or `printf` but rather using `scanf` and `std::cin` OR `printf` and `std::cout`/`std::cerr`. In general the C and C++ libraries have **independent** buffers, thus leading to strange results if they are not sync'ed together (controlled via `sync_with_stdio`). – Matthieu M. Oct 28 '13 at 08:21