java - 最速のアルゴリズム競争を実行する

Question

コードゴルフ大会のような大会を開催したいのですが、勝者は最小のコードではなく、最速のアルゴリズムを持ちます。

アルゴリズムの速度を測定する公正な方法の 1 つは、Java の JVM のようなニュートラルな仮想マシンを使用することです。実行された JVM 命令の総数を知る簡単な方法はありますか? (エントリが複数のスレッドを使用する場合、JVM 命令の総数はすべてのスレッドで合計されます。)

たとえば、コード

public class simple {
    public static int main(String argc[]) {
        int i;

        i = 3;
        while (i > 0) {
            i--;
        }

    return 0;
    }
}

JVMコードを生成します

0:  iconst_3
1:  istore_1
2:  iload_1
3:  ifle    12
6:  iinc    1, -1
9:  goto    2
12: iconst_0
13: ireturn

そして、(正しく数えた場合) 18 個の JVM 命令を実行する必要があります。

応募作品を自宅で走らせて、審査員が見るものを見てもらいたいと思います。明らかに、プログラムに入力を与える場合、最速の解決策は、メモ化され、事前に計算された回答を吐き出すことです。客観的に、人々が自宅でプログラムを実行できるようにし、メモ化された答えを見ないようにする方法はありますか?
非公式の「最速コード競争」の発生を妨げている他の問題は何ですか?

ありがとう！

score 5 · Accepted Answer

唯一の公正な比較は、一般的なハードウェアでの最短の完了時間です。プログラムを完了するまでの時間は完全にハードウェアに依存します。それ以外の場合、より強力なマシンにお金を費やす意味はありますか?

再現可能な結果に最も近いのは、相対速度を報告することです。たとえば、サンプルプログラムを提供し、たとえば 50% の時間で実行されているユーザープログラムに関して報告します。ある PC で 2 倍高速なプログラムは、別の PC でも 2 倍高速になる可能性があります。

大学では、「秘密の」入力に対して実行される課題を提出しますが、エラーを修正するために複数回提出することもできました。私の最初の送信はまったく機能しませんでしたが、すべての入力をログに記録しました。;)

編集：より長い答え。

次のプログラムを検討してください

public class FibMain {
    public static void main(String... args) {
        {
            long start = System.nanoTime();
            System.out.println(iteration_fib(Integer.parseInt(args[0])));
            long time = System.nanoTime() - start;
            System.out.printf("Iteration took %,d us%n", time /  1000);
        }
        {
            long start = System.nanoTime();
            System.out.println(recursive_fib(Integer.parseInt(args[0])));
            long time = System.nanoTime() - start;
            System.out.printf("Recursion took %,d us%n", time /  1000);
        }
    }

    public static long iteration_fib(int n) {
        long t1 = 1;
        long t2 = 1;
        while (n-- > 2) {
            long t = t2;
            t2 += t1;
            t1 = t;
        }
        return t2;
    }

    public static long recursive_fib(int n) {
        if (n <= 2) return 1;
        return recursive_fib(n - 1) + recursive_fib(n - 2);
    }
}

生成されたバイトコードを javap -c で見ると、

public static long iteration_fib(int);
  Code:
   0:   lconst_1
   1:   lstore_1
   2:   lconst_1
   3:   lstore_3
   4:   iload_0
   5:   iinc    0, -1
   8:   iconst_2
   9:   if_icmple       25
   12:  lload_3
   13:  lstore  5
   15:  lload_3
   16:  lload_1
   17:  ladd
   18:  lstore_3
   19:  lload   5
   21:  lstore_1
   22:  goto    4
   25:  lload_3
   26:  lreturn

public static long recursive_fib(int);
  Code:
   0:   iload_0
   1:   iconst_2
   2:   if_icmpgt       7
   5:   lconst_1
   6:   lreturn
   7:   iload_0
   8:   iconst_1
   9:   isub
   10:  invokestatic    #13; //Method recursive_fib:(I)J
   13:  iload_0
   14:  iconst_2
   15:  isub
   16:  invokestatic    #13; //Method recursive_fib:(I)J
   19:  ladd
   20:  lreturn

したがって、最初の例は 2 番目の例よりも長いため、最初の例の方が時間がかかると思われるかもしれません。ただし、「n」が興味深いサイズである場合は正しくありません。

