Алгоритмы оптимизации с огромными коллекциями с огромными числами (функционально)

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

Джувиан дал отличный ответ, изложив некоторые алгоритмические стратегии. Вот некоторые из этих идей, но реализованные в 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, что из-за того, что он должен быть нечетным числом цифр, кажется очень вероятным правильным.

Answer 2

Я не знаю, scala, но вот несколько советов:

• Ответ должен содержать нечетное количество цифр. Это потому, что если ответ имеет четное количество цифр, он будет делиться на 11. Поскольку вы никогда не генерируете числа с коэффициентом 11, ответ должен иметь нечетное количество цифр (9).
• Сито не обязательно, диапазон маленький, а числа маленькие, стандартного способа должно быть достаточно, чтобы найти все 8363 простых числа в этом диапазоне менее чем за 1 секунду.
• Нам нужно будет сделать до 8363 * 8363 умножений, что не так уж и плохо, но самая дорогая часть проверяет, является ли умножение палиндромом. Мы должны попытаться максимально сократить эти проверки.
• Для каждого простого числа, если вы умножите его на другие простые числа в порядке убывания, первый найденный вами палиндром будет максимально возможным для этого простого числа, поэтому нет необходимости итерировать остальные
• Если умножение меньше, чем самый высокий найденный палиндром, проверять, является ли это палиндромом, нет необходимости

Не уверен, сколько из этих советов вы можете применить к своему коду функциональным способом, но вот не функциональный подход javascript, который в полной мере использует эти идеи и занимает менее 1 секунды:

var start = new Date().getTime();

function isPrime(n) {
    if (n % 2 == 0) return false;
    for (var i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

var primes = []

for (var i = 99999; i >= 10000; i--) {
    if (isPrime(i)) primes.push(i)
}

var max = 0;

const isPalindrome = (string) => string == string.split('').reverse().join('');

var max = 0;

for (var i = 0; i < primes.length; i++) {
    var prime1 = primes[i];
    for (var j = i; j < primes.length; j++) {
        var prime2 = primes[j];
        var mul = prime1 * prime2
        if (mul > 999999999) continue;
        if (max > mul) break;
        if (isPalindrome(mul.toString())) {
            max = mul;
        }
    }
}


console.log(max, "took " + (new Date().getTime() - start) + " ms");

Дополнительный совет : он может быть дополнительно оптимизирован путем вычисления с помощью бинарного поиска первого простого числа2, в результате чего в Prime1 будет 9 цифр вместо 10, таким образом пропуская много итераций по простым числам2