Project Euler 7 Scala Проблема

Question

Я пытался решить проблему Project Euler № 7, используя scala 2.8

Первое реализованное мной решение занимает ~ 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;
}

Позже я попробовал ту же проблему, не сохраняя простые числа в буфере массива. Это займет 0,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?

Answer 1

Проблема здесь в том, что ArrayBuffer параметризован, поэтому в действительности он хранит ссылки на Object. Любая ссылка на Int автоматически упаковывается и распаковывается по мере необходимости, что делает его очень медленным. Это невероятно медленно с Scala 2.7, который использует для этого примитив Java, который делает это очень медленно. Scala 2.8 использует другой подход, делая его быстрее. Но любой бокс / распаковка замедлит вас. Кроме того, вы сначала просматриваете ArrayBuffer в куче, а затем снова ищите java.lang.Integer, содержащий Int - два обращения к памяти, что делает его медленнее, чем другое решение.

Когда коллекции Scala станут специализированными, это должно произойти намного быстрее. Будет ли этого достаточно, чтобы победить вашу вторую версию или нет, я не знаю.

Теперь, что вы можете сделать, чтобы обойти это - использовать Array вместо этого. Поскольку Java Array не стирается, вы избегаете упаковки / распаковки.

Кроме того, когда вы используете для-понимания, ваш код эффективно сохраняется в методе, который вызывается для каждого элемента. Таким образом, вы также делаете много вызовов методов, что является еще одной причиной, по которой это происходит медленнее. Увы, кто-то написал плагин для Scala, который оптимизирует хотя бы один случай для понимания, чтобы избежать этого.

Answer 2

Использование массива должно заставить его работать примерно за ноль секунд с правильным алгоритмом. Например, это занимает около 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)
  }
}

Результат (при втором вызове; первый имеет некоторые издержки):

scala> Primes.timedGet(10001)
res1: (Int, Double) = (104743,0.00683394)

Answer 3

Вот рекурсивное решение (используя функцию isPrime из вашего первого решения). Кажется, что хороший стиль Scala предпочитает неизменность (то есть стараться не использовать var s), поэтому я сделал это здесь (на самом деле var s или val s!). У меня нет установки Scala здесь, поэтому не могу сказать, если это на самом деле быстрее!

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)
}

Answer 4

Я думаю, вы должны думать из коробки:)

Поскольку проблема решаема, вы можете использовать Сито Эратосфена , чтобы решить ее очень эффективно.