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. 创建固定线程池
  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

这应该是一个有效的并行实现：

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 回答
0

至少有三种方法可以让你的代码运行得更快，从更有效到最不有效：

  1. 降低算法的复杂度。现在，您的算法具有O(N^2)时间复杂度：这意味着完成处理所需的时间与输入长度的平方成正比。您可能需要重新访问算法以减少不必要的计算或对中间结果应用优化。

  2. 在算法中引入并行性。您的算法目前被实现为按顺序执行的一大块代码；也就是说（除了硬件级别的指令流水线）每条指令只有在前一条指令完成时才能执行。您可以重写代码以使用线程在多个处理器之间拆分工作，或者您可以使用为您完成大部分工作的并行化框架。这比第 1 点效率低。因为机器中的处理器数量是恒定的，因此当您提供给算法的输入大小增加时，它不会扩展。

  3. 使用更快的机器。如果算法没有以其他方式改进，那么加速它的唯一方法就是运行得更快。

于 2012-09-30T19:36:57.153 回答