2

ブラウン運動と発散をテストするためにいくつかのコードを実行しています。このコードの実行にかかる時間と、プロセスを高速化する方法に興味がありました。私は Java に比較的慣れていないので、現時点でのコードは比較的基本的なものです。私が実行している引数は 1000000 1000000 です。

public class BrownianMotion {

    public static void main(String[] args) {

    /**starts vars for program*/

    int N = Integer.parseInt(args[0]);
    int T = Integer.parseInt(args[1]);
    double sqtotal = 0;
    double r;
    double avg;

    /**number of trials loop*/

    for (int count=0;count<T;count++) {

        /**started here so that x & y reset at each trial*/

        int x = 0;
        int y = 0;

        /**loop for steps*/
        for (int steps=0;steps<N;steps++) {

        r = Math.random();
        if      (r < 0.25) x--;
        else if (r < 0.50) x++;
        else if (r < 0.75) y--;
        else if (r < 1.00) y++;

        }
        /**squared total distance after each trial*/
        sqtotal = sqtotal + (x*x+y*y);

    }

    /**average of squared total*/

    avg = sqtotal/T;
    System.out.println(avg);

    }
}

助けてくれてありがとう。

4

4 に答える 4

4

あなたのコードを理解しているので、各トライアルを並行して実行できます。CPU に複数のコアがある場合は、それに応じてより高速に実行されます。

（編集を追加）

通常、アルゴリズムを Callable に変換し、数十個(次元ごと、状態ごとなど) に作成し、Executors.newFixedThreadPool() を使用して適切なサイズのスレッド プールを作成します (たとえば、インテルi3 ラップトップ、4 スレッド) を呼び出し、invokeAll() を呼び出します。 詳細については、このブログ投稿をご覧ください

ただし、100,000 の例では、これはうまく機能しません。理想的な方法は、完了時に CompletionService を使用してジョブを再送信することです。これは複雑になり始めます。

より単純で、効率的ではない (それでもより高速な) 方法は、

  1. たとえば、10 個の BrownianWalkers を含むコレクションを作成します。最初に x と y = 0 を設定すると、再利用できることに注意してください。したがって、このリストを作成する必要があるのは一度だけです
  2. fixedThreadPool を作成する
  3. i=0...10000 のループ内 {
  4. submitAll() を呼び出します。
  5. 結果 (先物) をループし、それらを合計に追加します。
    }

すべてが完了するのを待つのに少し時間がかかりますが、それでも大幅な高速化が見られるはずです。ほとんどのプロセッサは 2、4、8 などのコアを持っているため、コレクションを 2 の累乗にすることで (計算が簡単になる 10 ではなく) わずかな改善が得られます。

于 2012-09-30T04:31:03.323 に答える
0

これが実行される時間を見つけるためには、関数O（N ^ 2）の実行の複雑さを見つけることです。私は信じている。

于 2012-09-30T04:18:34.877 に答える
0

コードを高速化するには、少なくとも 3 つの方法があります。効果の高いものから低いものへとリストされています。

  1. アルゴリズムの複雑さを軽減します。現在、アルゴリズムにはO(N^2)時間の複雑さがあります。つまり、処理を完了するのに必要な時間は、入力の長さの 2 乗に比例します。不要な計算を減らしたり、中間結果に最適化を適用したりするために、アルゴリズムを再検討する必要がある場合があります。

  2. アルゴリズムに並列処理を導入します。あなたのアルゴリズムは現在、順次実行されるコードの大きなブロックとして実装されています。つまり、(ハードウェア レベルでの命令パイプライン化を禁止する) すべての命令は、前の命令が完了したときにのみ実行できます。スレッドを使用して作業を複数のプロセッサーに分割するようにコードを書き直すか、ほとんどの作業を行う並列化フレームワークを使用することができます。これはポイント 1 よりも効率的ではありません。これは、マシン内のプロセッサの数が一定であるため、アルゴリズムに供給する入力のサイズが増加してもスケーリングされないためです。

  3. より高速なマシンを使用してください。アルゴリズムが他の方法で改善されていない場合、それを高速化する唯一の方法は、より高速に実行することです。

于 2012-09-30T19:36:57.153 に答える
0

これは、動作する並列実装である必要があります。

public class BrownianMotionThread extends Thread
{
    int i;
    int T;
    int N;
    int numberOfProcessors;
    double sqtotal;

    BrownianMotionThread(int i, int T, int N, int numberOfProcessors)
    {
        this.i = i;
        this.T = T;
        this.N = N;
        this.numberOfProcessors = numberOfProcessors;

    }

    public void run()
    {
        double r;
        for (int count=i;count<T;count+= numberOfProcessors) {

            /**started here so that x & y reset at each trial*/

            int x = 0;
            int y = 0;
                /**loop for steps*/
            for (int steps=0;steps<N;steps++) {
                r = Math.random();
            if      (r < 0.25) x--;
            else if (r < 0.50) x++;
            else if (r < 0.75) y--;
            else if (r < 1.00) y++;
                }
            /**squared total distance after each trial*/
            sqtotal = sqtotal + (x*x+y*y);
            }
    }
}

public class BrownianMotion {
    static double sqtotal;
    public static void main(String[] args) {

    /**starts vars for program*/

    final int N = Integer.parseInt(args[0]);
    final int T = Integer.parseInt(args[1]);
    final int numberOfProcessors = Runtime.getRuntime().availableProcessors();
    BrownianMotionThread[] threads = new BrownianMotionThread[numberOfProcessors];
    double avg;

    /**number of trials loop*/
    for(int i = 0; i < numberOfProcessors; i++)
    {
        threads[i] = new BrownianMotionThread(i,T,N,numberOfProcessors);
        threads[i].start();
    }
    for(int i = 0; i < numberOfProcessors; i++)
    {
        try 
        {
            threads[i].join();
        } 
        catch (InterruptedException e) 
        {
            e.printStackTrace();
        }
    }

    for(int i = 0; i < numberOfProcessors; i++)
    {
        sqtotal += threads[i].sqtotal;
    }


    /**average of squared total*/

    avg = sqtotal/T;
    System.out.println(avg);

    }

}
于 2012-09-30T05:42:49.240 に答える