java - 高效并行素因数分解

Question

我正在尝试用Java制作质因数分解的并行版本，并且有一个工作程序。然而，该程序非常慢——比我的顺序版本慢得多。我确实明白这可能与线程优化和线程数量有关(我尝试使用 ExecutorService 但我不认为我真正掌握了它的窍门)。谁能指出优化这段代码的方法？

class HovedFaktorArbeider implements Runnable //Class for first step factorization
  {
    int fra;
    int til;
    int id;
    List<Long> tempFaktorer; //Must be long since we'll stumble upon primes larger than int.MAX_VALUE accidentally
    long[] lokaleFaktorer;
    CyclicBarrier faktorBarrier = new CyclicBarrier(k+1);
    ExecutorService executorService = Executors.newFixedThreadPool(2);
    long g;

    public HovedFaktorArbeider(int fra, int til, int id)
    {
      this.fra = fra;
      this.til = til;
      this.id = id;
    }

    public void run()
    {
      try
      {
        //int tempK = 2; //Erstatter bare k for aa sjekke
        long tempN = (long) n;
        g = (tempN*tempN)-100;
        long tall = g + (long) fra; //The long numbers to be factorized
        for(int i = fra; i <= til; i++) //For the number split
        {
          int tempFra = 0;
          int tempTil = 0;
          int rest = 0;
          int faktor = 0;
          if(primes.size() % k > 0)  //If not perfect division
          {
            rest = (primes.size() % k);  //Saving remainder
            faktor = (primes.size()/k);  //Saving divisor, spreading remainder
            rest--; //Decrement remainder
          }
          else  //If perfect divison
            faktor = primes.size()/k;

          tempTil = faktor; //Setting end value

          tempFaktorer = new ArrayList<Long>();
          for(int ii = 0; ii < k; ii++) //For the prime number split
          {
            //executorService.submit(new HjelpeFaktorArbeider(tempFra, tempTil, tall, ii));
            new Thread(new HjelpeFaktorArbeider(tempFra, tempTil, tall, ii)).start();
            tempFra = tempTil + 1; //Set new value for start
            if(rest > 0)
            {
              tempTil += faktor + 1; //Spreading remainder
              rest--;
            }
            else
              tempTil += faktor; //New end value
          }
          faktorBarrier.await();
          lokaleFaktorer = new long[tempFaktorer.size()];
          for(int j = 0; j < tempFaktorer.size(); j++)
          {
            lokaleFaktorer[j] = tempFaktorer.get(j);
          }
          faktorer[i] = lokaleFaktorer; //TNB: i does not start at 0, so placement should be correct
          tall++;
        }
        mainBarrier.await();
        executorService.shutdown();
      }
      catch(Exception e){e.printStackTrace();}
    }

    public synchronized void oppdaterTempFaktorer(long tall)
    {
      tempFaktorer.add(tall);
    }

    class HjelpeFaktorArbeider implements Runnable //Class for second step factorization
    {
      int fra;
      int til;
      int id;
      long tall;


      public HjelpeFaktorArbeider(int fra, int til, long tall, int id)
      {
        this.fra = fra;
        this.til = til;
        this.id = id;
        this.tall = tall;
      }

      public void run()
      {
        try
        {
          long t = tall;
          for(int i = fra; i < til; i++)
          {
            int primtall = primes.get(i);

            while(t % primtall == 0)
            {
              try
              {
                oppdaterTempFaktorer((long) primtall);
              }
              catch(Exception e){e.printStackTrace();}

              t = t/primtall;
            }
          }
          runBarrier.await();
          if(t > 1 && id == 0 && !tempFaktorer.contains(t))
          {
            try
            {
              oppdaterTempFaktorer(t);
            }
            catch(Exception e){e.printStackTrace();}
          }
          faktorBarrier.await();
        }
        catch(Exception e){e.printStackTrace();}
      }
    }
  }

到目前为止，我已经通过埃拉斯托尼筛找到了一个素数列表，一个极限 n 和核心 k(我的机器上有 8 个)。

P.S.:之所以有两个 Runnable 类，是因为我需要每个分解都由多个线程执行。

Answer 1

如果您对并发感兴趣，我建议您查看其他并发模型，例如 Futures 或 Actors。线程和锁是 SOooo0o 2007。

至于如何使并行代码更快，这是一个值(value)数十亿美元的问题，有很多方法。这完全取决于您的问题和架构。

因此，从您的问题开始，正如您所看到的那样，利用并行架构并不是一个很棒的问题，因为例如您有 9 个线程，并且您检查数字 2,3,4,5,6,7 ,8,9,10，这已经很糟糕了，因为你不必检查 4,6,8,9,10，因为 2 和 3 会告诉你那些非常糟糕(好吧，你可能不会检查偶数，但只是为了证明我的观点)。因此，有些问题不能很好地利用并行代码，正如您在此处看到的那样。

关于如何有效地并行化 Java 代码的问题，最广为接受的答案是“不”。现在的程序员更关心的是不阻塞线程，这些线程通常围绕着不要调用我，我们会调用你原则。但如何为数学问题编写高效的并行代码是一个过于宽泛的计算机科学问题。

但总的来说，你的问题太宽泛了。