Power By 专否社区

Is there a way to speed up a recursion with many loops?

Go To StackoverFlow.com

4

I'm basically trying to play with recursions and created a small program that finds all the combinations from 0-10 of 10 items({1 apple, 0 grapes}, {2 apple, 0 grapes}, {0 apple, 1 grapes}, etc..) .

import java.util.Arrays;
import java.util.List;

public class main {

    public static void main(String[] args) {
        System.out.println("Starting..");
        long startTime = System.currentTimeMillis();
        List<Integer> list_to_start = Arrays.asList(new Integer[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 
        String[] name_of_list_to_start = new String[] {"Grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};       
        System.out.println(list_to_start.size());
        counter(list_to_start.size(), list_to_start, name_of_list_to_start);
        long endTime = System.currentTimeMillis(); 
        System.out.println("Total execution time: " + (endTime-startTime));
    }

    private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start) {
        // If we've gone through everything then return the results
        if (length == 0) {
            for (int i = 0; i<list_to_start.size(); i++) {
                //System.out.println(name_of_list_to_start[i] + " = " + list_to_start.get(i));
            }
            //System.out.println("****");
            return;
        }   
        //This part basically increments list_to_start and then the above part displays it.
        for (int i = 0; i<=10; i++) {
            if (length != 0 ) {
                list_to_start.set((length-1), i);
                counter((length-1), list_to_start, name_of_list_to_start);
                list_to_start.set((length-1), 0);
            }
        }
    }
}

Right now it has 10,000,000,000 loops(10^10) so I understand why it takes long, but I'm wondering is there any Java or algorithm tricks I can use to reduce the number of loops to speed it up?

I've thought of using threading/multiprocessing but the same number of loops will still need to happen which will still take a long time. I'm not sure if there's any data structures, sorting algorithms or caching algorithms that could be employed here. or can I add the results to an array in parallel and then bring them together for the final results? I'm not familiar with any other existing approaches so any suggestions of language specific tricks or algorithm solutions are very welcomed.

Update: To clarify what I'm doing and the performance I'll post a few examples. To increase processing time, simply add/remove zeros to list_to_start(results below are in miliseconds):

1 zero = 0 
2 zero = 1
3 zero = 1
4 zero = 29
5 zero = 37
6 zero = 115
7 zero = 345
8 zero = 1517
9 zero = 23738 (23 seconds)
10 zero = over 30 min. I gave up.

The output(which I disabled to make it run a bit faster) is this for 2 variables(the above code is running 10):

Grapes = 0
Strawberries = 0
****
Grapes = 1
Strawberries = 0
****
Grapes = 2
Strawberries = 0
****
Grapes = 3
Strawberries = 0
****
Grapes = 4
Strawberries = 0
****
Grapes = 5
Strawberries = 0
****
Grapes = 6
Strawberries = 0
****
Grapes = 7
Strawberries = 0
****
Grapes = 8
Strawberries = 0
****
Grapes = 9
Strawberries = 0
****
Grapes = 10
Strawberries = 0
****
Grapes = 0
Strawberries = 1
****
Grapes = 1
Strawberries = 1
****
Grapes = 2
Strawberries = 1
****
Grapes = 3
Strawberries = 1
****
Grapes = 4
Strawberries = 1
****
Grapes = 5
Strawberries = 1
****
Grapes = 6
Strawberries = 1
****
Grapes = 7
Strawberries = 1
****
Grapes = 8
Strawberries = 1
****
Grapes = 9
Strawberries = 1
****
Grapes = 10
Strawberries = 1
****
Grapes = 0
Strawberries = 2
****
Grapes = 1
Strawberries = 2
****
Grapes = 2
Strawberries = 2
****
Grapes = 3
Strawberries = 2
****
Grapes = 4
Strawberries = 2
****
Grapes = 5
Strawberries = 2
****
Grapes = 6
Strawberries = 2
****
Grapes = 7
Strawberries = 2
****
Grapes = 8
Strawberries = 2
****
Grapes = 9
Strawberries = 2
****
Grapes = 10
Strawberries = 2
****
Grapes = 0
Strawberries = 3
****
Grapes = 1
Strawberries = 3
****
Grapes = 2
Strawberries = 3
****
Grapes = 3
Strawberries = 3
****
Grapes = 4
Strawberries = 3
****
Grapes = 5
Strawberries = 3
****
Grapes = 6
Strawberries = 3
****
Grapes = 7
Strawberries = 3
****
Grapes = 8
Strawberries = 3
****
Grapes = 9
Strawberries = 3
****
Grapes = 10
Strawberries = 3
****
Grapes = 0
Strawberries = 4
****
Grapes = 1
Strawberries = 4
****
Grapes = 2
Strawberries = 4
****
Grapes = 3
Strawberries = 4
****
Grapes = 4
Strawberries = 4
****
Grapes = 5
Strawberries = 4
****
Grapes = 6
Strawberries = 4
****
Grapes = 7
Strawberries = 4
****
Grapes = 8
Strawberries = 4
****
Grapes = 9
Strawberries = 4
****
Grapes = 10
Strawberries = 4
****
Grapes = 0
Strawberries = 5
****
Grapes = 1
Strawberries = 5
****
Grapes = 2
Strawberries = 5
****
Grapes = 3
Strawberries = 5
****
Grapes = 4
Strawberries = 5
****
Grapes = 5
Strawberries = 5
****
Grapes = 6
Strawberries = 5
****
Grapes = 7
Strawberries = 5
****
Grapes = 8
Strawberries = 5
****
Grapes = 9
Strawberries = 5
****
Grapes = 10
Strawberries = 5
****
Grapes = 0
Strawberries = 6
****
Grapes = 1
Strawberries = 6
****
Grapes = 2
Strawberries = 6
****
Grapes = 3
Strawberries = 6
****
Grapes = 4
Strawberries = 6
****
Grapes = 5
Strawberries = 6
****
Grapes = 6
Strawberries = 6
****
Grapes = 7
Strawberries = 6
****
Grapes = 8
Strawberries = 6
****
Grapes = 9
Strawberries = 6
****
Grapes = 10
Strawberries = 6
****
Grapes = 0
Strawberries = 7
****
Grapes = 1
Strawberries = 7
****
Grapes = 2
Strawberries = 7
****
Grapes = 3
Strawberries = 7
****
Grapes = 4
Strawberries = 7
****
Grapes = 5
Strawberries = 7
****
Grapes = 6
Strawberries = 7
****
Grapes = 7
Strawberries = 7
****
Grapes = 8
Strawberries = 7
****
Grapes = 9
Strawberries = 7
****
Grapes = 10
Strawberries = 7
****
Grapes = 0
Strawberries = 8
****
Grapes = 1
Strawberries = 8
****
Grapes = 2
Strawberries = 8
****
Grapes = 3
Strawberries = 8
****
Grapes = 4
Strawberries = 8
****
Grapes = 5
Strawberries = 8
****
Grapes = 6
Strawberries = 8
****
Grapes = 7
Strawberries = 8
****
Grapes = 8
Strawberries = 8
****
Grapes = 9
Strawberries = 8
****
Grapes = 10
Strawberries = 8
****
Grapes = 0
Strawberries = 9
****
Grapes = 1
Strawberries = 9
****
Grapes = 2
Strawberries = 9
****
Grapes = 3
Strawberries = 9
****
Grapes = 4
Strawberries = 9
****
Grapes = 5
Strawberries = 9
****
Grapes = 6
Strawberries = 9
****
Grapes = 7
Strawberries = 9
****
Grapes = 8
Strawberries = 9
****
Grapes = 9
Strawberries = 9
****
Grapes = 10
Strawberries = 9
****
Grapes = 0
Strawberries = 10
****
Grapes = 1
Strawberries = 10
****
Grapes = 2
Strawberries = 10
****
Grapes = 3
Strawberries = 10
****
Grapes = 4
Strawberries = 10
****
Grapes = 5
Strawberries = 10
****
Grapes = 6
Strawberries = 10
****
Grapes = 7
Strawberries = 10
****
Grapes = 8
Strawberries = 10
****
Grapes = 9
Strawberries = 10
****
Grapes = 10
Strawberries = 10
2012-04-04 17:36
by Error_404

3

You can use a single loop.

There are 11^10 possible combinations. you can iterate through them all

// String[] names = "Grapes,Strawberries,Raspberries,Blackberries,Pineapples,Oranges,Prunes,Pears,Cherries,Peaches,Apples".split(",");
String[] names = "Pineapples,Oranges,Prunes,Pears,Cherries,Peaches,Apples".split(",");
int maxQuantity = 10;
long combinations = 1;
int quantities = maxQuantity + 1;
for (String _ : names)
    combinations *= quantities;

long start = System.currentTimeMillis();
PrintStream out = new PrintStream(new BufferedOutputStream(new FileOutputStream("combinations.tsv")));
// heading
for (String name : names)
    out.print(name + "\t");
out.println();

for (long comb = 0; comb < combinations; comb++) {
    // comb is a base N number of digits 0 to maxQuantity.
    long c = comb;
    for (int i = 0; i < names.length; i++) {
        long n = c % quantities;
        c /= quantities;
        out.print(n);
        out.print('\t');
    }
    out.println();
}
out.close();
System.out.println("Took " + (System.currentTimeMillis() - start) / 1e3 + " seconds" +
        " to write " + combinations + " combinations");

prints

Took 51.585 seconds to write 19487171 combinations

if you comment out the lines were it prints the values to a file you get

Took 0.065 seconds to write 19487171 combinations

Note: This program will spend most of its time printing. If you remove the printing part it will finish very quickly. ;)

2012-04-04 17:53
by Peter Lawrey
Thanks Peter. Helpful, but in the example code I had it set to 2 so if anyone runs it by mistake it doesn't take forever to run(I edited it now). Say I had it at 10 instead of 2(0 to 10 instead of 0 to 2)..is there any techniques that could be used at that point to speed it up? even reducing the printing still makes it take a long time(just did the print to demonstrate what I was looking for - Error_404 2012-04-04 18:04
@learningJava: You have two options. You can either (a) change the algorithm so that the algorithm itself is faster, like Peter did, or you can (b) optimize. Optimization of small things won't help much when you have an extremely inefficient algorithm (as in the original code). I strongly recommend taking an algorithms class where they discuss computational complexity to fully understand the issue - atk 2012-04-04 18:13
After running it, I'm not sure this is doing what my program above is doing. my program provides shows all the combinations for each fruit from 0-10 but there are some combinations that don't seem to be in the output of this sample(also the value is not shown) - Error_404 2012-04-04 18:27
I have changed it so it counts the number of unique solutions. How many solutions are you expecting - Peter Lawrey 2012-04-04 19:44
I'm not exactly sure because it takes forever to run up to number 10, but if you run the above code and remove a few zeros so there's only 3 zeros(10^3) then I get 1331 results. If I run 4 variables then I get 14641. - Error_404 2012-04-04 20:05
You can only remove some of the words in the combination, I can't see how you can remove any of the zeros above. If you have three words you should get 8 combinations - Peter Lawrey 2012-04-04 20:35
I see the confusion. I assume each item can appear up to 1 times, not ten times as you have. If you can have 0-10 of each time that means you can have 11^3 combinations for three words - Peter Lawrey 2012-04-04 20:37
Yes thats correct. The code is running combinations of 0-10 for each fruit. I posted the output/performance info. The more fruits I add the longer it takes, I'm trying to see if there's any tricks I can do(caching, data structure,etc..) to overcome it - Error_404 2012-04-04 20:47
You should expect it to be 11 times longer with each item, after all its doing 11x times more work. See my edit for an updated solution - Peter Lawrey 2012-04-04 21:05
wow..thanks for the update, I didn't realized writing out took such a toll on performance. I'm playing around with your code, I tried to run it with 11 variables and it took less than 3 min(no writes). I think my actual program will get up to 100 variables max so I'll do some testing. Thanks so much. Do you know if I can cache results to prevent it from doing exponentially more work - Error_404 2012-04-04 21:31
The simplest thing you can do is loop the last one or two elements using the result so far - Peter Lawrey 2012-04-05 05:51

0

Assuming that you will only care about the first instance of the same item you can break the loop when you match to avoid extra loops. Can you provide a better break down of what the 'problem' is here (what your program is supposed to do)?

2012-04-04 18:12
by RyanS
I'm trying to learn. I have a different hobby program thats pretty complex but follows a similar logic. I'm trying to figure out if there are any techniques to speed it up as well as learn a new way of doing things(if it exists) - Error_404 2012-04-04 18:28
I mean for your search, are you only interested in yes/no solutions, if not do you need to keep a count of the items? Will there be more than two of the same item/does it matter? Stuff like that, while learning I would recommend breaking problems down and being as specific as much as possible, essentially the basis for creating an algorithm. There are mannny ways to speed up the process such as using advanced search/sort algorithms or data structures. I would recommend researching those general topics. Good luc - RyanS 2012-04-04 18:36
After reading your other comments I realize I'm missing the mark a little, although my suggestions are still somewhat reasonable. To speed up your output try storing your combination's in an array and dumping it at the end of your program. Opening and closing an IO stream will slow down your program significantly - RyanS 2012-04-04 18:41
Thanks for the comment Ryan. Even without the IO stream, if you run the above code it takes over 30 minutes(and more, its still running for me). I was looking for something like you mentioned, advanced search/sort algorithms or data structures..do you know which ones would apply? or is it in any basic algorithm book - Error_404 2012-04-04 19:14
Ads