복붙노트

[SCALA] 스칼라를 사용하여 소수를 찾을 수 있습니다. 개선하는 데 도움이

SCALA

스칼라를 사용하여 소수를 찾을 수 있습니다. 개선하는 데 도움이

나는 덜 스칼라에서 지정된 수의 난보다 소수를 찾기 위해이 코드를 썼다.

def findPrime(i : Int) : List[Int] = i match {
    case 2 => List(2)
    case _ => {
    val primeList = findPrime(i-1)
    if(isPrime(i, primeList)) i :: primeList else primeList
    }
}

def isPrime(num : Int, prePrimes : List[Int]) : Boolean = prePrimes.forall(num % _ != 0)

그러나, 나는 a를 findPrime 기능을 느낌, 특히이 부분을 가지고 :

case _ => {
    val primeList = findPrime(i-1)
    if(isPrime(i, primeList)) i :: primeList else primeList
}

꽤 기능 스타일이다.

나는 아직도 함수형 프로그래밍을 배우고있다. 사람이 도움을 기쁘게 할 날이 더 많은 기능 만들기 위해이 코드를 향상시킬 수 있습니다.

많은 감사합니다.

해결법

  1. ==============================

    1.스타일은 나에게 벌금을 보인다. 에라 토 스테 네스의 체는 소수를 찾을 수있는 매우 효율적인 방법이지만 당신이 알려진 소수에 대한 부문을 테스트하고 있기 때문에, 당신의 접근 방식은 너무 잘 작동합니다. 당신의 재귀 함수는 꼬리 재귀되지 않습니다 - 당신은 그러나 조심해야합니다. 꼬리 재귀 함수는 재귀 호출의 결과를 수정하지 않습니다 - 당신의 예제에서 당신은 재귀 호출의 결과에 앞에 추가. 오랜 호출 스택을하고 findPrime 있도록 큰 난을 위해 작동하지 않습니다이 의미합니다. 다음은 꼬리 재귀 솔루션입니다.

    스타일은 나에게 벌금을 보인다. 에라 토 스테 네스의 체는 소수를 찾을 수있는 매우 효율적인 방법이지만 당신이 알려진 소수에 대한 부문을 테스트하고 있기 때문에, 당신의 접근 방식은 너무 잘 작동합니다. 당신의 재귀 함수는 꼬리 재귀되지 않습니다 - 당신은 그러나 조심해야합니다. 꼬리 재귀 함수는 재귀 호출의 결과를 수정하지 않습니다 - 당신의 예제에서 당신은 재귀 호출의 결과에 앞에 추가. 오랜 호출 스택을하고 findPrime 있도록 큰 난을 위해 작동하지 않습니다이 의미합니다. 다음은 꼬리 재귀 솔루션입니다.

    def primesUnder(n: Int): List[Int] = {
  require(n >= 2)

  def rec(i: Int, primes: List[Int]): List[Int] = {
    if (i >= n) primes
    else if (prime(i, primes)) rec(i + 1, i :: primes)
    else rec(i + 1, primes)
  }

  rec(2, List()).reverse
}

def prime(num: Int, factors: List[Int]): Boolean = factors.forall(num % _ != 0)

    이 솔루션은 예뻐하지 않습니다 - 그것은 큰 인수 작업에 솔루션을 얻기 위해 더 세부입니다. 목록 빠른 앞에 추가을 활용하기 위해 뒤로를 구축하고 있기 때문에, 목록의 요구는 반전된다. 다른 방법으로, 당신은 결과를 추가 할 배열, 벡터 또는 ListBuffer를 사용할 수 있습니다. 배열로, 그러나, 당신은 그것을 위해 할당하는 메모리 양을 추정해야합니다. 다행히 우리는 당신이 적당한 크기를 선택할 수 있도록 그 파이가 (N) N / LN (n)이 동일에 대해 알고있다. 배열 및 ListBuffer는 다시 기능적인 스타일에 대한 당신의 욕망을가는 가변 데이터 유형입니다.

    업데이트 : 난 당신이 또한 함수형 프로그래밍 스타일에 대한 당신의 욕망에 반하는 기본 배열에 데이터를 저장해야합니다 생각 에라토스테네스의 체 중 좋은 성능을 얻을 수 있습니다. 하지만 창조적 인 기능 구현이있을 수 있습니다!

    업데이트 : 죄송합니다! 그것을 놓친! 이 방법을 사용하면 단지 당신이 테스트중인 숫자의 제곱근보다 적은 소수로 나눈다면 너무 잘 작동합니다! 나는이 놓친, 불행히도 내가 거꾸로 소수를 저장하고 있습니다 때문에이 작업을 수행하는 내 솔루션을 조정하기 쉽지 않다.

    업데이트 : 여기에 매우 비 기능 솔루션의 그 제곱근까지 적어도에만 검사에서.

    rnative, 당신은 결과를 추가 할 배열, 벡터 또는 ListBuffer를 사용할 수 있습니다. 배열로, 그러나, 당신은 그것을 위해 할당하는 메모리 양을 추정해야합니다. 다행히 우리는 당신이 적당한 크기를 선택할 수 있도록 그 파이가 (N) N / LN (n)이 동일에 대해 알고있다. 배열 및 ListBuffer는 다시 기능적인 스타일에 대한 당신의 욕망을가는 가변 데이터 유형입니다.

    업데이트 : 난 당신이 또한 함수형 프로그래밍 스타일에 대한 당신의 욕망에 반하는 기본 배열에 데이터를 저장해야합니다 생각 에라토스테네스의 체 중 좋은 성능을 얻을 수 있습니다. 하지만 창조적 인 기능 구현이있을 수 있습니다!

    업데이트 : 죄송합니다! 그것을 놓친! 이 방법을 사용하면 단지 당신이 테스트중인 숫자의 제곱근보다 적은 소수로 나눈다면 너무 잘 작동합니다! 나는이 놓친, 불행히도 내가 거꾸로 소수를 저장하고 있습니다 때문에이 작업을 수행하는 내 솔루션을 조정하기 쉽지 않다.

    업데이트 : 여기에 매우 비 기능 솔루션의 그 제곱근까지 적어도에만 검사에서.

    import scala.collection.mutable.ListBuffer

def primesUnder(n: Int): List[Int] = {
  require(n >= 2)

  val primes = ListBuffer(2)
  for (i <- 3 to n) {
    if (prime(i, primes.iterator)) {
      primes += i
    }
  }

  primes.toList
}

// factors must be in sorted order
def prime(num: Int, factors: Iterator[Int]): Boolean = 
  factors.takeWhile(_ <= math.sqrt(num).toInt) forall(num % _ != 0)

    아니면 내가 내 원래의 접근 방식과 벡터를 사용할 수 있습니다. 그들이 그것을 상각 O (1)에도 불구하고 금식 O (1)이 없기 때문에 벡터는 아마 가장 좋은 방법이 아니다.

  2. ==============================

    2.물론 코 세라 Odersky의 '스칼라 함수 프로그래밍의 원칙 "에 제시된 여기 에라토스테네스의 체의 기능 구현은 다음과 같습니다

    물론 코 세라 Odersky의 '스칼라 함수 프로그래밍의 원칙 "에 제시된 여기 에라토스테네스의 체의 기능 구현은 다음과 같습니다

      // Sieving integral numbers
  def sieve(s: Stream[Int]): Stream[Int] = {
    s.head #:: sieve(s.tail.filter(_ % s.head != 0))
  }

  // All primes as a lazy sequence
  val primes = sieve(Stream.from(2))

  // Dumping the first five primes
  print(primes.take(5).toList) // List(2, 3, 5, 7, 11)
  3. ==============================

    3.schmmd 언급, 당신은 꼬리 재귀가되고 싶어요, 당신은 또한 게으른되고 싶어요. 다행히이를위한 완벽한 데이터 구조가있다 : 스트림입니다.

    schmmd 언급, 당신은 꼬리 재귀가되고 싶어요, 당신은 또한 게으른되고 싶어요. 다행히이를위한 완벽한 데이터 구조가있다 : 스트림입니다.

    이 작업은 몇 최적화와 스트림으로 구현 매우 효율적인 소수 계산기입니다 :

    object Prime {
  def is(i: Long): Boolean =
    if (i == 2) true
    else if ((i & 1) == 0) false // efficient div by 2
    else prime(i)

  def primes: Stream[Long] = 2 #:: prime3

  private val prime3: Stream[Long] = {
    @annotation.tailrec
    def nextPrime(i: Long): Long =
      if (prime(i)) i else nextPrime(i + 2) // tail

    def next(i: Long): Stream[Long] =
      i #:: next(nextPrime(i + 2))

    3 #:: next(5)

  }

    // assumes not even, check evenness before calling - perf note: must pass partially applied >= method
  def prime(i: Long): Boolean =
    prime3 takeWhile (math.sqrt(i).>= _) forall { i % _ != 0 }
}

    Prime.is는 주요 체크 술어이며, Prime.primes 모든 소수의 스트림을 반환합니다. prime3는 스트림 덜 난의 제곱근에 비해 모든 주요 약수를 확인하기 위해 주요 술어를 사용하여 계산되는 경우입니다.

  4. ==============================

    4.

      /**
   * @return Bitset p such that p(x) is true iff x is prime
   */
  def sieveOfEratosthenes(n: Int) = {
    val isPrime = mutable.BitSet(2 to n: _*)
    for (p <- 2 to Math.sqrt(n) if isPrime(p)) {
      isPrime --= p*p to n by p
    }
    isPrime.toImmutable
  }
  5. ==============================

    5.체 방법은 (10-100000000 정도까지) 숫자의 작은 목록에 대한 당신의 최선의 방법이다. 참조 : 에라토스테네스의 체

    체 방법은 (10-100000000 정도까지) 숫자의 작은 목록에 대한 당신의 최선의 방법이다. 참조 : 에라토스테네스의 체

    당신이 훨씬 더 큰 숫자를 찾으려면하더라도, 당신은 N ^ 2 여기서 n으로 번호를 테스트하기 위해 약수로이 방법으로 당신이 생성 목록을 사용하면 목록의 한계입니다.

  6. ==============================

    6.; @netzwerg가 아닌 SOE 버전을 올렸습니다, 그래서 SOE와 @Luigi Plinge 기능 코드를 사용하여이 작업을 수행해야한다고 언급했다 - @mfa은 에라토스테네스의 체를 사용하여 언급하고있다 여기에, 나는 또 다른 질문에 대한 답변으로 게시하는 것이 완전히 불가능한 변경 가능한 비트 세트의 내용을 제외하고 상태 (가변보다는 성능에 대한 불변)를 사용하여 SOE의 "거의"기능 버전을 게시 :

    ; @netzwerg가 아닌 SOE 버전을 올렸습니다, 그래서 SOE와 @Luigi Plinge 기능 코드를 사용하여이 작업을 수행해야한다고 언급했다 - @mfa은 에라토스테네스의 체를 사용하여 언급하고있다 여기에, 나는 또 다른 질문에 대한 답변으로 게시하는 것이 완전히 불가능한 변경 가능한 비트 세트의 내용을 제외하고 상태 (가변보다는 성능에 대한 불변)를 사용하여 SOE의 "거의"기능 버전을 게시 :

    object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    }
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
  }
}
  7. ==============================

    7.이건 어때요.

    이건 어때요.

    def getPrimeUnder(n: Int) = {
  require(n >= 2)
  val ol = 3 to n by 2 toList // oddList
  def pn(ol: List[Int], pl: List[Int]): List[Int] = ol match {
    case Nil => pl
    case _ if pl.exists(ol.head % _ == 0) => pn(ol.tail, pl)
    case _ => pn(ol.tail, ol.head :: pl)
  }
  pn(ol, List(2)).reverse
}

    그것은 그것 걸릴 약 2.5 초, 100,000에서 모든 소수를 얻기 위해, 내 Mac에서, 꽤 빨리 나를 위해입니다.

  8. ==============================

    8.스칼라 FP 접근 방식

    스칼라 FP 접근 방식

    // returns the list of primes below `number`
