Пространство кучи с изменяемым.HashMap

Question

Я создаю HashMap, где я могу оценить требуемый размер для факториалов:

  import scala.collection.mutable.HashMap

  val mm = new HashMap [Int, BigInt] 
  mm.put (0, 1)
  def fak (i: Int) : BigInt = mm.getOrElseUpdate (i, i * fak (i-1))

Я часто запрашиваю факториал (fak) простых чисел в порядке возрастания и люблю получать довольно высокие значения (> 10 млн. Факториалов).

Вызов его с 70000 приводит к ошибке OutOfMemory: пространство кучи Java. Я начал программу с

scala -J-Xmx4G TestFak 70000

С 60000 в качестве параметра это работает. Я предполагаю, что он создает 70000 MutableMaps, которые часто выбрасывают и собирают мусор. Так как я заранее знаю требуемый размер, возможно ли с самого начала сгенерировать mutableMap правильного размера?

Ошибка выдается в строке mm.getOrElseUpdate.

Версия: Scala версия 2.11.6 (64-битная виртуальная машина OpenJDK, Java 1.8.0_66-internal)

Answer 1

Факториал 70000 огромен! BigInt требуется для хранения, которое будет довольно большим само по себе! Просто чтобы дать вам идею, BigInt вероятно, поддерживается Array[Int] на Яве. Это означает, что общий размер, необходимый для хранения 1!, 2!, ..., 70000! будет sum_(1 to n) of 4 * log_(2^32) n! за n = 70000, что составляет порядка четырех гигабайт.