aspose file tools*
The moose likes Beginning Java and the fly likes it took too long to execute Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "it took too long to execute" Watch "it took too long to execute" New topic
Author

it took too long to execute

fion bera
Greenhorn

Joined: Nov 17, 2012
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

Joined: Jan 03, 2004
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

Joined: Nov 17, 2012
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
Sheriff

Joined: Sep 28, 2004
Posts: 18116
    
  39

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

Joined: Jan 03, 2004
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?

1. Wrap a BufferedReader around your FileWriter.

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

Joined: Jan 28, 2003
Posts: 3947
    
  17

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).


Steve
fion bera
Greenhorn

Joined: Nov 17, 2012
Posts: 13
thanks for pointing out the bottleneck.
I think I probably have to think of other algorithm
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 3947
    
  17

Steve Luke wrote:...All those strings can be replaced with a single StringBuilder...


Example:
>
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
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

Joined: Jan 28, 2003
Posts: 3947
    
  17

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

Joined: Jan 03, 2004
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: it took too long to execute
 
Similar Threads
HELP~~
Math.Random() query
Fybunic series
Dsplaying the alphabet with a loop?
June Newsletter Puzzle