3

私は基本的に再帰を試して、10 個の項目 ({1 リンゴ、0 ブドウ}、{2 リンゴ、0 ブドウ}、{0 リンゴ、1 ブドウ}) のうち 0 から 10 までのすべての組み合わせを見つける小さなプログラムを作成しました。など）。

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 に答える