Scala에서 통합 및 루프를 최적화하려면 어떻게 해야 합니까?

Scala에서 통합 및 루프를 최적화하려면 어떻게 해야 합니까?

스칼라는 자바만큼 빠르다고 생각됩니다.저는 원래 자바에서 다루었던 Scala의 Project Oiler 문제를 다시 살펴보고 있습니다.구체적으로 문제 5: "1부터 20까지의 모든 숫자로 균등하게 나눌 수 있는 가장 작은 양의 숫자는?"

다음은 제 기계에서 완료하는 데 0.7초가 걸리는 Java 솔루션입니다.

public class P005_evenly_divisible implements Runnable{
    final int t = 20;

    public void run() {
        int i = 10;
        while(!isEvenlyDivisible(i, t)){
            i += 2;
        }
        System.out.println(i);
    }

    boolean isEvenlyDivisible(int a, int b){
        for (int i = 2; i <= b; i++) {
            if (a % i != 0) 
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        new P005_evenly_divisible().run();
    }
}

여기 Scala로의 직접 번역이 있습니다.이것은 103초(147배 더 길다)입니다.

object P005_JavaStyle {
    val t:Int = 20;
    def run {
        var i = 10
        while(!isEvenlyDivisible(i,t))
            i += 2
        println(i)
    }
    def isEvenlyDivisible(a:Int, b:Int):Boolean = {
        for (i <- 2 to b)
            if (a % i != 0)
                return false
        return true
    }
    def main(args : Array[String]) {
        run
    }
}

마지막으로 39초(55배)가 걸리는 기능 프로그래밍을 소개합니다.

object P005 extends App{
    def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
    def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
    println (find (2))
}

Windows 7 64비트에서 Scala 2.9.0.1 사용.퍼포먼스를 향상시키려면 어떻게 해야 하나요?내가 뭘 잘못하고 있나요?아니면 Java가 훨씬 더 빠를까요?

이 경우 문제는 for-expression 내에서 되돌아오는 것입니다.다음으로 NonLocalReturnException의 슬로우로 변환됩니다.이거는 인클로징 메서드로 검출됩니다.옵티마이저는 포어치를 제거할 수 있지만 던지기/캐치를 제거할 수는 없습니다.그리고 던지기/잡기는 비싸다.그러나 이러한 중첩된 반환은 Scala 프로그램에서는 드물기 때문에 옵티마이저는 아직 이 경우를 다루지 않았습니다.옵티마이저를 개선하기 위한 작업이 진행 중이며, 곧 이 문제가 해결되기를 바랍니다.

는 " " "를 입니다.for의 isEvenlyDivisible · ★★forwhile루프를 사용하면 Java와의 성능 차이를 없앨 수 있습니다.

와 for프 scal, Scalafor는 사실 방법을 위한 이다; 이 은 보상을 이라고 부른다; 이 경우, 여러분은 보상이라고 .foreach의 Range스칼라for매우 일반적이지만 때로는 고통스러운 퍼포먼스로 이어지기도 합니다.

해 보세요.-optimize버전 2.9.scala의 는 사용 중인 하고 최적화하는 데 이 있는 에 따라 수 .관측된 성능은 사용 중인 특정 JVM에 따라 달라질 수 있으며, JIT 옵티마이저는 핫스팟을 식별하고 최적화할 수 있는 충분한 "웜업" 시간을 갖습니다.

에 따르면 은 Scala의 개선을 .for퍼포먼스를 심플한 케이스로 실현합니다.

• http://groups.google.com/group/scala-user/browse_thread/thread/86adb44d72ef4498
• http://groups.google.com/group/scala-language/browse_thread/thread/94740a10205dddd2

다음은 버그 트래커의 문제입니다.https://issues.scala-lang.org/browse/SI-4633

업데이트 5/28:

• 단기 솔루션으로서 ScalaCL 플러그인(alpha)은 단순한 Scala 루프를 다음과 같은 것으로 변환합니다.whiledisplaces.displaces
• 잠재적인 장기 솔루션으로서 EPFL과 스탠포드 팀은 매우 높은 성능을 위해 "가상" Scala의 런타임 컴파일을 가능하게 하는 프로젝트에 협력하고 있습니다.예를 들어 실행 시 여러 개의 관용적인 기능 루프를 최적의 JVM 바이트 코드 또는 GPU 등의 다른 타깃에 융합할 수 있습니다.이 시스템은 확장 가능하며 사용자 정의 DSL 및 변환이 가능합니다.출판물과 스탠포드 코스노트를 확인해 주세요.예비 코드는 Github에서 이용할 수 있으며, 향후 몇 개월 내에 출시될 예정입니다.

후속으로 -optimize 플래그를 시도해보니 실행 시간이 103초에서 76초로 단축되었지만 Java나 while loop보다 107배 느립니다.

그리고 '기능' 버전을 살펴보았습니다.

object P005 extends App{
  def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

간결하게 '포울'을 없애는 방법을 찾고 있습니다.저는 비참하게 실패해서

object P005_V2 extends App {
  def isDivis(x:Int):Boolean = {
    var i = 1
    while(i <= 20) {
      if (x % i != 0) return false
      i += 1
    }
    return true
  }
  def find(n:Int):Int = if (isDivis(n)) n else find (n+2)
  println (find (2))
}

내 교활한 5줄 용액이 12줄로 부풀어 올랐어단, 이 버전은 원래 Java 버전과 같은 속도로 실행되며 위의 버전보다 56배 빠른 "forall"(40.2초)을 사용합니다(Java보다 빠른 이유에 대해서는 아래 편집 참조).

물론 다음 단계는 위의 내용을 Java로 변환하는 것입니다만, Java는 이를 처리하지 못하고 StackOverflowError를 22000 마크 부근에 n으로 설정합니다.

그리고 잠시 머리를 긁적거리더니 "while"을 조금 더 많은 테일 재귀로 대체했습니다. 이렇게 하면 몇 줄의 줄이 절약되고, 같은 속도로 달리기도 하지만, 현실을 직시해 보면 더 이해하기 어렵습니다.

object P005_V3 extends App {
  def isDivis(x:Int, i:Int):Boolean = 
    if(i > 20) true
    else if(x % i != 0) false
    else isDivis(x, i+1)