マシンで FibMain 44 を実行したところ、次の結果が得られました。

701408733
Iteration took 495 us
701408733
Recursion took 19,174,036 us

これは、反復の実行にかかる時間は n (この場合は 44) に比例し、直線的に増加しますが、再帰にかかる時間は結果 (この場合は 701408733) に比例し、指数関数的に増加するためです。

入力として 50 を試してみると、1 回目は瞬く間に完了しますが、2 回目は時間がかかりすぎて、待つのに飽きてしまいます。

score 2 · Accepted Answer

SPOJ (これは無料で、Java をサポートしています) のようないくつかのオンラインツールで競争を行うことができます。このようにして、プログラムの実行時間を測定する 1 つの参照マシンができます。

score 1 · Accepted Answer

ガベージコレクターを適切に制御できるように、おそらくリアルタイムJVMを使用する必要があります。ガベージコレクターが実行中に開始したという理由だけで、1人の候補者がより長い実行時間を示した場合は不公平になります。

score 1 · Accepted Answer

（1）プロセスの実行の時間を計ってみませんか？プロセスの起動よりも実際の処理がタイミングの最も支配的な側面になるようにパズルを設計し、平均を取得するために数回反復して時間をかけます。

(2) についてはサンプル入力を提供しますが、ライブコンテストには別の入力を使用してください。

score 1 · Accepted Answer

(2) に関しては、プログラミングコンテスト (正しさだけが重要な場合) で通常使用される解決策は、少数の限られた数の入力例を提供することですが、審査システムではより包括的なテストセットを使用します。

(3) に関しては、使用される JVM 命令の数は必ずしも速度の良い尺度ではありません。一部の実装では、各命令にかかる時間が長くなったり短くなったりする場合があります。jitting やその他の最適化についてはまだ始めていません。

score 0 · Accepted Answer

また、指示の数を数えるのも良い方法だと思います。

私が見る唯一の欠点は、JVM命令が強力すぎる場合です。JVCはわかりませんが、文字列がネイティブにサポートされている可能性があります。文字列を追加すると、命令が1つだけになる可能性があります。（そうは思わないでください。）

昔ながらのtimeコマンドを使用します。これは実行時間を測定しますが、バックグラウンドプロセスによるほとんどすべての影響を排除するリアルタイムではありません。

score 0 · Accepted Answer

VJM をさらに一歩進めて、完全な Linux ベースの VM を実装してみませんか? クロックサイクルは同じである必要があります (VM の実装方法によると思います)。

たとえば、256K RAM と MINUX を実行する 5 MB のディスク容量を持つ 8088 に基づいて VM を作成できます。コードの実行速度に関係なく、8088 が実際に Pentium デュアルコアまたは一部の古い Power PC に実装されているかどうかにかかわらず、CPU サイクルの数は (8088 と比較して) 同じままではないでしょうか。

仮想ハードウェアを確立したら、言語の選択が「最速のアルゴリズム」コンテストのソリューションの一部になる可能性があります。

score 0 · Accepted Answer

オートグレーダータイプのテストサイトを実装して、人々がコードを送信し、パフォーマンス結果とおそらく最高速度の結果を示す電子メールを受け取ることができるようにすることができます。それらは入力を取得しませんが、公式の JVM が生成する結果を取得します。悪用を防ぐには、クラスローダーを修正して、あらゆる種類の送信接続タイプのものをロードしないようにし、パフォーマンステスターをアドレスごとに 1 日 1 回の送信に制限するか、その他の戦略を立てます。

score 0 · Accepted Answer

特にさまざまなハードウェア構成の管理、およびベンチマークと検証手順に関して、FastCodeを見ることで、この種の競争に必要なものについて多くを学ぶことができます.

score 0 · Accepted Answer

唯一の賢明な尺度は、実際のハードウェアでの時間です。コンパイラは、実行された命令の数ではなく、時間に対して最適化するため、命令をカウントすると、多くの最適化が無効になり、それらの一部が悲観化されます。命令にかかる時間が異なるだけでなく、メモリアクセスなどによる実行の遅延も大幅に異なります。

java - 最速のアルゴリズム競争を実行する

10 に答える 10

Related

Reference