Исправлен код Scala, использующий номера разделов с вычислением потока, НО слишком медленно - PullRequest
Новая
       32

Исправлен код Scala, использующий номера разделов с вычислением потока, НО слишком медленно

1 голос
/ 27 сентября 2019

Я хочу поговорить о том, как действовать.
1. Неправильное использование Scala.Я должен попытаться улучшить код.
2. Эффективность алгоритма низкая.Я должен подумать об эффективном алгоритме.

Цель : может быстро рассчитать максимальное число из более чем 1000 коллекций номеров разделов.

Номер раздела:
например,

5 -> (5), (1, 4), (2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 1, 2), (1, 1, 1, 1, 1)

Я прошу «Я хочу преобразовать из Python в Scala ту функцию разделения, используя Vector» , и меня вчера научили использовать Stream.
Я исправил код, я могу использовать 10, 50 и так далее.Но использование больших чисел (например, 100, 1000 или 10000) не вычисляло максимальное число.
Оно рассчитывалось от Stream.last до Stream.head.

В моем понимании, тип потока может добавить элементтолько в заголовке, поэтому порядок чисел меняется с первого кода.

код 

import scala.math.floor

class PartitionNumbers(startNum: Int, point: Int) {
  var maxNum = 0
  var tmpNum = 0

  private def appendOnes(n: Int, s: Stream[Int] = Stream.empty[Int]): Stream[Int] = {
    if (n == 0) s
    else appendOnes(n - 1, 1 #:: s)
  }

  private def partition(n: Int, k: Int, tmpStream: Stream[Int] = Stream.empty): Int = {
    if (n == 0) tmpNum = calculate(tmpStream)
    else if (n == 1 | k == 1) tmpNum = calculate(appendOnes(n))
    else {
      if (n >= k) partition(n - k, k, k #:: tmpStream)
      partition(n, k - 1, tmpStream)
    }
    if (maxNum < tmpNum) maxNum = tmpNum
    maxNum
  }

  def searchMax(n: Int = point): Int = {
    partition(n, n)
  }

  def calculate(usePointsStream: Stream[Int], num: Int = startNum): Int = {
    if (usePointsStream.isEmpty) {
      num
    } else {
      calculate(usePointsStream.init, floor(num * (100 + usePointsStream.last) / 100).toInt)
    }
  }

}

пример вывода 

val pn_1 = new PartitionNumbers(100, 10)
println(pn_1.searchMax())  // -> 110

val pn_2 = new PartitionNumbers(1000, 50)
println(pn_2.searchMax())  // -> 1630

val pn_3 = new PartitionNumbers(10000, 100)
println(pn_3.searchMax())  // Can't calculate within 3 minutes using Ryzen 7 2700X.
...