• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Efficient Nested Iteration over multiple Arrays

 
Fawad Ali
Ranch Hand
Posts: 116
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All:
Forgive me if I am asking a too dumb question. I have three String Arrays containing like 1000 elements each. I want to get all the possible combinations of the three arrays as



Whats the efficient way of doing it?
 
William P O'Sullivan
Ranch Hand
Posts: 859
Chrome IBM DB2 Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's about as efficient as it gets.

WP
 
Fawad Ali
Ranch Hand
Posts: 116
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Really, there is not any other way of doing it? I get Java heap space when I add other calculations into the inner loop.
 
Koen Aerts
Ranch Hand
Posts: 344
Java Linux Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're iterating correctly over the arrays; that's as efficient as that will go. What calculations are you doing that is causing issues? The issue might actually be related to whatever it is you're doing with the calculations, not the array iterating itself.
 
William P O'Sullivan
Ranch Hand
Posts: 859
Chrome IBM DB2 Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
1000 x 1000 x 1000 new Strings will do some serious damage to your heap!

WP
 
fred rosenberger
lowercase baba
Bartender
Pie
Posts: 12102
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Concatenating strings like this is a bad idea. Unless they have changed it, a line like this:

String seriesName = tableNameArray[i] + ":" + databaseNameArray[j] + ":" + accountNameArray[k] ;

will actually cause FOUR strings to be created. It does each "+" sequentially, building intermediate strings as you go. so you get "i:", then "i:j", then "i:j:", then "i:j:k".

since you have arrays that are 1000 elements each, you are creating 4 BILLION new strings. I'm not surprised you are running out of memory.

What is it you need to do with these once you build them? do you really need them all?
 
Koen Aerts
Ranch Hand
Posts: 344
Java Linux Oracle
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I ran a little test. With your original String concatenation I noticed memory usage around 317MB. When I instantiated and re-used a StringBuilder object, memory usage stayed around 8MB and I noticed a huge performance increase, which I assume is related the elimination of instantiating a large amount of String objects and the Garbage Collector kicking in.
 
Matthew Brown
Bartender
Posts: 4567
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You've got 10^9 combinations to try regardless of how you try to loop over them. So it's what you do inside the loop that matters. If you're running out of memory, that's probably because you're allocating some memory within the loop and not releasing it. E.g. creating objects that have a scope beyond the loops. That's one thing you need to focus on. What's the nature of the calculations you're doing?

(The other possibility is finding a more intelligent search approach that doesn't involve checking all combinations, but whether that's possible depends on what you're trying to do).
 
Mike Simmons
Ranch Hand
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
fred rosenberger wrote:Concatenating strings like this is a bad idea. Unless they have changed it, a line like this:

String seriesName = tableNameArray[i] + ":" + databaseNameArray[j] + ":" + accountNameArray[k] ;

will actually cause FOUR strings to be created. It does each "+" sequentially, building intermediate strings as you go. so you get "i:", then "i:j", then "i:j:", then "i:j:k".

I don't think that's correct. The compiler writers would have had to be pretty dense not to optimize this, at least by the turn of the century. I'd be very surprised to find a JDK put out in the last ten years that does this. The compiler can easily avoid creating more than one new string on each execution of this line.

Perhaps you're thinking of what happens when we append to a string inside a loop, like this?

Here the compiler can easily avoid creating more than one string per loop. But it can't avoid that one per line, and when we keep appending to the same base, that's what gets really nasty.

fred rosenberger wrote:since you have arrays that are 1000 elements each, you are creating 4 BILLION new strings. I'm not surprised you are running out of memory.

Well, 1 BILLION. Still a lot.

fred rosenberger wrote:What is it you need to do with these once you build them? do you really need them all?

Yes, this is the real key here. Are you doing something that forces these strings to stay in memory? And can we avoid that?

If we really need to keep the strings around, perhaps they can be written to a file or database instead. That will be slower than memory, but can save the heap from being overrun.

Also, it my be worthwhile to try simply increasing the heap size using the -Xmx flag. Try something like "java -Xmx1G MyProgram" to start the program.

Of course it would be much better to remove the overuse of memory, if possible.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Mike Simmons wrote:
fred rosenberger wrote:Concatenating strings like this is a bad idea. Unless they have changed it, a line like this:

String seriesName = tableNameArray[i] + ":" + databaseNameArray[j] + ":" + accountNameArray[k] ;

will actually cause FOUR strings to be created. It does each "+" sequentially, building intermediate strings as you go. so you get "i:", then "i:j", then "i:j:", then "i:j:k".

I don't think that's correct.


It's not. That gets turned into calls to StringBuilder.append(). (I don't think it's required by the spec, but that's what any mainstream compiler does.) It's str += stuff; in a loop (or the equivalent thereof) that can get expensive and wasteful.
 
Campbell Ritchie
Sheriff
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I notice that local variable is re-declared every time the loop runs. So it will go out of scope and become available for garbage collection. In fact that entire loop as written does nothing.

In fact what was written is a block containing nothing but a declaration and initialisation. Does that even compile?
 
Mike Simmons
Ranch Hand
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It compiles, sure. It gets a warning from IntelliJ, probably from Eclipse as well, complaining the variable is unused. But as the original poster said:
I get Java heap space when I add other calculations into the inner loop.

These "other calculations" are, thus far, not shown. We've indicated we'd like to know more, since they are the key to understanding the problem he's having. Probably he's doing something which causes the strings to be retained in memory somewhere.
 
Fawad Ali
Ranch Hand
Posts: 116
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you all for your replies. What I actually do inside is as under




While addColor() is




And the convertToHtmlCode is



I guess, I will have to use StringBuilder and will try to make the functionality further efficient.
 
Campbell Ritchie
Sheriff
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is bound to be a better way to convert an int into a hex String. For a start, you can convert the number to a hex string directly, without dividing it into RGB. Try getting the so-called RGB with the Color#getRGB() method, and doing a bitwise and with 0x00ffffff as a mask. That will get rid of the alpha and reduce it to six digits.
What about something like String.format("%06x", myColour.getRGB() & 0x00ffffff)? You can add things like # or #0x to the format String. The & operator has a higher precedence than the comma.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic