10 Replies - 7735 Views - Last Post: 31 October 2008 - 03:23 PM Rate Topic: -----

#1 wingman358  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-November 05

Nested loops & efficiency(?)

Posted 21 May 2006 - 06:40 PM

I'm eventually going to be using the following code to generate all possible 5-digit combinations of 0-9 and A-Z. Obviously, when you're using many nested loops, it takes a while to execute the code. So I've been wondering A) how can I make the code more efficient B) can I dedicate more system resources to the execution and C) is there a way to have the program run in such a way that it doesn't try to execute instantaneously, but over a longer period of time? Basically, how can I have a lot of nested loops without worrying about the computer locking up when I execute the code?

public class Main
{
	 public static void main(String[] args)
	 {
//	 String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	 double count=0;
	 
	 for(int a=0; a<36; a++)
				for(int b=0; b<36; b++)
		 		   for(int c=0; c<36; c++)
						  for(int d=0; d<36; d++)
								 for(int e=0; e<36; e++)
											count++;

	 System.out.println("\n\n"+count);
	 }
}


Is This A Good Question/Topic? 0
  • +

Replies To: Nested loops & efficiency(?)

#2 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Nested loops & efficiency(?)

Posted 21 May 2006 - 09:25 PM

I don't know about you, but my comp doesn't lock on loops the JVM usually handles that kind of thing.
But there are a few things you can do:
use recursion and a couple for loop should be enough, the first would rotate the letters eg: ( hello -> elloh -> llohe...)
hopefully you see where i'm going with this, it will also allow you to handle more than just 5 letter words, but any length
Was This Post Helpful? 0
  • +
  • -

#3 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Nested loops & efficiency(?)

Posted 22 May 2006 - 01:28 PM

I think that your problems are based on the fact, that you are writing to the standard output. It needs lots of synchronization (if inside the IDE, it even puts a large amount of data into a text component, that makes it even slower). So simply write your results into a file with a buffering writer, and it will be at least 10-times faster. Aslo, compiling a release build, and running it ouside the IDE will increase the performance significantly.
I would suggest to be careful about recursion, as it introduces the overhead of function calls (stack usage, etc.). However in some cases it might still end up faster, if you use it well.
If you really experience lock ups, you might try setting the priority of the working thread lower. I think it only makes a diference, if the same JVM runs several threads. If something outside of the JVM locks up, try to put little sleeps into the thread - or if it is only for your personal usage, simply lower the priority of the JVM.
Was This Post Helpful? 0
  • +
  • -

#4 wingman358  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-November 05

Re: Nested loops & efficiency(?)

Posted 22 May 2006 - 02:47 PM

Thanks for the replies guys. B)

@1lacca: I thought about outputting to a file at first, but I've never been good at that so put it off til later. I didn't know that outputting to a file would make it faster, but that makes sense now cause it uses a buffered writer.

I also considered compiling a release build so I don't have to run it throught the IDE, but I've never done that. I'm gunna try outputting to a file first and then I'll see what I can figure out with a release compile. Would you be willing to help if I run into trouble?

Thanks!!!
Was This Post Helpful? 0
  • +
  • -

#5 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: Nested loops & efficiency(?)

Posted 22 May 2006 - 09:31 PM

you don't have to use a file, i would suggest a vector or array, the size can be found very easily at runtime, then all the data is passed in RAM and never involves the standard IO OR hard disk, two of the slowest transfers in a computer.
Was This Post Helpful? 0
  • +
  • -

#6 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Nested loops & efficiency(?)

Posted 23 May 2006 - 01:11 AM

Yes, if it's part of a bigger "plan" and you are going to further process the outcome, then storing them in an array is definitely the best way! However if it's only for the generation of this data, then I think it's an overkill and the BufferedWriter (with a big enough buffer) is more efficient (both memory and performance wise ). The main problem was in this case the synchronization overhead of the console. Actually as I see he is only writing out the count, so just writing out the final one, or every 100th would solve the problem, too...

A little help:
Creating a writer:
BufferedWriter bw = new BufferedWriter(new FileWriter("foo.out"));
writing:
bw.write("blabla");
Closing:
bw.close();
It's not that difficult :)
Was This Post Helpful? 0
  • +
  • -

#7 wingman358  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 06-November 05

Re: Nested loops & efficiency(?)

Posted 27 May 2006 - 04:20 PM

Alright well I finally got around to working on this program again and I now have it so it ouputs to a file:
import java.io.*;

