Proyecto Euler 7 Problema de Scala

Question

Estaba tratando de resolver el problema del Proyecto Euler número 7 usando Scala 2.8

La primera solución implementada por mí toma ~ 8 segundos

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

Más tarde intenté el mismo problema sin almacenar números primos en el búfer de matriz. Esto toma .118 segundos.

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

Intenté usar varias implementaciones mutables de matriz/lista en Scala pero no pude hacer la solución una más rápida. No creo que almacenar int en una matriz de tamaño 10001 pueda hacer que el programa sea lento. ¿Hay alguna mejor manera de usar listas/matrices en Scala?

Answer 1

El uso de la matriz debería hacer que funcione en aproximadamente cero segundos con el algoritmo derecho. Esto, por ejemplo, toma alrededor de 7 milisegundos en mi sistema:

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

Resultado (en la segunda llamada; primero tiene algo de sobrecarga):

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

Answer 2

El problema aquí es que ArrayBuffer está parametrizado, entonces lo que realmente almacena son referencias Object. Cualquier referencia a un Int está en caja automáticamente y se desempeña según sea necesario, lo que lo hace muy lento. Es increíblemente lento con Scala 2.7, que usa un Java primitivo para hacerlo, lo que lo hace muy lentamente. Scala 2.8 adopta otro enfoque, haciéndolo más rápido. Pero cualquier boxeo/Unboxing lo retrasará. Además, primero estás buscando el ArrayBuffer en el montón, y luego mirando hacia arriba para java.lang.Integer que contiene el Int - Dos accesos de memoria, lo que lo hace mucho más lento que su otra solución.

Cuando las colecciones de Scala se especializan, debería ser mucho más rápido. Si debería ser suficiente para vencer a su segunda versión o no, no lo sé.

Ahora, lo que puede hacer para evitarlo es usar Array en cambio. Porque Java's Array no se borra, evita el boxeo/unboxing.

Además, cuando usa para competencias, su código se almacena efectivamente en un método que se requiere para cada elemento. Por lo tanto, también está haciendo muchas llamadas de métodos, que es otra razón por la que esto es más lento. Por desgracia, alguien escribió un complemento para SCALA que optimiza al menos un caso de comprensiones para evitarlo.

Answer 3

Creo que tienes que pensar fuera de la caja :)

Porque el problema es manejable, puede usar Tamiz de Eratosthenes para resolverlo de manera muy eficiente.

Answer 4

Aquí hay una solución recursiva (utilizando la función ISPRIME de su primera solución). Parece ser un buen estilo de Scala preferir la inmutabilidad (es decir, tratar de no usar vars) Así que he hecho eso aquí (de hecho no hay vars o val¡s!). Sin embargo, no tengo una instalación de Scala aquí, ¡así que no puedo decir si esto es realmente más rápido!

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