aspose file tools*
The moose likes Beginning Java and the fly likes Efficient Nested Iteration over multiple Arrays Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Efficient Nested Iteration over multiple Arrays" Watch "Efficient Nested Iteration over multiple Arrays" New topic
Author

Efficient Nested Iteration over multiple Arrays

Fawad Ali
Ranch Hand

Joined: Dec 28, 2009
Posts: 112
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?

Regards, Fawad Ali.
Software Engineer, Stafona Inc. - My Blog
William P O'Sullivan
Ranch Hand

Joined: Mar 28, 2012
Posts: 859

That's about as efficient as it gets.

WP
Fawad Ali
Ranch Hand

Joined: Dec 28, 2009
Posts: 112
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

Joined: Feb 07, 2012
Posts: 344

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

Joined: Mar 28, 2012
Posts: 859

1000 x 1000 x 1000 new Strings will do some serious damage to your heap!

WP
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11406
    
  16

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?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Koen Aerts
Ranch Hand

Joined: Feb 07, 2012
Posts: 344

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

Joined: Apr 06, 2010
Posts: 4421
    
    8

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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Oct 13, 2005
Posts: 39396
    
  28
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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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

Joined: Dec 28, 2009
Posts: 112
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

Joined: Oct 13, 2005
Posts: 39396
    
  28
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Efficient Nested Iteration over multiple Arrays