Efficient Nested Iteration over multiple Arrays

[Fawad Ali]

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

		for (int i = 0; i < tableNameArray.length; i++) {
			for (int j = 0; j < databaseNameArray.length; j++) {
				for (int k = 0; k < accountNameArray.length; k++) {
					String seriesName = tableNameArray[i] + ":" + databaseNameArray[j] + ":" + accountNameArray[k] ;
				}

			}
		}

Whats the efficient way of doing it?

[William P O'Sullivan]

That's about as efficient as it gets.

WP

[Fawad Ali]

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]

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]

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

WP

[fred rosenberger]

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]

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.

StringBuilder sb = new StringBuilder(100);
for (int i = 0; i < tableNameArray.length; i++) {
    for (int j = 0; j < databaseNameArray.length; j++) {
        for (int k = 0; k < accountNameArray.length; k++) {
            sb.delete(0, sb.length());
            sb.append(tableNameArray[i]).append(":").append(databaseNameArray[j]).append(":").append(accountNameArray[k]);
        }
    }
}

[Matthew Brown]

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]

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?

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

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]

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]

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]

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]

Thank you all for your replies. What I actually do inside is as under

for (int i = 0; i < tableNameArray.length; i++) {
			for (int j = 0; j < databaseNameArray.length; j++) {
				for (int k = 0; k < accountNameArray.length; k++) {
					String seriesName = tableNameArray[i] + ":" + databaseNameArray[j] + ":" + accountNameArray[k];
					jsonDataObject.getSeriesList().add(seriesName);
					jsonDataObject.getColorsList().add(addColor(seriesName, colorsMap));
				}

			}
			System.out.println("loop" + i);
		}

While addColor() is

public String addColor(String seriesName, Map<String, String> colorsMap) {//If a series exists in color map,  
                                                           // retrieve its color from map otherwise create color for the series
		String colorValue = null;
		if (colorsMap.get(seriesName) == null) {
			Random numGen = new Random();
			Color color = new Color(numGen.nextInt(256), numGen.nextInt(256), numGen.nextInt(256));
			colorValue = this.convertToHtmlCode(color);
			colorsMap.put(seriesName, colorValue);
		} else {
			colorValue = colorsMap.get(seriesName);
		}
		return colorValue;
	}

And the convertToHtmlCode is

	private String convertToHtmlCode(Color c) {
		StringBuilder sb = new StringBuilder();
		sb.append("#");

		if (c.getRed() < 16)
			sb.append('0');
		sb.append(Integer.toHexString(c.getRed()).toUpperCase());

		if (c.getGreen() < 16)
			sb.append('0');
		sb.append(Integer.toHexString(c.getGreen()).toUpperCase());

		if (c.getBlue() < 16)
			sb.append('0');
		sb.append(Integer.toHexString(c.getBlue()).toUpperCase());

		return sb.toString();

	}

I guess, I will have to use StringBuilder and will try to make the functionality further efficient.

[Campbell Ritchie]

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.