File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

it took too long to execute

 
fion bera
Greenhorn
Posts: 13
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


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
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20835
75
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 4181
21
IntelliJ IDE Java Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks for pointing out the bottleneck.
I think I probably have to think of other algorithm
 
Steve Luke
Bartender
Pie
Posts: 4181
21
IntelliJ IDE Java Python
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:...All those strings can be replaced with a single StringBuilder...


Example:
>
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 4181
21
IntelliJ IDE Java Python
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic