Effectively print a long sequence

Question

I've to print a number which is a huge sequence of 5's and 3's (upto 100,000 ints). Instead of storing it in array, I just kept their count in noOfThrees and noOfFives.

For simplicity call this number x. .

Since I have to print the largest number in the sequence, x will be initially 5's and then followed with 3's (I have working logic to print if there's no 5's or no 3's)

To print the number, I am using a for loop like this :

for(int i=0; i<noOfFives; i++) 
    System.out.print(5);
for(int i=0; i<noOfThrees; i++)
    System.out.print(3);

But if x is a 100,000 long int number, it takes about 4-5sec to print it on console which is not desirable.

My take:

If the noOfFives is even, then print 55 in the for loop which increases the performance by x2 and increment the loop by two, else
Use the same for loop as above. Same goes for noOfThrees.

But the problem here is if it's odd, it will again end up printing in steps of 1. How do I effectively print this sequence?

What practical use does this have? Why do you need it to be faster? — Andy Turner, Nov 04 '15 at 07:16
@AndyTurner I'am solving a challenge on online judge which causes timeout if execution time is >4sec — Mayur Kulkarni, Nov 04 '15 at 07:17
what about a [BitSet](http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html) instead of a simple `int`? — SomeJavaGuy, Nov 04 '15 at 07:17
If it is being judged online, it's not really printing to a console. Since you aren't flushing, your output will be buffered; as such, writing in larger chunks won't make much difference. — Andy Turner, Nov 04 '15 at 07:19
@AndyTurner when I print it on my machine, it takes around 4-5sec, I believe that's what is causing timeout, since it pases all test cases, and causes timeout on others. — Mayur Kulkarni, Nov 04 '15 at 07:21
How long does it take to run if you pipe the output to /dev/null? — Andy Turner, Nov 04 '15 at 07:22
Possible duplicate of [What's the fastest way to output a string to system out?](http://stackoverflow.com/questions/11823095/whats-the-fastest-way-to-output-a-string-to-system-out) — Ken Geis, Nov 04 '15 at 07:32
You can try [Apache StringUtils](https://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/StringUtils.html#leftPad%28java.lang.String,%20int,%20char%29) to pad with 5 and 3, instead of looping though them. — Viorel, Nov 04 '15 at 07:26

Andy Turner · Accepted Answer · 2016-12-26T15:24:00.437

4

If you think that the number of print calls is the issue, you could reduce it to just 1: put the right number of 3s and 5s into a char array, then print that:

char[] cs = new char[noOfFives + noOfThrees];
Arrays.fill(cs, 0, noOfFives, '5');
Arrays.fill(cs, noOfFives, cs.length, '3');
System.out.print(cs);

edited Dec 26 '16 at 15:24

answered Nov 04 '15 at 07:27

Andy Turner

137,514
11
162
243

score 1 · Answer 2 · edited May 23 '17 at 12:33

Your question seems a bit strange - I wonder whether the logical way to make your code faster is to look elsewhere at how these values are calculated.

However I think it would significantly increase your performance to first build the string in memory and then print it.

I also think you should look at Why is printing "B" dramatically slower than printing "#"? which might shed some interesting light on your issue.

score 0 · Answer 3 · edited Dec 26 '16 at 14:49

0

I think you can use loop unrolling, it can reduce execute time of loop.
for example:

    for(int i=0; i<noOfFives; i+=5) {
        System.out.print(5);
        System.out.print(5);
        System.out.print(5);
        System.out.print(5);
        System.out.print(5);
    }

For more details look at https://en.wikipedia.org/wiki/Loop_unrolling

edited Dec 26 '16 at 14:49

Kenly

24,317
7
44
60

answered Nov 04 '15 at 07:23

He Yuntao

86
11

1

In all likelyhood the number of `System.out.print` is the problem, not the number of loops. – Keppil Nov 04 '15 at 07:24

Effectively print a long sequence

3 Answers3