algorithm - 具有大量集合的优化算法(以功能方式)

Question

我最近开始学习scala，发现了一个有趣的任务。挑战在于找到最大的回文数(例如 144858441)，它是两个 5 位素数的乘积。此外，我还需要返回两个乘数。我是这样解决的:

case class PrimesHolder(a:Int, b:Int, palindrome:BigInt) 

object palindromeFinder {
  def find(from:Int, to:Int) = {
    // getting all primes between FROM and TO 
    val primes = calculatePrimesStreamBetween(from, to)

    // getting all possible compositions of primes and filtering non-palindromes, 
    //   result is a list of tuples (BigInt, Int), first val is palindrome, second is one of prime multipliers (we'll get the second one by division)
    val palindromes = multiplyAll(primes).filter(palindromeFilter)

    // looking for maximum  
    val res = if (palindromes.nonEmpty) palindromes.maxBy(_._1) else (BigInt(0), 0)

    // return statement
    if (res._2 != 0) PrimesHolder(res._2, (res._1 / res._2).toInt, res._1) else PrimesHolder(0, 0, 0)
  }

  // it's The Sieve Eratosthen implementation 
  private def calculatePrimesStreamBetween(from:Int, to: Int): List[Int] = {
    val odds = Stream.from(3, 2).takeWhile(_ <= Math.sqrt(to).toInt)
    val composites = odds.flatMap(i => Stream.from(i * i, 2 * i).takeWhile(_ <= to))
    Stream.from(3, 2).takeWhile(i => i >= from && i <= to).diff(composites).toList
  }

  // multiplies values in lists "each by each", yields list of tuples (BigInt, Int)
  private def multiplyAll(a:List[Int]) = a.flatMap(item => a.filter(j => j >= item).map(i => (BigInt(i) * item, i)))

  // palindrome filter function for passing to .filter((BigInt, Int) => Boolean)
  private def palindromeFilter(num:(BigInt, Int)):Boolean = {
    if (num._1.toString.head != num._1.toString.last) false else num._1.toString == num._1.toString.reverse
  }
}  

/////////////////////////////////////////////////////////
object Main {
  def main(args: Array[String]): Unit = {
    val res = palindromeFinder.find(10000, 99999)
    println(s"${res.palindrome} = ${res.a} * ${res.b}")
  }
}

但是这段代码需要太多内存，在我的电脑上需要大约 30 秒。 为了得到结果，我需要在执行前输入 -J-Xms1024m -J-Xmx3000m 参数。 如何以功能方式优化我的代码？ 谢谢!

Answer 1

juvian 给出了一个很好的答案，概述了一些算法策略。以下是其中一些想法，但在 Scala 中实现，纯粹是功能性的:

def primes(min: Int, max: Int): List[Int] = {
  val primeCandidates = 2 #:: Stream.from(3, 2)
  def isPrime(n: Int): Boolean = {
    primeCandidates.takeWhile(x => x * x <= n).forall(x => n % x != 0)
  }
  primeCandidates.dropWhile(_ < min).takeWhile(_ < max).filter(isPrime).toList
}

@scala.annotation.tailrec
final def findLargestPalindrome(primesDesc: List[Int], bestSoFar: Option[(Int, Int, Long)]): Option[(Int, Int, Long)] = primesDesc match {
  case p1 :: rest => {
    val needToCheck = bestSoFar match {
      case Some((_, _, product)) => rest.takeWhile(_.toLong * p1 > product)
      case None => rest
    }
    val result = needToCheck.find { p2 =>
      val product = p1.toLong * p2
      val str = product.toString
      str == str.reverse
    }
    val newBest = result.map(p2 => (p1, p2, p1.toLong * p2)).orElse(bestSoFar)
    findLargestPalindrome(rest, newBest)
  }
  case Nil => bestSoFar
}

val primesDesc = primes(10000, 100000).reverse
findLargestPalindrome(primesDesc, None)

我认为在 findLargestPalindrome 中我可能重复了太多次乘法，所以你可以考虑收紧它，但实际上它还是很快的。

它发现 33211 * 30109 = 999949999，由于它需要是奇数位，这似乎极有可能是正确的。