2

私はscala2.8を使用してプロジェクトオイラーの問題番号7を解決しようとしていました

私が実装した最初のソリューションは約8秒かかります

def problem_7:Int = {
    var num = 17;
    var primes = new ArrayBuffer[Int]();
    primes += 2
    primes += 3
    primes += 5
    primes += 7
    primes += 11
    primes += 13

    while (primes.size < 10001){

        if (isPrime(num, primes)) primes += num
        if (isPrime(num+2, primes)) primes += num+2

        num += 6
    }
    return primes.last;
}

def isPrime(num:Int, primes:ArrayBuffer[Int]):Boolean = {
    // if n == 2 return false;
    // if n == 3 return false;
    var r = Math.sqrt(num)  
    for (i <- primes){
        if(i <= r ){
            if (num % i == 0) return false;
        }
    }
    return true;
}

後で、素数を配列バッファに格納せずに同じ問題を試しました。これには.118秒かかります。

def problem_7_alt:Int = {
    var limit = 10001;
    var count = 6;
    var num:Int = 17;

    while(count < limit){

        if (isPrime2(num)) count += 1;
        if (isPrime2(num+2)) count += 1;

        num += 6;
    }
    return num;
}

def isPrime2(n:Int):Boolean = {
    // if n == 2 return false;
    // if n == 3 return false;

    var r = Math.sqrt(n)
    var f = 5;
    while (f <= r){
        if (n % f == 0) {
            return false;
        } else if (n % (f+2) == 0) {
            return false;
        }
            f += 6;
    }
    return true;
}

Scalaでさまざまな可変配列/リストの実装を使用してみましたが、ソリューションをより速くすることができませんでした。Intをサイズ10001の配列に格納すると、プログラムが遅くなるとは思いません。Scalaでリスト/配列を使用するためのより良い方法はありますか？

4

4 に答える 4

5

ここでの問題は、ArrayBufferパラメータ化されているため、実際に格納されるのはへの参照Objectです。への参照は、Int必要に応じて自動的にボックス化およびボックス化解除されるため、非常に遅くなります。これを行うためにJavaプリミティブを使用するScala2.7では、非常に遅くなります。Scala 2.8は別のアプローチを採用しており、より高速になっています。しかし、ボクシング/アンボクシングはあなたを遅くします。さらに、最初ArrayBufferにヒープ内を検索し、次にもう一度検索して、-2つのメモリアクセスがjava.lang.Integer含まれていることを確認します。これにより、他のソリューションよりもはるかに低速になります。Int

Scalaコレクションが特殊化されると、はるかに高速になるはずです。2番目のバージョンを打ち負かすのに十分かどうかはわかりません。

さて、それを回避するためにあなたがするかもしれないことはArray代わりに使うことです。JavaArrayは消去されないため、ボックス化/ボックス化解除を回避します。

また、for-comprehensionsを使用すると、コードは要素ごとに呼び出されるメソッドに効果的に格納されます。したがって、多くのメソッド呼び出しも行っています。これが、これが遅いもう1つの理由です。悲しいかな、誰かがScalaのプラグインを作成しました。これは、それを回避するために、少なくとも1つのfor-comprehensionsのケースを最適化します。

于 2010-03-12T00:21:44.947 に答える
2

Arrayを使用すると、適切なアルゴリズムで約0秒で動作するはずです。たとえば、これは私のシステムでは約7ミリ秒かかります。

class Primes(bufsize: Int) {
  var n = 1
  val pbuf = new Array[Int](bufsize max 1)
  pbuf(0) = 2
  def isPrime(num: Int): Boolean = {
    var i = 0
    while (i < n && pbuf(i)*pbuf(i) <= num) {
      if (num % pbuf(i) == 0) return false
      i += 1
    }
    if (pbuf(i)*pbuf(i) < num) {
      i = pbuf(i)
      while (i*i <= num) {
        if (num % i == 0) return false
        i += 2
      }
    }
    return true;
  }
  def fillBuf {
    var i = 3
    n = 1
    while (n < bufsize) {
      if (isPrime(i)) { pbuf(n) = i; n += 1 }
      i += 2
    }
  }
  def lastPrime = { if (n<bufsize) fillBuf ; pbuf(pbuf.length-1) }
}
object Primes {
  def timedGet(num: Int) = {
    val t0 = System.nanoTime
    val p = (new Primes(num)).lastPrime
    val t1 = System.nanoTime
    (p , (t1-t0)*1e-9)
  }
}

結果（2回目の呼び出しで、最初の呼び出しにはオーバーヘッドがあります）：

scala> Primes.timedGet(10001)
res1: (Int, Double) = (104743,0.00683394)
于 2010-03-12T03:18:17.497 に答える
1

私はあなたが箱から出して考える必要があると思います:)

問題は管理しやすいので、エラトステネスのふるいを使用して非常に効率的に解決できます。

于 2010-03-11T20:02:48.930 に答える
1

これが再帰的な解決策です（最初の解決策のisPrime関数を使用します）。不変性を好む（つまり、sを使用しないようにする）のは良いScalaスタイルのように思われるので、ここでそれを行いました（実際、 sまたはsvarはありません！）。私はここにScalaをインストールしていませんが、これが実際にもっと速いかどうかはわかりません！varval

def problem_7:Int = { 
  def isPrime_(n: Int) = (n % 6 == 1 || n % 6 == 5) && isPrime(n)
  def process(n: Int, acc: List[Int]): Int = {
    if (acc.size == 10001) acc.head
    else process(n+1, if isPrime_(n) n :: acc else acc) 
  }
  process(1, Nil)
}
于 2010-03-11T22:11:40.137 に答える