性能如何避免java。计算Scala中所有可能的组合时，lang.OutOfMemoryError异常？

Question

我知道有很多关于java.lang.OutOfMemoryError: GC overhead limit exceeded（例如How to avoid java.lang.OutOfMemoryError?）的相关问题，我知道我的问题是由我糟糕的实现造成的，但我不知道如何解决它

所以，我的目标是从列表中获得所有可能的重复组合。我通过使用这个question的Mark Lister在answer中提出的代码实现了这个任务。它工作得很好，但显然，使用包含52个元素的列表来获得10个范围内的所有组合对我的计算机来说太多了。有没有办法解决这个问题

可能比收集大量的List组合更好，我可以在生成组合时处理每个word

这是我的代码：

object MyApp extends App {

  val letters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".toList

  run(10)

  def mycomb[T](n: Int, l: List[T]): List[List[T]] =
    n match {
      case 0 => List(List())
      case _ => for (el <- l;
                     sl <- mycomb(n - 1, l dropWhile {
                       _ != el
                     }))
        yield el :: sl
    }

  def comb[T](n: Int, l: List[T]): List[List[T]] = mycomb(n, l.distinct)

  def run(n: Int): Unit = {

    for (i <- 1 to n) {
      val combo = comb(i, letters)

      combo.par.foreach { word =>
        println(word.mkString(""))
        // Process each word one by one in parallel
      }
    }
  }

}

Answer 1

我为所有可能的组合找到了一些时间和解决方案，没有重复：

  val digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

  def concat[T](it1: Iterator[T], it2: => Iterator[T]): Iterator[T] = new Iterator[T] {
    def hasNext: Boolean = it1.hasNext || it2.hasNext

    def next(): T = if (it1.hasNext) {
      it1.next()
    } else {
      it2.next()
    }
  }

  def combinationWithoutRepetitions[T](k: Int, seq: Seq[T]): Iterator[Seq[T]] = {
    def combination(k: Int, acc: Seq[T], tail: Seq[T]): Iterator[Seq[T]] = k match {
      case 0 =>
        Iterator.empty
      case 1 =>
        tail.iterator.map { t => t +: acc }
      case _ if tail.nonEmpty =>
        val it1 = combination(k - 1, tail.head +: acc, tail.tail)
        lazy val it2 = combination(k, Seq.empty, tail.tail)
        concat(it1, it2)
      case _ =>
        Iterator.empty
    }

    combination(k, Seq.empty, seq)
  }

  //TEST
  val iterator = combinationWithoutRepetitions(10, digits.toSeq) // it should return immediatelly
  println(s"${iterator.next()}")
  println(s"${iterator.next()}")

  combinationWithoutRepetitions(2, digits.toSeq).foreach{
         el => println(s"$el")
  }

我使用惰性加载。函数concat通过两个迭代器创建迭代器——第一个迭代器由第一个迭代器迭代，当这个迭代器为空时——开始第二个迭代器迭代

更新

重复组合（基于之前的功能）：

  def combinationWithRepetitions[T](k: Int, sequence: Seq[T]): Iterator[Seq[T]] = new Iterator[Seq[T]] {
    val without = combinationWithoutRepetitions(k, sequence)
    var combination: Iterator[Seq[T]] = Iterator.empty

    def hasNext: Boolean = {
      combination.hasNext || without.hasNext
    }

    def next(): Seq[T] = {
      if (combination.isEmpty) {
        combination = without.next().permutations
      }
      combination.next()
    }
  }