• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Create triangle of asterisks with StringBuilder in one loop

 
Ranch Hand
Posts: 38
IntelliJ IDE Python Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,
Is it possible to create triangle with one instance of StringBuilder in one loop?
This is example of shape of triangle I am  writing about:


I know it is possible to do it with two loops, but I wish to reduce number of iterations.
 
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, it's possible. You'll need another variable besides your StringBuilder though.
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My solution has 7 lines of code, which includes a separate line for the closing brace of the single for-loop.

EDIT: Actually, now it has only 6 lines of code: there's a way to combine two lines so the for-loop only has one line of code in the body. If you do away with the braces for the single-statement for-loop, then the solution will be 5 lines of code. Not that I'd ever recommend doing away with braces for single-statement for-loops, by the way—that's generally not advisable if you want to keep your code maintainable.

EDIT: Actually, only 4 lines if you use String.repeat() because you won't need that extra variable I mentioned before.
 
Master Rancher
Posts: 4024
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
These days, the body of the solution fits comfortably in one line.  Three with a method declaration and closing brace.  Though a stream-based solution with a small lambda might not be a solution appropriate for Beginning Java.
 
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A Stream‑based solution might be eminently suitable for beginners, but we shall have to make them do it the hard way with a loop (‍) because these exercises are for teaching people how to use loops.
 
Andrzej Zahorski
Ranch Hand
Posts: 38
IntelliJ IDE Python Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:A Stream‑based solution might be eminently suitable for beginners, but we shall have to make them do it the hard way with a loop (‍) because these exercises are for teaching people how to use loops.


I thought about using Stream API, but it is out of scope for explaining it (I am doing it for another person and he just started learning Java) , but  would you mind sharing Stream solution?
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's one:

I formatted into 3 lines of code for readability but it's still just one statement.

That's basically what you do with a for-loop and StringBuilder, too.
 
Andrzej Zahorski
Ranch Hand
Posts: 38
IntelliJ IDE Python Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I got to this point:


But printing every iteration is not efficient, because I am creating multiple Strings in String Pool at this moment I've got no idea how to append it so I will get this inside stringBuilder (example size = 5):
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1. You're agonizing over milliseconds difference in performance. Is that really worth it? Premature optimization is the root of all evil, as Donald Knuth would tell you.

2. Keeping the output separate from the calculation is a better idea. Having a System.out.println() in there smells to me.

3. Did you know about the String.repeat() method? That's going to help a lot, assuming you're using at least JDK 11. Otherwise, you could write your own String repeat(String s) method.
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Andrzej Zahorski wrote:But printing every iteration is not efficient, because I am creating multiple Strings in String Pool


And this is what's evil about premature optimization: you've agonized over the wrong thing. You're not creating multiple Strings in the String pool. For one, objects you create are placed on the heap, even Strings you create on the fly. They only get put in the String pool if you explicitly put them there and you're not doing that so whatever Strings you think you're creating, they're on the heap.

Moreover, all you're doing is appending to the StringBuilder one character at a time. You only have one instance of a StringBuilder so you're not creating multiple objects there and '*' is a literal so. If you're agonizing over calling System.out.println(stringBuilder.toString()) multiple times, then again, you're fretting over nothing. Don't do that to yourself, it's not worth it.
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My own streaming solution was just:

Which is extremely close to what Junilu suggested.  For something more complicated, it might be nice to separate creating the string from printing it - makes it easier to test.  But for this, it seems easy enough to just print it right away and be done.

Incidentally, a traditional non-streaming loop can be even shorter.  But traditionally we are taught that the loop structure needs multiple lines.  While for lambdas, we're often encouraged to put it on one line.  Well, we can really do that with loops to; it needn't be a big deal:

However, writing it like that is often treated as heresy for some reason.
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Building on what Junilu was just saying about premature optimization... worrying about how many lines your code takes is also not generally worth worrying about.  At least not at this level.  But I was playing along with what Junilu himself said earlier about lines of code.  Anyway, we shouldn't focus on that.
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:But I was playing along with what Junilu himself said earlier about lines of code.  Anyway, we shouldn't focus on that.


True that! As I was telling someone in another thread, if you want to write clever code on one line, learn Perl. But then again, if you can make it crisp but still keep it clear, go for it!
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:
However, writing it like that is often treated as heresy for some reason.


Begone, you heathen!    
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's just interesting that using lambdas tends to affect one's view of what should be normal to put on one line.  For me, at least.  I'm perfectly happy doing method chaining an putting each new method call on a new line, as you did in your stream example.  But if it's really short, I'm also fine putting it all in one line.  And the fact that forEach() encourages concise one-liners... makes me look back at the old for loop and wonder, why not?
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:My own streaming solution was just:


This one works, too, just a little bit longer:

 
Bartender
Posts: 4631
182
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
and for the few java < 11 users:
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nice, Piet! I suppose you could also use a method reference there:
 
Piet Souris
Bartender
Posts: 4631
182
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Didn't think of that, but it looks great!
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Who would have thought there were so many ways to build a triangle of stars in Java?
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator



 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . so many ways to build a triangle of stars . . .

