3

我基本上是在尝试使用递归并创建了一个小程序，该程序可以从 0-10 的 10 个项目中找到所有组合（{1 苹果，0 葡萄}，{2 苹果，0 葡萄}，{0 苹果，1 葡萄} ， 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);
            }
        }
    }
}

现在它有 10,000,000,000 个循环（10 ^ 10）所以我理解为什么需要很长时间，但我想知道是否有任何 Java 或算法技巧可以用来减少循环数以加快速度？

我考虑过使用线程/多处理，但是仍然需要发生相同数量的循环，这仍然需要很长时间。我不确定这里是否可以使用任何数据结构、排序算法或缓存算法。或者我可以将结果并行添加到数组中，然后将它们组合在一起以获得最终结果？我不熟悉任何其他现有方法，因此非常欢迎任何关于语言特定技巧或算法解决方案的建议。

更新：为了澄清我在做什么以及我将发布一些示例的性能。要增加处理时间，只需向 list_to_start 添加/删除零（以下结果以毫秒为单位）：

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.

输出（我禁用它以使其运行得更快）是 2 个变量（上面的代码运行 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
4

2 回答 2

3

您可以使用单个循环。

有 11^10 种可能的组合。你可以遍历它们

// 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");

印刷

Took 51.585 seconds to write 19487171 combinations

如果您注释掉这些行，它会将值打印到您获得的文件中

Took 0.065 seconds to write 19487171 combinations

注意：该程序将大部分时间用于打印。如果您移除打印部分，它将很快完成。;)

于 2012-04-04T17:53:45.350 回答
0

假设您只关心同一项目的第一个实例，您可以在匹配时打破循环以避免额外的循环。你能更好地分解这里的“问题”（你的程序应该做什么）吗？

于 2012-04-04T18:12:53.377 回答