java - 実行時間を短縮

Question

HashSet を使用して文字配列の重複要素を単純に削除するプログラムがあります。

これが私のプログラムです：

import java.util.Arrays;
import java.util.HashSet;

import java.util.Set;

public class MainClass {
    public static void main(String[] arg) {
        double sT = System.nanoTime();
        Character[] data = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
                'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f',
                'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd',
                'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
                'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b',
                'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
                'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
                'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
                'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
                'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
                'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
                'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
                'u', 'v', 'w', 'x', 'y', 'z' };

        Set<Character > uniqueSet = new HashSet<Character>(Arrays.asList(data));

         Character[] strArr = new Character[uniqueSet.size()];
         uniqueSet.toArray(strArr);

            for(Character str:strArr){
                System.out.println(str);
            }


        System.out.println(System.nanoTime() - sT);

    }

}

目的の出力が得られます。しかし、問題は実行時間です。実行時間を短縮するためにプログラムに実装できる方法はありますか?

Answer 1

持つことができるさまざまなタイプの要素は非常に小さいため、ハッシュセットの代わりに単純な配列を簡単に使用できます (セットまたはカウントソートに似たアプローチ)。大文字以外の英語の文字のみboolean met[26];が必要な場合は array を宣言し、すべての文字をサポートできるようにする必要がある場合はboolean met[256];.

配列を繰り返し処理し、met値が false の場合にのみ結果に文字を追加します。結果に文字を追加するときは、使用済みとしてマークすることを忘れないでください。

ハッシュが含まれないため、パフォーマンスが向上します。

編集：コードサンプルを追加しようとする意味と混乱があるようです

boolean met[] = new boolean[256]; // Replace 256 with the size of alphabet you are using
List<Character> res = new ArrayList<Character>();
for(Character c:data){
  int int_val = (int)c.charValue();
  if (!met[int_val]) {
     met[int_val] = true;
     res.add(c);
  }
}

// res holds the answer.

Answer 2

最初に認識すべきことは、コンソールへの書き込みは非常にコストがかかるということです。外すと

System.out.println(str);

これにより、コードが劇的に高速化されます。

もう 1 つの注意点は、コードがウォームアップするのに十分な時間実行されていない (コンパイルされない) ことです。テストを約 2 ～ 10 秒間実行して、ウォームアップされたコードでどれくらいの時間がかかるかを確認する必要があります。 .

かかった時間

• 印刷あり => 2,498,085 ns
• 印刷なし => 1,509,978 ns
• 最初にコードを警告した場合 => 43,347 ns
• コードをウォームアップして平均 10,000 回実行した場合 => 18,922 ns
• コードをさらに最適化し、100 万回実行 ~2 秒 => 1,287 ns

エンド ツー エンドで 2000 倍のパフォーマンス向上です ;)

最終的なコードは次のようになります

StringBuilder strArr = null;
long sT = 0;
int runs = 1000000;
for (int i = -40000; i < runs; i++) {
    if (i == 0)
        sT = System.nanoTime();

    String text = "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm" +
            "qwertyuiopasdfghjklzxcvbnm";
    BitSet bs = new BitSet(256);
    for (int j = 0, len = text.length(); j < len; j++)
        bs.set(text.charAt(j));
    strArr = new StringBuilder();
    for (int j = -1; (j = bs.nextSetBit(j+1)) >= 0; )
        strArr.append((char) j);
}

System.out.printf("Took an average of %,d ns%n", (System.nanoTime() - sT) / runs);

System.out.print(strArr);

版画

Took an average of 1,287 ns
abcdefghijklmnopqrstuvwxyz

Answer 3

Let Google Caliper take care of microbenchmarking:

 0% Scenario{vm=java, trial=0, benchmark=Array} 12868.77 ns; σ=523.07 ns @ 10 trials

  us
12.9

vm: java
trial: 0
benchmark: Array

12.9 microseconds. Not quite the same as your 1319 microseconds, is it :)

For reference, this is the exact code:

import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;

public class Performance extends SimpleBenchmark {
  public int timeArray(int reps) {
    int sum = 0;
    for (int rep = 0; rep < reps; rep++) {
      Character[] data = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
          'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
          'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b',
          'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
          'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
          'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g',
          'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
          'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
          't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
          'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e',
          'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
          'y', 'z' };
      sum += new HashSet<>(Arrays.asList(data))
          .toArray(new Character[new HashSet<Character>
                   (Arrays.asList(data)).size()]).length;
    }
    return sum;
  }

  public static void main(String... args) {
    Runner.main(Performance.class, args);
  }
}

Answer 4

GoogleGuavaを使用してそれを行うことができます。それについてのStackoverflowの議論があります。