-1 
import java.io.*;
import java.util.ArrayList;

public class Ristsumma {
static long numberFromFile;
static long sum1, sum2;
static long number, number2;
static long variable, variable2;
static long counter;

public static void main(String args[]) throws IOException{
    try{
        BufferedReader br = new BufferedReader(new FileReader("ristsis.txt"));
        numberFromFile = Long.parseLong(br.readLine()); 

        br.close();
    }catch(Exception e){
    e.printStackTrace();
    }   

    variable=numberFromFile;
    ArrayList<Long> numbers = new ArrayList<Long>();

    while (variable > 0){
        number = variable %10;
        variable/=10;
        numbers.add(number);
    }

    for (int i=0; i< numbers.size(); i++) {
        sum1 += numbers.get(i);
    }

    ArrayList<Long> numbers2 = new ArrayList<Long>();
    for(long s=1; s<numberFromFile; s++){
        variable2=s;
        number2=0;
        sum2=0;

        while (variable2 > 0){
            number2 = variable2 %10;
            variable2/=10;  
            numbers2.add(number2);
        }

        for (int i=0; i< numbers2.size(); i++) {
            sum2 += numbers2.get(i);
        }

        if(sum1==sum2){
        counter+=1; 
        }

        numbers2.clear();
    }       
PrintWriter pw = new PrintWriter("ristval.txt", "UTF-8");
pw.println(counter);
pw.close();

}
}

だから私はこのコードを持っています。ファイルから数値を取得し、その数値とは別にすべての数値を追加し、それらを合計します (たとえば、数値が 123 の場合、1+2+3=6 になります)。後半では、ファイル内の 1 からその番号までのすべての数字を調べ、同じ答えを返す異なる数字がいくつあるかを数えます。数が 123 の場合、合計は 6 で、コードが書き込む答えは 9 です (6、15、24、33、42、51、60、105、114 も同じ答えになるため)。コードは機能しますが、私の問題は、ファイルからの番号がたとえば 2 222 222 222 の場合、答えを得るのにほぼ 30 分かかることです。これをより速く実行するにはどうすればよいですか?

4

4 に答える 4

3

不要なリストの作成を削除

不必要にリストを作成している

ArrayList<Long> numbers = new ArrayList<Long>();

while (variable > 0){
    number = variable %10;
    variable/=10;
    numbers.add(number);
}

for (int i=0; i< numbers.size(); i++) {
    sum1 += numbers.get(i);
}

ここで配列リストを作成します。Long を一時的に保持するためだけに、リスト全体を削除できます。

while (variable > 0){
    number = variable %10;
    variable/=10;
    sum1 += number
}

他のarraylist番号についても同じ2

プリサイズのアラリスト

配列リストは既に削除しましたが、削除していない場合は、配列のサイズを前もって調整することで速度を向上させることができます。

ArrayList<Long> numbers = new ArrayList<Long>(someGuessAsToSize);

推測が正しいことは必須ではありません。arraylist は引き続き自動サイズ変更されますが、推測がほぼ正しい場合は、arraylist を定期的にサイズ変更する必要がないため、コードが高速化されます。

一般的なスタイル

多くの（あるべき）メソッド変数をフィールドとして保持しています

static long numberFromFile;
static long sum1, sum2;
static long number, number2;
static long variable, variable2;
static long counter;

これがパフォーマンスに影響を与える可能性は低いですが、これは異常なことであり、コードが読みにくくなり、「隠れた影響」が発生する可能性があります。

于 2013-11-12T15:02:42.527 に答える
1

個々の数字をまったく保存する必要がないことに注意してください。

代わりに、関心があるのは実際の数字の合計だけです。

これを考慮して、次のような方法

static int diagsum(long number)  { ... }

素晴らしいことだ。十分に簡単な場合は、JIT でインライン化するか、少なくともスパゲッティ コードよりも最適化することができます。

もう一度言いますが、ある制限で桁の合計の計算を停止する別の方法を利用できます。たとえば、あなたが持っているとき

22222222

合計は 20 です。これは、20 より大きい他の合計を計算する必要がないことを意味します。たとえば、次のようになります。

45678993

代わりに、9 + 9 + 3 は 21 であり、これはすでに 20 より大きいため、最後の 3 桁 (diision メソッドによって最初に取得する) を取得したら、停止することができます。

================================================== =================

別の最適化:

いくつかの番号がある場合：

123116

これらの 6 桁のすべての一意の順列が同じ桁の合計を持つことはすぐに明らかです。

321611, 231611, ... are solutions

次に、個々の数字 ab の任意のペアについて、変換された数値は、a+1, .. . はまだ 0..9 の範囲にあります。再帰的に適用して、さらに多くの数値を取得します。

その後、桁数の少ない数字に変えることができます。明らかに、同じ数字の合計を得るには、可能であれば元の数字の 2 桁を組み合わせる必要があります。たとえば、

5412 => 912, 642, 741, 552, 561, 543

変換や組み合わせが不可能になるまで、上記と同じアルゴリズムを再帰的に適用します。

=========

ただし、重複を処理するためにセットのようなデータ構造を維持する必要があるため、上記のアイデアは大量のメモリを必要とすることに注意してください。ただし、987_654_321 の場合、すでに 39_541_589 の結果が得られており、さらに大きな数になるとさらに多くの結果が得られます。したがって、実際に組み合わせ的な方法でそれを行う努力が価値があるかどうかは疑問です.

于 2013-11-12T15:05:12.460 に答える