  def find(n:Int):Int = if (isDivis(n, 2)) n else find (n+2)
  println (find (2))
}

따라서 Scala의 꼬리 재귀는 승리하지만, "for" 루프와 같은 단순한 방법(및 "forall" 방법)이 본질적으로 고장나므로 고급스럽고 장황한 "whiles" 또는 "tail recursion"으로 대체해야 한다는 사실에 놀랐습니다.제가 Scala를 사용하는 이유는 대부분 구문이 간결하기 때문입니다만, 만약 코드가 100배 느리게 실행된다면 좋지 않습니다!

편집: (삭제)

편집: 이전 실행 시간 2.5초와 0.7초의 불일치는 32비트 또는 64비트 JVM 중 어느 쪽을 사용했는지에 전적으로 기인합니다.명령줄의 scala는 JAVA_에 의해 설정된 모든 것을 사용합니다.HOME. 단, Java는 어떤 경우에도 64비트를 사용합니다.IDE에는 독자적인 설정이 있습니다.몇 가지 측정값: Scala 실행 시간(Eclipse)

이해에 대한 답은 맞지만, 그것이 전부는 아니다.「 」의.returnisEvenlyDivisible료가아아 아아아다다「 」의 forscala 컴파일러가 로컬이 아닌 반환을 생성하도록 강제합니다(즉, 함수 외부에서 반환).

이것은 예외를 사용하여 루프를 종료함으로써 이루어집니다.다음과 같이 자체 제어 추상화를 구축하는 경우에도 동일한 현상이 발생합니다.

def loop[T](times: Int, default: T)(body: ()=>T) : T = {
    var count = 0
    var result: T = default
    while(count < times) {
        result = body()
        count += 1
    }
    result
}

def foo() : Int= {
    loop(5, 0) {
        println("Hi")
        return 5
    }
}

foo()

"Hi"라고 한 번만 출력됩니다.

에 주의:returnfoo를 종료합니다.foo(어느쪽이든)로 묶은 리터럴이기 에, 「」의 됩니다.loop를 통해 는 로컬 을 생성하게 컴파일러는 로컬 이외의 반환을 합니다.return를 강제로 합니다.foo 「 」만이.body.

Java(예: JVM)에서는 이러한 동작을 구현하는 유일한 방법은 예외를 두는 것입니다.

로로로 isEvenlyDivisible:

def isEvenlyDivisible(a:Int, b:Int):Boolean = {
  for (i <- 2 to b) 
    if (a % i != 0) return false
  return true
}

if (a % i != 0) return false는 반환이 있는 함수 리터럴이기 때문에 반환이 히트할 때마다 런타임은 예외를 슬로우 및 캐치해야 하므로 상당한 양의 GC 오버헤드가 발생합니다.

「 」의 속도를 높이는 forall다음 중 하나:

오리지널 : 41.3초

def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}

매번 새로운 범위를 작성하지 않도록 범위 사전 설치: 9.0초

val r = (1 to 20)
def isDivis(x:Int) = r forall {x % _ == 0}

범위가 아닌 목록으로 변환: 4.8초

val rl = (1 to 20).toList
def isDivis(x:Int) = rl forall {x % _ == 0}

다른 컬렉션을 몇 개 시도했지만 List가 가장 빨랐습니다(Range 이상의 고차 함수를 모두 사용하지 않는 경우보다 7배 느리지만).

Scala는 처음이지만 컴파일러는 메서드의 Range 리터럴을 자동으로 가장 바깥쪽 범위의 Range 상수로 대체함으로써 빠르고 큰 성능 향상을 쉽게 구현할 수 있을 것입니다.아니면 Java의 Strings Literal처럼 인턴을 하는 것이 좋습니다.

---

각주:어레이는 Range와 거의 동일하지만 흥미로운 점은 새로운 테크놀로지를 구현하고 있다는 점입니다.forall메서드(아래 참조)를 사용하면 64비트에서 실행 속도가 24%, 32비트에서 실행 속도가 8% 빨라집니다.계수를 20에서 15로 줄여서 계산 크기를 줄였더니 차이가 없어졌기 때문에 쓰레기 수거 효과일지도 모릅니다.원인에 관계없이 장시간 최대 부하 상태에서 작동할 경우 중요합니다.

List에 대한 유사한 포주 또한 약 10% 더 나은 성능을 보였습니다.