def primes(number: Int): List[Int] = {
    number match {
        case a
        if (a <= 3) => (1 to a).toList
        case x => (1 to x - 1).filter(b => isPrime(b)).toList
    }
}

// checks if a number is prime
def isPrime(number: Int): Boolean = {
    number match {
        case 1 => true
        case x => Nil == {
            2 to math.sqrt(number).toInt filter(y => x % y == 0)
        }
    }
}
  9. ==============================

    9.

    def primeNumber(range: Int): Unit ={
    val primeNumbers: immutable.IndexedSeq[AnyVal] =
      for (number :Int <- 2 to range) yield {
        val isPrime = !Range(2, Math.sqrt(number).toInt).exists(x => number % x == 0)
        if(isPrime)  number
      }
    for(prime <- primeNumbers) println(prime)
  }
  10. ==============================

    10.

    object Primes {
  private lazy val notDivisibleBy2: Stream[Long] = 3L #:: notDivisibleBy2.map(_ + 2)
  private lazy val notDivisibleBy2Or3: Stream[Long] = notDivisibleBy2
      .grouped(3)
      .map(_.slice(1, 3))
      .flatten
      .toStream
  private lazy val notDivisibleBy2Or3Or5: Stream[Long] = notDivisibleBy2Or3
      .grouped(10)
      .map { g =>
        g.slice(1, 7) ++ g.slice(8, 10)
      }
      .flatten
      .toStream

  lazy val primes: Stream[Long] = 2L #::
      notDivisibleBy2.head #::
      notDivisibleBy2Or3.head #::
      notDivisibleBy2Or3Or5.filter { i =>
        i < 49 || primes.takeWhile(_ <= Math.sqrt(i).toLong).forall(i % _ != 0)
      }

  def apply(n: Long): Stream[Long] = primes.takeWhile(_ <= n)

  def getPrimeUnder(n: Long): Long = Primes(n).last
}

    11. from https://stackoverflow.com/questions/9711785/find-prime-numbers-using-scala-help-me-to-improve by cc-by-sa and MIT license

'SCALA' 카테고리의 다른 글

[SCALA] 하나 개의 컬럼이 다른 컬럼의 구성원 인 경우 스파크 dataframe를 필터링하는 방법  (0) 2019.11.23
[SCALA] 이웃와 비교하여 목록 항목을 그룹화  (0) 2019.11.23
[SCALA] 원시 스칼라 타입을 갖는 구현 방법  (0) 2019.11.23
[SCALA] 왜 scaladoc 방법 서명이 잘못입니까?  (0) 2019.11.23
[SCALA] 스칼라 스크립트와 응용 프로그램 사이의 차이  (0) 2019.11.23
,

티스토리툴바