Scala：是什么让 Collat​​z 序列的算法如此低效？

Question

我正在尝试解决 collatz problem on project Euler:

的变体

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

我的尝试是找到 最长的 Collat​​z 序列，该序列小于 一百万

为此，我在 Scala 中编写了一个强力解决方案并对其进行了优化。

虽然优化版本非常快速有效地解决了问题，但暴力解决方案从未完成，最终导致内存不足错误：

object LongestCollatz {
  def apply(upperbound: Long) = {
    bruteForce(upperbound)
  }

  def bruteForce(upperBound: Long) = (1l to upperBound)
    .map(toCollatzSequence)
    .map(list => list.length)
    .max

  def toCollatzSequence(start: Long): ListBuffer[Long] = {
    var term = start
    var retList = ListBuffer(start)
    if(start<=1) return retList
    while(term > 1) {
      if(term % 2 == 0) {
        term = term/2l
      } else {
        term = (3l * term) + 1
      }

      retList.addOne(term)
    }
    retList.addOne(1l)
    retList
  }
}

object Solver extends App {
  println("sol is " + LongestCollatz(1000000))
}

使用 visualvm 和一些日志记录，我看到在进入下一步之前，bruteforce 方法中范围流的每个步骤都将完全完成所有 1M 数字。所以： .map(toCollatzSequence) 正在加载所有 1M 项的序列并将它们保存在堆中，直到它可以到达下一个 .map() 语句以将它们变成单数长度。我能够通过修改函数来解决该问题：

  def bruteForce(upperBound: Long) = (1l to upperBound)
    .map(l => toCollatzSequence(l).length)
    .max

因此将两个 map 语句合并为一个。我的问题是，我把两张地图分开是不是犯了错误？或者对于这类问题，功能性解决方案通常不是一个好主意？

Answer 1

您应该使用 .view 将其转换为非严格集合。

您通过将两个 .map 合并为一个来避免直接列表，但是当您只是调用 .max.

时，长度列表也是可以避免的

def bruteForce(upperBound: Long) = (1l to upperBound)
  .view
  .map(toCollatzSequence)
  .map(_.length)
  .max

这应该可以解决暴力问题。

Answer 2

did I make an error by separating out the two maps?

对多个 .map() 调用进行排序很少是个好主意。将它们结合起来会减少你遍历集合的次数。

is a functional solution not a good idea in general for this type of problem?

我不知道你为什么这么说。 不是的好主意是在想出蛮力解决方案后停下来。蛮力只是一个起点。

这是一个使用尾递归、惰性求值且没有可变数据的解决方案。

@annotation.tailrec
def getLen(n: Long, count: Int = 0): Int =
  if (n < 2) count + 1
  else getLen(if (n % 2 == 0) n / 2 else 3 * n + 1, count + 1)

LazyList.tabulate(1000000)(n => (getLen(n),n)).max._2