-3

I was wondering how i can minimize the runtime of the following code

int j = 0;    
while (j < n) {
    int i = 0;    
    while (i < m) {
        cout << i*j;
        i++;
    }
    j++;
}
momo
  • 23
  • 1
  • 8
  • What is n and m? Is there any constraint like e.g. n < m or so? – Lucia Pasarin Apr 26 '15 at 09:44
  • @Dici - *I* know that but... – ChiefTwoPencils Apr 26 '15 at 09:44
  • Could it be that this is a homework question? What have you tried so far, and what tool do you use to measure the runtime? Also, it would be helpful to know the size of `n`. – Martin J.H. Apr 26 '15 at 09:45
  • I run it using online compiler it keeps giving me ((Runtime error )) ... I was wondering why ... it takes O(n*m) time ... i can use any programming language ,, such as java or c# whatever ,,, the problem is why it takes more than 5sec ... how I can minimize that .. and no it isn't a homework .. I am still learn how build algorithms with minimum time complexity – momo Apr 26 '15 at 09:53
  • any, m and n ... in general .. if I have two nested for loops or while how I can minimize the time ? – momo Apr 26 '15 at 09:54
  • Depending on the compiler, switching from cout to printf may help performance. See http://stackoverflow.com/questions/1736267/c-cout-printing-slowly – Adam Apr 26 '15 at 11:11

1 Answers1

0

There's not much to do, these are just mere loops. However, it is usually more efficient to accumulate the strings and print at the end than printing tiny strings several times.

Dici
  • 25,226
  • 7
  • 41
  • 82
  • how I can do that with single loop ... I dnt get it – momo Apr 26 '15 at 09:58
  • You can't, the complexity is `O(n*m)` no matter what. – Dici Apr 26 '15 at 09:59
  • I was wondering if i convert it to greedy programing or memoization maybe these approaches would make it with polynomial time like in greedy it always takes O(m+n) but I dnt know how to convert it to greedy – momo Apr 26 '15 at 10:03
  • I told why it is slow : printing something to the console is much slower than a single iteration in your nested loops, therefore you must accumulate the result and print it in the end – Dici Apr 26 '15 at 10:03
  • @majdsoud yes you can, but that's not how I understood your question. This is not only changing the code, this is changing the algorithm – Dici Apr 26 '15 at 10:05
  • ok I will try to print it at once and check the time .. thanks – momo Apr 26 '15 at 10:06
  • Tested with `std::ostringstream` as a buffer and there's no significant difference. Use files for such large dump. – LogicStuff Apr 26 '15 at 10:06
  • yes .. changing an algorithm to get the best time ,, cause I already know how it works but trying to make the best time optimization – momo Apr 26 '15 at 10:12
  • I just verified it takes (on my machine) ~1.50x more nano seconds with nested loops vs. a single loop using Java (of course) ;). @majdsoud – ChiefTwoPencils Apr 26 '15 at 10:19
  • Chief Two Pencils ... how i can convert it to single loop ? – momo Apr 26 '15 at 10:25
  • @majdsoud, consider what it's doing. `j` is the same for the entire iteration against `m`; dead give-away. Basically the entire outer loop is replaced by an if nested in an if in the loop over `m`- same number of lines of code. Worth it I suppose if you're worried about 0.16 ms. – ChiefTwoPencils Apr 26 '15 at 10:34
  • @ChiefTwoPencils man I really don't see what you are talking about. He has `n*m` numbers to print, it is `n*m` computations no matter how you write it. Concerning memoization, it would actually change almost nothing because such a small multplication is not much slower than an addition – Dici Apr 26 '15 at 10:47
  • Chief Two Pencils .. it gives me an infinite loop :( – momo Apr 26 '15 at 10:58
  • @Dici i think greedy will make it n+m but have no idea how to do that – momo Apr 26 '15 at 11:01
  • @majdsoud what do you mean by greedy ? Really, I tell you, there's no way to significantly boost such a simple computation. The only reasonible optimization is to write to the console **only once** instead of each iteration – Dici Apr 26 '15 at 11:03
  • greedy algorithm approach ... you can search about it ... i will try ti print it once and give u the feedback thank you – momo Apr 26 '15 at 11:06
  • I know what is a greedy algorithm, but it has nothing to do with this. A greedy algorithm is an algorithm which tries to optimize a given metric at each step of the algorithm. You are not optimizing a metric here – Dici Apr 26 '15 at 11:09
  • All I can say is in my experience simple loops like these average out to be faster if the outer is removed. That may be language or paradigm specific though. What I know is of 100,000 tests ~41% of the time the nested ran faster. But when it did it was even *more* negligible than when the single was faster. In the end the single was 10% faster on average. If it was an algo that ran 24/7/365 the nanos would add up (obviously) and it might be worth it. However, such a micro optimization, if you can call it that since it *may* not run faster for a given iteration, is nit-picking. – ChiefTwoPencils Apr 26 '15 at 19:50
  • Ultimately though I think saying m*n no matter what is true but neglecting things we have no control over. Taking the complexity of an algorithm is a bound not an exact account. – ChiefTwoPencils Apr 26 '15 at 19:55