There are usually so many ways to do anything.
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is it really premature optimisation to run System.out.println() only once? As we have seen, it is easy enough to create one String and only print it once. When you consider that accessing the terminal may take a few milliseconds whereas the rest of the code probably takes < 1μs, even if I use horrors like +=, I think it is a bit unfair to call it premature optimisation. OK, in this little example, the time taken for printing will be less than the eye can follow, but large applications with hundreds of print calls per second will find them a drag on their performance.Maybe the preceding doesn't count because it uses two string builders.Repeatedly using += is another way to cause slow execution, but you won't notice anything for such a small program. += was optimised in Java9, so the performance problem isn't quite as bad as it was. The repeat() method (Java11+ only) can remove the temptation to use +=, but there is an off by one error in its documentation.
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried some timings with System.nanoTime() on JShell, which told me earnestly it takes 8ms to print the execution time and the stars up to 10 pre per line. It also told me it took nearly 2 hours to create the stars, with two StringBuilders. Maybe I have made a mistake in the arithmetic.
[edit]Second try→6,666 seconds. You could hardly have a worse execution time
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Once I corrected the error, I got about 13μs for the execution time and about 1ms for printing. Less of a difference than I thought, but the printing still takes much more time than the loop.
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My timings for the following code were about 0.2ms, which is slower than a loop. And I am sure the OP was supposed to write a loop as practice.Yes, I used the lineSeparator() method for all cases.
 
Junilu Lacar
Marshal
Posts: 16591
277
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Worrying about a few System.out.printlns in a program this trivial is premature optimization. If you're talking about the difference of hours or even minutes, then maybe we can have a talk about how important it is to make the code more performant. If it's just a few milliseconds we're talking about, well, somebody better be dying otherwise it's just a waste of time.  
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Regarding use of += for String concatenation, the usual reason we would regard that with horror inside a loop is that inside a loop, it would introduces O(N²) performance.  Which is evil, if O(N) is possible.  Of course in this problem, the loop is already O(N²)  because we are asked to print a triangle, copying an increasing number of characters on each iteration through the loop.  The I/O is the slowest part anyway, and however we form the data on each iteration, we have to output O(N²) characters each time.  So use of += for String concatenation really doesn't cause any new problems here.  


 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I did say earlier that nobody would notice the performance handicap caused by +=. I can't remember what the optimisation did, because it is such a long time since I tried it, but a Java9 program with repeated += runs either about 10× or about 100× the speed of the same program on Java8 before the optimisation. I suspect it runs in worse time complexity than n²; when I tried something like this,...I used to be able to see the execution time for n=10,000 and for n=100,000 I could expect several minutes to elapse before I saw any printed output. Every use of += used to entail a new StringBuilder object behind the scenes, and by the time we were into the thousands that necessitated repeated garbage collection cycles. And by that stage, the time for repeated concatenations greatly overwhelmed the time for the IO. I don't even try repeated concatenations any more. Not when there are much faster ways to do it, including StringBuilder#append and String#repeat.
When you have a total of 55 stars to concatenate (sum 0...10inc), the concatenations might change my 13μs to 20μs, which won't be discernible against even 1ms for the IO.

Have just tried multiple concatenation, as above, on JShell (JDK16); the concatenation takes about 34sec for 100,000× and it takes about 2sec for the result to appear on screen(!) When I used to run that sort of abomination on pre‑Java9 versions, and older computers, the loop ran for 10min or 20min.
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I did something daft: ran that loop 1,000,000×; it took about 54½min, which is as near to 100×34sec as makes no difference, so it seems to be big‑O‑n². Anybody know the Unicode number for big‑O? The Unicode site seems to be on a go‑slow just at the moment.
 
Piet Souris
Bartender
Posts: 4631
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Fortunately we get away with a triangle... a parallellogram would take twice the time.    
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Campbell: I'm not sure why you're talking about N=10,000 or N=100,000 for your "CampbellRitchie" example, but only N=55 for the triangle of asterisks.  Performance problems with string concatenation in a loop will always be ignorable for small enough N; the real problems emerge only for some larger N.  My point is that while the CampbellRitchie example can be written in a much more performant way (O(N)) by using a single StringBuilder and repeatedly appending to it, the triangle of asterisks will always be O(N²) even with the fastest possible coding, simply because there are O(N²) asterisks in the triangle.  And all the solutions proposed so far create at least one new String object (of increasing length) on each pass through the loop; the += solutions are no different in that respect.

 
Sheriff
Posts: 26771
82
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Anybody know the Unicode number for big‑O?



The Wikipedia article for Big O notation just uses an ordinary capital O. If it was good enough for Bachmann and Landau it's good enough for me.
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:. . . the CampbellRitchie example can be written in a much more performant way (O(N)) by using a single StringBuilder . . . ,

About 0.5sec to 1sec for 1,000,000 append()s earlier today if I supplied the exact size for the StringBuilder in advance.

the triangle of asterisks will always be O(N²) . . .

Yes, it will run in n² time, But nobody has the patience to look at enough asterisks for the concatenation to exceed the time for IO.
And maybe I should shut up before I say anything even dafter.
 
Mike Simmons
Master Rancher
Posts: 4024
53
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Mike Simmons wrote:the triangle of asterisks will always be O(N²) . . .

Yes, it will run in n² time, But nobody has the patience to look at enough asterisks for the concatenation to exceed the time for IO.


I don't think there's any reason to expect the concatenation time would ever exceed the IO time.  For the triangle of asterisks, both are O(N²).
 
Campbell Ritchie
Marshal
Posts: 73984
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When I tried CampbellRitchieRitchie... with +=, the concatenation seemed to run in n² time. But that was the equivalent of one line. Had I tried that with n lines, each concatenating, it would never finish before my computer packed in run in n³ time. Using an explicit StringBuilder reduces the time per line to linear (n) and the whole triangle would run in n² time.
 
A wop bop a lu bob a womp bam boom. Tutti frutti ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic