プロジェクトオイラーの最適化＃22

Question

ありがとうございます。

私はちょうどファイルから約5,000行のテキストを読み込み、その文字列の合計とそのアルファベット順の位置に基づいて特定の名前の値を決定するという問題を解決しました。

しかし、コードの実行には約5-10秒かかってしまいますが、これはちょっと面倒です。このコードを最適化する最良の方法は何ですか？現在、スキャナを使用してファイルを文字列に読み込んでいます。これを行うための別の、より効率的な方法がありますか？あなたはここで行うように、「+」でループ内の文字列を追加は

public static int P22(){ 


    String s = null; 

    try{ 
     //create a new Scanner to read file 
     Scanner in = new Scanner(new File("names.txt")); 
     while(in.hasNext()){ 
      //add the next line to the string 
      s+=in.next(); 
     } 

    }catch(Exception e){ 

    } 
    //this just filters out the quotation marks surrounding all the names 
    String r = ""; 
    for(int i = 0;i<s.length();i++){ 
     if(s.charAt(i) != '"'){ 
      r += s.charAt(i); 
     } 
    } 
    //splits the string into an array, using the commas separating each name 
    String text[] = r.split(","); 
    Arrays.sort(text); 



    int solution = 0; 
    //go through each string in the array, summing its characters 
    for(int i = 0;i<text.length;i++){ 
     int sum = 0; 
     String name = text[i]; 
     for(int j = 0;j<name.length();j++){ 
      sum += (int)name.charAt(j)-64; 
     } 
     solution += sum*(i+1); 
    } 
    return solution; 


} 

Answer 1

Scannerを使用する場合は、それが何をするべきか（トークン化）に使用しないでください。

Scanner in = new Scanner(new File("names.txt")).useDelimiter("[\",]+"); 
    ArrayList<String> text = new ArrayList<String>(); 
    while (in.hasNext()) { 
    text.add(in.next()); 
    } 
    Collections.sort(text); 

あなたは引用符を除去する必要がある、またはカンマで分割していない - Scannerはあなたのためにすべてを行います。

Javaの起動時間を含むこのスニペットは、私のマシンで0.625秒（ユーザ時間）で実行されます。私はそれがあなたがやっていたものより少し速くなければならないと思う。

EDIT OPには、useDelimiterに渡された文字列が尋ねられました。それはregular expressionです。あなたが取り除くときは、文字列の中に引用符文字を含めるためにJavaで必要なエスケープ、それは[",]+だ - と意味は次のとおりです。このパターンにマッチする

[...] character class: match any of these characters, so 
[",] match a quote or a comma 
...+ one or more occurence modifier, so 
[",]+ match one or more of quotes or commas 

シーケンスは、次のとおりです。確かに

" 
, 
,,,, 
""",,,","," 

とを","、ここで私たちが何をしていたのか？

Answer 2

を（私はBufferedReaderのを使用してみましたが、それにも遅かった）：それは作成する必要がありますので

/* That's actually not the problem since there is only one line. */ 
while(in.hasNext()){ 
    //add the next line to the string 
    s+=in.next(); 
} 

が、遅いです新しい文字列を作成し、各繰り返しですべてをコピーします。 StringBuilder、

StringBuilder sb = new StringBuilder(); 
while(in.hasNext()){ 
    sb.append(in.next()); 
} 
s = sb.toString(); 

を使用してみてください。しかし、あなたが本当にStringにファイルの内容を読んではいけません、あなたは、しかし、直接

int names = 5000; // use the correct number of lines in the file! 
String[] sa = new String[names]; 
for(int i = 0; i < names; ++i){ 
    sa[i] = in.next(); 
} 

を、ファイルの内容からString[]またはArrayList<String>を作成する必要がありますチェックすると、ファイルには約5000行が含まれていないことがわかります。むしろすべてが1行になっているので、大きな問題は実際には

/* This one is the problem! */ 
String r = ""; 
for(int i = 0;i<s.length();i++){ 
    if(s.charAt(i) != '"'){ 
     r += s.charAt(i); 
    } 
} 

です0

これにはStringBuilderを使用してください。または、Scannerを次の '、'まで読んで、ArrayList<String>に直接読み込んで、ArrayListの各単一の名前から二重引用符を削除してください。

Answer 3

プロファイラでコードを実行することをお勧めします。どの部分が実際に遅いのか（IO /計算など）を理解することができます。 IOが遅い場合は、NIO：http://docs.oracle.com/javase/1.4.2/docs/guide/nio/を確認してください。

Answer 4

この問題では5秒以上が非常に遅いです。私のWebアプリケーション全体（600 Javaクラス）は、を4秒でコンパイルします。あなたの問題の根源はおそらく、ファイル内のすべての文字に新しい文字列を割り当てることです：r += s.charAt(i)

本当にスピードアップするには、文字列を使用しないでください。ファイルサイズを取得し、単一のI/Oコールでバイト配列に全部を読む：

public class Names { 
    private byte[] data; 
    private class Name implements Comparable<Name> { 
    private int start; // index into data 
    private int length; 
    public Name(int start, int length) { ...; } 
    public int compareTo(Name arg0) { 
     ... 
    } 
    public int score() 
    } 
    public Names(File file) throws Exception { 
    data = new byte[(int) file.length()]; 
    new FileInputStream(file).read(data, 0, data.length); 
    } 
    public int score() { 
    SortedSet<Name> names = new ... 
    for (int i = 0; i < data.length; ++i) { 
     // find limits of each name, add to the set 
    } 
    // Calculate total score... 
    } 
} 

Answer 5

アプリケーションに応じて、StreamTokenizerがしばしばScannerよりも測定可能な高速です。 2つを比較する例は、hereおよびhereであると見なすことができる。

補遺：Euler Project 22は、遭遇した各トークン内の文字のチェックサムの一種を導出することを含む。トークンを2回トラバースするのではなく、カスタムanalyzerは認識と計算を組み合わせることができます。その結果は、後の反復のために総計を見つけるためにSortedMap<String, Integer>に格納されます。

Answer 6

面白いと思われる鈍い解決策です。

long start = System.nanoTime(); 
long sum = 0; 
int runs = 10000; 
for (int r = 0; r < runs; r++) { 
    FileChannel channel = new FileInputStream("names.txt").getChannel(); 
    ByteBuffer bb = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size()); 
    TLongArrayList values = new TLongArrayList(); 

    long wordId = 0; 
    int shift = 63; 
    while (true) { 
     int b = bb.remaining() < 1 ? ',' : bb.get(); 
     if (b == ',') { 
      values.add(wordId); 
      wordId = 0; 
      shift = 63; 
      if (bb.remaining() < 1) break; 

     } else if (b >= 'A' && b <= 'Z') { 
      shift -= 5; 
      long n = b - 'A' + 1; 
      wordId = (wordId | (n << shift)) + n; 

     } else if (b != '"') { 
      throw new AssertionError("Unexpected ch '" + (char) b + "'"); 
     } 
    } 

    values.sort(); 

    sum = 0; 
    for (int i = 0; i < values.size(); i++) { 
     long wordSum = values.get(i) & ((1 << 8) - 1); 
     sum += (i + 1) * wordSum; 
    } 
} 
long time = System.nanoTime() - start; 
System.out.printf("%d took %.3f ms%n", sum, time/1e6); 

プリント

XXXXXXX took 27.817 ms.