  val ra = (1 to 20).toArray
  def isDivis(x:Int) = ra forall2 {x % _ == 0}

  case class PimpedSeq[A](s: IndexedSeq[A]) {
    def forall2 (p: A => Boolean): Boolean = {      
      var i = 0
      while (i < s.length) {
        if (!p(s(i))) return false
        i += 1
      }
      true
    }    
  }  
  implicit def arrayToPimpedSeq[A](in: Array[A]): PimpedSeq[A] = PimpedSeq(in)  

이런 문제로 Scala에 대한 신뢰를 잃을 수 있는 분들을 위해 말씀드리고 싶습니다.이러한 문제는 거의 모든 기능 언어의 퍼포먼스에서 발생합니다.Haskell에서 폴드를 최적화할 경우, 종종 반복적인 테일콜 최적화 루프로 다시 작성해야 합니다.그렇지 않으면 성능 및 메모리 문제가 발생합니다.

FP가 아직 최적화되지 않은 것은 유감스럽지만 이는 Scala만의 문제가 아닙니다.

Scala 고유의 문제는 이미 논의되었지만, 가장 큰 문제는 brute-force 알고리즘을 사용하는 것이 그다지 바람직하지 않다는 것입니다.이것을 고려해 주세요(원래 Java 코드보다 훨씬 빠릅니다).

def gcd(a: Int, b: Int): Int = {
    if (a == 0)
        b
    else
        gcd(b % a, a)
}
print (1 to 20 reduce ((a, b) => {
  a / gcd(a, b) * b
}))

프로젝트 오일러를 위한 솔루션 스칼라에 제시된 원라이너를 사용해 보십시오.

주어진 시간은 적어도 당신의 시간보다 빠릅니다. while loop과는 거리가 멀지만..:)

언급URL : https://stackoverflow.com/questions/6146182/how-to-optimize-for-comprehensions-and-loops-in-scala