Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# it took too long to execute

fion bera
Greenhorn
Posts: 13

the code took too long to execute and I can't add to 20 for loop. Any suggestion on how to improve this? Thanks in advanced!

Jeff Verdegan
Bartender
Posts: 6109
6
First, stop and think for a minute about why it's taking so long. By my count you've got 12 nested loops, each one executing 4 iterations. I hope you can see that this means you'll be doing 4^12 operations. That's 16,777,216 unbuffered file appends. So, yeah, I wouldn't be surprised if it's taking a little while.

As for finding another approach, what are you actually trying to accomplish?

fion bera
Greenhorn
Posts: 13
Jeff Verdegan wrote:First, stop and think for a minute about why it's taking so long. By my count you've got 12 nested loops, each one executing 4 iterations. I hope you can see that this means you'll be doing 4^12 operations. That's 16,777,216 unbuffered file appends. So, yeah, I wouldn't be surprised if it's taking a little while.

As for finding another approach, what are you actually trying to accomplish?

I am trying to create a file with 4^20. the output file will be used to compare with a file "abcdabcdabcdbabbcdbbabcdbbcbdbcbbbdbcbbcbbbcbbbabababbababababbabababababbbabababbabababbcdbcbbcbcbdbbcbcbcb" that produce another 20 alphabet combination(a, b, c,d only) file for every frame. Then to find out which 20 alphabet combination is not there.

Henry Wong
author
Marshal
Posts: 21744
85
fion bera wrote:
Jeff Verdegan wrote:First, stop and think for a minute about why it's taking so long. By my count you've got 12 nested loops, each one executing 4 iterations. I hope you can see that this means you'll be doing 4^12 operations. That's 16,777,216 unbuffered file appends. So, yeah, I wouldn't be surprised if it's taking a little while.

As for finding another approach, what are you actually trying to accomplish?

I am trying to create a file with 4^20. the output file will be used to compare with a file "abcdabcdabcdbabbcdbbabcdbbcbdbcbbbdbcbbcbbbcbbbabababbababababbabababababbbabababbabababbcdbcbbcbcbdbbcbcbcb" that produce another 20 alphabet combination(a, b, c,d only) file for every frame. Then to find out which 20 alphabet combination is not there.

(4 ^ 20) is more than a trillion iterations. And each iterations has more that 13 (actually now) 21 method calls (keeping the pattern) which adds 13 21 bytes to the file. So... more than 13 21 trillion method calls to generate a file that is more than 13 21 TB is size.

So... to improve this? I recommend putting it on a really high speed I/O device to a really large disk (as that is probably your bottleneck).

Henry

Jeff Verdegan
Bartender
Posts: 6109
6
fion bera wrote:
I am trying to create a file with 4^20.

I don't think I even want to know why. And I don't know if that will even be possible in a reasonable amount of time. I don't feel like doing any more math right now.

Here are a few possibilities. I would expect the BufferedReader to have the biggest impact, but who knows?

2. Unroll your innermost loop or two. I doubt that will help much, as the JVM is probably already doing that.

3. One thread to generate the combinations and another to write them out to the disk. I doubt this will help though, as you're probably mainly I/O bound. This may actually slow it down.

4. You could get fancier with the multitasking, running pieces on multiple computers or multiple processes on one computer, then combining the results at the end, or running your searches in parallel on the multiple computers where the combos were generated. The multiple computer approach will almost certainly help more than the multiple process approach. Multiple processes on a single computer might actually slow it down.

Steve Luke
Bartender
Posts: 4181
22
Also play with object creation. When you do the file IO you are concatenating a lot of strings together. All those strings can be replaced with a single StringBuilder. When I do this on your code (everything else the same) I can cut the execution time in half (literally (11.5s to run your code 5.0s to run with a single StringBuilder). I compared output and they are the same (as long as we add a flush and close to your file writer - at the end of the method, not in the loop).

fion bera
Greenhorn
Posts: 13
thanks for pointing out the bottleneck.
I think I probably have to think of other algorithm

Steve Luke
Bartender
Posts: 4181
22
• 1
Steve Luke wrote:...All those strings can be replaced with a single StringBuilder...

Example:
>

Jeff Verdegan
Bartender
Posts: 6109
6
Steve Luke wrote:Also play with object creation. When you do the file IO you are concatenating a lot of strings together. All those strings can be replaced with a single StringBuilder.

You mean this?

That does use StringBuilder.

Steve Luke
Bartender
Posts: 4181
22
Yes, but it uses lots of them - one for each inner-most loop. You only need one for the entire method.

Jeff Verdegan wrote:You mean this?

That does use StringBuilder.

Jeff Verdegan
Bartender
Posts: 6109
6
Steve Luke wrote:Yes, but it uses lots of them - one for each inner-most loop. You only need one for the entire method.

Ah, I see now. Didn't realize what you were getting at.