Scala неожиданное переполнение стека - PullRequest
Новая
       2

Scala неожиданное переполнение стека

2 голосов
/ 15 мая 2011

Я написал эту базовую программу на Scala: 

import scala.collection.mutable.HashMap

object HelloWorld {

  val treasureMap = new HashMap[BigInt, BigInt]

  def main(args: Array[String]) {
    println(fibCache(10))
  }

  def fibCache(n: BigInt): BigInt = {
    if (n == 0 || n == 1) {
      return n
    }
    return treasureMap.getOrElseUpdate(n, fibCache(n - 1) + fibCache(n - 2))
  }
}

и я ожидаю, что при действительно больших значениях у меня будет OutOfMemoryError или что-то подобное, но вместо этого я вижу это: 

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.compareMagnitude(Unknown Source)
    at java.math.BigInteger.compareTo(Unknown Source)
    at scala.math.BigInt.compare(BigInt.scala:141)
    at scala.math.BigInt.$less$eq(BigInt.scala:145)
    at scala.math.BigInt.fitsInLong(BigInt.scala:130)
    at scala.math.BigInt.hashCode(BigInt.scala:120)
    at scala.runtime.BoxesRunTime.hashFromNumber(Unknown Source)
    at scala.collection.mutable.HashTable$HashUtils$class.elemHashCode(HashTable.scala:366)
    at scala.collection.mutable.HashMap.elemHashCode(HashMap.scala:43)
    at scala.collection.mutable.HashTable$class.findEntry(HashTable.scala:108)
    at scala.collection.mutable.HashMap.findEntry(HashMap.scala:43)
    at scala.collection.mutable.HashMap.get(HashMap.scala:63)
    at scala.collection.mutable.MapLike$class.getOrElseUpdate(MapLike.scala:186)
    at scala.collection.mutable.HashMap.getOrElseUpdate(HashMap.scala:43)

Может кто-нибудь помочь объяснить, почему? Кроме того, есть ли настройка времени выполнения, которую я могу использовать, чтобы облегчить это? Поможет ли -Xss?

1 Ответ

7 голосов
/ 15 мая 2011

StackOverflowError - это вариация на тему нехватки памяти, она просто точно определяет, какая область памяти исчерпана.

Так что да, -Xss поможет , но есть лучший способ ....

На этой странице есть несколько альтернативных реализаций, которые вы можете попробовать: http://en.literateprograms.org/Fibonacci_numbers_(Scala)

Вы захотите использовать хвостовой рекурсивный или потоковый вариант, чтобы уменьшить размер стека.

...