public class Main
{
	 public static void main(String[] args)
	 {
	 try
	 {
	 BufferedWriter out = new BufferedWriter(new FileWriter("output.dat", true));

	 String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	 		   
	 for(int k=0; k<10; k++)
	 {	 
	 for(int l=0; l<10; l++)
	 {	 
	 for(int m=0; m<10; m++)
	 {	 
	 for(int n=0; n<10; n++)
	 {	 
	 for(int o=0; o<10; o++)
	 {

	 for(int p=0; p<10; p++)
	 {	 
	 for(int q=0; q<10; q++)
	 {	 
	 for(int r=0; r<10; r++)
	 {	 
	 for(int s=0; s<10; s++)
	 {	 
	 for(int t=0; t<10; t++)
	 {
		  
			  out.write(chars.charAt(k));
		  out.write(chars.charAt(l));
		  out.write(chars.charAt(m));
		  out.write(chars.charAt(n));
		  out.write(chars.charAt(o));

		  out.write(chars.charAt(p));
		  out.write(chars.charAt(q));
		  out.write(chars.charAt(r));
		  out.write(chars.charAt(s));
		  out.write(chars.charAt(t)+"\n");
	 
		 }}}}}
		 }}}}}
	 out.close();
	 }
	 catch (IOException e)
	 {
	 }
	 }
}



When I run this, my IDE (NetBeans 5.0) will hang at "compile: " and will then ask for an input, which of course, I dont have. However, if I comment out loops K-O, it will compile and run fine. The file contains the output just as I want it. Got any suggestions?
Was This Post Helpful? 0
  • +
  • -

#8 1lacca  Icon User is offline

  • code.rascal
  • member icon

Reputation: 44
  • View blog
  • Posts: 3,822
  • Joined: 11-August 05

Re: Nested loops & efficiency(?)

Posted 28 May 2006 - 04:29 AM

I am not sure what could be wrong, as I have pasted your code into an empty project, and it is running fine (it finished in 1 minute and 33 seconds as I am answering right now) - I used NetBeans 5.0, too.
Was This Post Helpful? 0
  • +
  • -

#9 bmnpls  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 31-October 08

Re: Nested loops & efficiency(?)

Posted 31 October 2008 - 12:30 PM

I know this is really old, but there's a much, much easier way to get the number of combinations that a 5-deep loop. To generate all the permutations, all you have to do is multiply the number of options the length of string times. Or: numchars ^ strlen = numperms.

To be precise, the value you're looking for is: 60466176 (which, by the way, when I ran your code I did not get because you were using doubles, which are both slower and less precise than integers) which can be very easily generated by power(36,5). Note that I don't use Math.pow, because Math.pow returns a double, which is has the same imprecision problem I mentioned before, so you'll want to roll your own integer power function.
Was This Post Helpful? 0
  • +
  • -

#10 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Nested loops & efficiency(?)

Posted 31 October 2008 - 01:12 PM

A) how can I make the code more efficient
B) can I dedicate more system resources to the execution and
C) is there a way to have the program run in such a way that it doesn't try to execute instantaneously, but over a longer period of time?

Sounds like someone's trying to execute a distributed brute force attack on breaking passwords.. :P
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5901
  • View blog
  • Posts: 12,805
  • Joined: 16-October 07

Re: Nested loops & efficiency(?)

Posted 31 October 2008 - 03:23 PM

You can do this pretty simply with recursion. This will find all permutations of a given collection of symbols.
public void findAllResults(Writer writer, String symbols, String s, int size) 
		throws IOException
{
	if (size==0) {
		writer.write(s + "\n");
	} else {
		for(int i=0; i<symbols.length(); i++) {
			findAllResults(writer, symbols, s + symbols.charAt(i), size - 1);
		}
	}
}

public void findAllResults() {
	try {
		BufferedWriter writer = new BufferedWriter(new FileWriter("output.dat", true));
		findAllResults(writer, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ", "", 10);
		writer.close(); 
	} catch(IOException e) {
		e.printStackTrace();
	}
}




The real issue is scale. Finding all four letter strings with the above code will give 1,679,616 (36*36*36*36) results. For the ten letters it's slightly worse: 3,656,158,440,062,976. If you want all three letters, then all four, etc, you get to add all that up.

If the goal is nefarious, like a dictionary attack, it can take some time. In some cases that time is measured in years. So, well, good luck with that. ;)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1